💬 Discord
Sign In
NeetCode #888LC-867EasyMath & GeometryNC 250
← Back to All Problems

#888 · #867 · Transpose Matrix(转置矩阵)

📌 Problem Statement & Constraints

Given a 2D integer array matrix, return its transpose: the matrix whose element at row j, column i equals matrix[i][j]. Constraints: 1 <= m, n <= 1000, 1 <= m * n <= 10^5, -10^9 <= matrix[i][j] <= 10^9.

💡 Core Algorithmic Approaches

  1. The transpose has dimensions n x m, so allocate a result of exactly that shape.
  2. Copy each element matrix[i][j] into result[j][i].
  3. Unlike the square in-place case, a rectangular matrix cannot be transposed in place, so a new array is unavoidable.
  4. The loop order does not affect correctness, though writing rows in the source order is friendlier to the cache in low-level languages.

💻 Benchmark Python3 Implementation

class Solution:
    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
        m, n = len(matrix), len(matrix[0])
        res = [[0] * m for _ in range(n)]     # n rows, m columns
        for i in range(m):
            for j in range(n):
                res[j][i] = matrix[i][j]
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): each element is copied exactly once.
💾 Space Complexity
O(m * n): the output matrix.

⚠️ Interview Pitfalls & Follow-ups

  • Allocating [[0] * n for _ in range(m)]: the dimensions are swapped; the result must have n rows of m columns.
  • Writing [[0] * m] * n: every row is an alias of the same list, so the writes collide.
  • Attempting an in-place transpose: impossible for a non-square matrix.
  • Transposing only the square sub-block: the rectangular remainder must also be copied.