Transpose Matrix — Editorial

Opening the reading…

Intuitionwhy swapping the indices is the entire transformation

A matrix entry is identified by two coordinates: its row and its column. Transposing does not change the value; it changes which coordinate is treated as the row and which is treated as the column. Therefore, an entry at original position i, j must appear at position j, i in the result.

If the original matrix has m rows and n columns, the result has n rows and m columns. Each original row becomes a result column, while each original column becomes a result row. Allocate that shape first, then visit every original position exactly once and write its value into the swapped position.

Approachone allocation and one index swap

Read m as the number of rows and n as the number of columns, because these dimensions determine both the result shape and the loop limits.

Allocate a result with n rows and m columns, because transposition exchanges the roles of rows and columns; using m by n would make the rectangular case impossible to fill correctly.

Visit each original row i from 0 through m - 1, because every row contributes values to a different region of the result.

Within that row, visit each column j from 0 through n - 1, because skipping a column would leave one result position without its original value.

Assign result[j][i] = matrix[i][j], because transposition changes the coordinate order while preserving the value.

Return the completed result after both loops finish, because every one of the m x n original entries has then been copied exactly once.

Complexitythe input contains m x n entries

MEASURE	BOUND	WHY
Time	O(m x n)	The nested loops process every one of the m x n input entries once, and each iteration performs one constant-time assignment. No entry is revisited or compared with another.
Space	O(m x n) extra	The result stores m x n integers and is required output, so it is excluded from the extra-space bound. Apart from that output, the algorithm keeps only the dimensions and loop variables, which use O(1) working memory.

Here, m is the number of rows and n is the number of columns in the input matrix.

Annotated solutionC++ · direct construction · the index swap in one pass

CPPAllocate the reversed shape, then copy every value with its row and column indices exchanged.

#include <vector>
using namespace std;

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;
    }
};

The allocation and assignment lines work together. result has n rows because each original column becomes a result row, and each result row has m entries because it receives one value from every original row. The assignment uses result[j][i], not result[i][j], which is the exact coordinate swap that defines transposition.