Skip to main content
CodePeetCodePeet
CodePeet 250

Transpose Matrix

EASYProblemSolveExternal Links

Description

Given a two-dimensional integer array matrix, return its transpose.

The transpose of a matrix is formed by flipping it over its main diagonal, which runs from the top-left corner to the bottom-right corner. This operation swaps the row and column index of every element: the element originally at row i, column j moves to row j, column i in the transposed matrix.

If the original matrix has m rows and n columns (an m × n matrix), the transposed result will have n rows and m columns (an n × m matrix).

Examples

Example 1

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]

Output: [[1,4,7],[2,5,8],[3,6,9]]

Explanation: This is a 3×3 square matrix. Row 0 [1, 2, 3] becomes column 0 of the result. Row 1 [4, 5, 6] becomes column 1. Row 2 [7, 8, 9] becomes column 2. For a square matrix, the transpose reflects elements across the main diagonal. Elements on the diagonal (1, 5, 9) stay in place, while off-diagonal elements swap: the 2 at position (0,1) swaps with the 4 at position (1,0), the 3 at (0,2) swaps with 7 at (2,0), and the 6 at (1,2) swaps with 8 at (2,1).

Example 2

Input: matrix = [[1,2,3],[4,5,6]]

Output: [[1,4],[2,5],[3,6]]

Explanation: The original is a 2×3 matrix (2 rows, 3 columns). The transpose becomes a 3×2 matrix (3 rows, 2 columns). Row 0 [1, 2, 3] becomes column 0 of the result, and row 1 [4, 5, 6] becomes column 1. Notice how the dimensions flip: the original's 2 rows become 2 columns, and its 3 columns become 3 rows in the output.

Example 3

Input: matrix = [[1]]

Output: [[1]]

Explanation: A 1×1 matrix contains a single element. Its transpose is identical to itself, since flipping a single value over the diagonal produces no change.

Constraints

  • m == matrix.length
  • n == matrix[i].length
  • 1 ≤ m, n ≤ 1000
  • 1 ≤ m × n ≤ 10^5
  • -10^9 ≤ matrix[i][j] ≤ 10^9

Editorial

Brute Force

Intuition

The most natural way to think about transposing a matrix is to focus on what each column of the original becomes in the result. By definition, column j of the original matrix becomes row j of the transposed matrix.

Imagine you have a spreadsheet with rows of student data. If you wanted to reorganize it so that each column becomes a row, you would go column by column: pick out all the values running down column 0, write them across as a new row, then do the same for column 1, column 2, and so on.

This column-extraction approach directly translates the definition of transpose into code. For each column index j (from 0 to n-1), we walk down the rows collecting matrix[0][j], matrix[1][j], ..., matrix[m-1][j] into a new list, and that list becomes one row of our result.

Step-by-Step Explanation

Let's trace through with matrix = [[1, 2, 3], [4, 5, 6]]. The original has m=2 rows and n=3 columns, so the transpose will have 3 rows and 2 columns.

Step 1: Initialize an empty result list. We will build it one row at a time.

Step 2: Extract column 0 of the original. Walk down the rows: matrix[0][0] = 1, matrix[1][0] = 4. Collect these into a row [1, 4]. This becomes row 0 of the result.

Step 3: Extract column 1 of the original. Walk down: matrix[0][1] = 2, matrix[1][1] = 5. Collect into row [2, 5]. This becomes row 1 of the result.

Step 4: Extract column 2 of the original. Walk down: matrix[0][2] = 3, matrix[1][2] = 6. Collect into row [3, 6]. This becomes row 2 of the result.

Step 5: All 3 columns processed. The transposed matrix is [[1, 4], [2, 5], [3, 6]].

Column Extraction — Building the Transpose Row by Row — Watch how each column of the original matrix is extracted and placed as a row in the result, filling the transpose grid one row at a time.

Algorithm

  1. Determine m (number of rows) and n (number of columns) of the input matrix
  2. Create an empty result list
  3. For each column index j from 0 to n-1:
    • Create an empty row list
    • For each row index i from 0 to m-1:
      • Append matrix[i][j] to the row list
    • Append the completed row to the result
  4. Return the result

Code

class Solution {
public:
    vector<vector<int>> transpose(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> result;
        
        for (int j = 0; j < n; j++) {
            vector<int> row;
            for (int i = 0; i < m; i++) {
                row.push_back(matrix[i][j]);
            }
            result.push_back(row);
        }
        
        return result;
    }
};
class Solution:
    def transpose(self, matrix: list[list[int]]) -> list[list[int]]:
        m = len(matrix)
        n = len(matrix[0])
        result = []
        
        for j in range(n):
            row = []
            for i in range(m):
                row.append(matrix[i][j])
            result.append(row)
        
        return result
class Solution {
    public int[][] transpose(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] result = new int[n][m];
        
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                result[j][i] = matrix[i][j];
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(m × n)

We visit every element of the original matrix exactly once. The outer loop runs n times (once per column), and the inner loop runs m times (once per row), giving m × n total operations. Each operation (reading a value and appending it) takes O(1) amortized time.

Space Complexity: O(m × n)

The result matrix itself requires n × m = m × n space to store all the transposed elements. Additionally, in languages like C++ and Python, the temporary row vectors/lists created during column extraction add minor overhead due to dynamic allocation and resizing, though this does not change the asymptotic space complexity.

Why This Approach Is Not Efficient

Both the brute force and the optimal approach share the same asymptotic complexity of O(m × n) in time and space — since we must read every element and write it to a new position, this is the theoretical minimum. However, the column-extraction approach has two practical drawbacks worth understanding:

1. Column-Wise Memory Access Pattern: When extracting column j, we read matrix[0][j], matrix[1][j], matrix[2][j], and so on. In most programming languages, two-dimensional arrays are stored in row-major order, meaning all elements of row 0 are contiguous in memory, followed by all elements of row 1, etc. Reading down a column means jumping across rows — accessing non-contiguous memory locations. This causes cache misses on large matrices, because the CPU cache loads a block of consecutive memory addresses at a time, and jumping between rows wastes those prefetched values.

2. Dynamic Allocation Overhead: In the brute force, we build each result row by appending elements one at a time (using push_back in C++ or append in Python). Dynamic list resizing involves occasional memory reallocation and copying, adding constant-factor overhead compared to writing directly into pre-allocated memory.

With m × n up to 100,000 elements, these constant-factor inefficiencies can noticeably impact execution time. The next approach addresses both concerns by pre-allocating the result and reading the original in row-major order.

Optimal Approach - Direct Index Mapping

Intuition

Instead of thinking column-by-column, we can approach the transpose from the opposite direction: iterate through the original matrix row by row, and for each element at position (i, j), place it directly at position (j, i) in the result.

The key improvement is that we pre-allocate the entire result matrix upfront (with dimensions n × m) and then fill it in using direct index assignment rather than appending to growing lists. This eliminates dynamic allocation overhead.

Additionally, by iterating the original matrix in row-major order (row 0 left to right, then row 1 left to right, etc.), we read elements in the order they are stored in memory. This is cache-friendly because consecutive memory accesses hit the same cache line, reducing cache misses.

The mapping formula is simple: result[j][i] = matrix[i][j]. For every element in the original, we just swap its row and column indices when writing to the result.

Step-by-Step Explanation

Let's trace through with matrix = [[1, 2, 3], [4, 5, 6]]. The original has m=2 rows and n=3 columns. We pre-allocate a 3×2 result matrix.

Step 1: Pre-allocate result as a 3×2 matrix: [[0, 0], [0, 0], [0, 0]].

Step 2: Process row 0 of the original. For each element matrix[0][j], apply the mapping result[j][0] = matrix[0][j]:

  • matrix[0][0] = 1 → result[0][0] = 1
  • matrix[0][1] = 2 → result[1][0] = 2
  • matrix[0][2] = 3 → result[2][0] = 3

Step 3: Process row 1 of the original. For each element matrix[1][j], apply the mapping result[j][1] = matrix[1][j]:

  • matrix[1][0] = 4 → result[0][1] = 4
  • matrix[1][1] = 5 → result[1][1] = 5
  • matrix[1][2] = 6 → result[2][1] = 6

Step 4: All elements placed. Result: [[1, 4], [2, 5], [3, 6]].

Direct Index Mapping — Row-Major Traversal of the Original — Watch how iterating the original matrix row by row fills the transpose column by column, using the direct mapping result[j][i] = matrix[i][j].

Algorithm

  1. Determine m (rows) and n (columns) of the input matrix
  2. Pre-allocate a result matrix of size n × m (all values initialized to 0)
  3. For each row index i from 0 to m-1:
    • For each column index j from 0 to n-1:
      • Set result[j][i] = matrix[i][j]
  4. Return the result

Code

class Solution {
public:
    vector<vector<int>> transpose(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> result(n, vector<int>(m));
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                result[j][i] = matrix[i][j];
            }
        }
        
        return result;
    }
};
class Solution:
    def transpose(self, matrix: list[list[int]]) -> list[list[int]]:
        m = len(matrix)
        n = len(matrix[0])
        result = [[0] * m for _ in range(n)]
        
        for i in range(m):
            for j in range(n):
                result[j][i] = matrix[i][j]
        
        return result
class Solution {
    public int[][] transpose(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] result = new int[n][m];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                result[j][i] = matrix[i][j];
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(m × n)

We visit every element of the original matrix exactly once. The outer loop runs m times and the inner loop runs n times, giving m × n total operations. Each operation is a direct array assignment in O(1) time — no appending or resizing involved.

Space Complexity: O(m × n)

The result matrix requires n × m = m × n space. Since the problem asks us to return a new matrix (the original and transpose may have different dimensions), this space is unavoidable. Unlike the brute force, no temporary lists are created — the result is the only additional allocation.

This approach achieves the theoretical minimum complexity for matrix transposition: we must read every element at least once (Ω(m × n) time) and store every element in the output (Ω(m × n) space). No algorithm can do better.