Log inSign up
easyLeetCodeNot Started

Transpose Matrix

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

Given a 2D integer array matrix, return *the* transpose *of* matrix.

The transpose of a matrix is the matrix flipped over its main diagonal, switching the matrix's row and column indices.

Example 1 · 3x3 Square Matrix:

Input: matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output: [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
Explanation: Row 0 [1, 2, 3] becomes Column 0. Row 1 [4, 5, 6] becomes Column 1. Row 2 [7, 8, 9] becomes Column 2.

Example 2 · 2x3 Rectangular Matrix:

Input: matrix = [[1, 2, 3], [4, 5, 6]]
Output: [[1, 4], [2, 5], [3, 6]]
Explanation: Input has 2 rows and 3 columns. The output transpose matrix has 3 rows and 2 columns.

Example 3 · 1x4 Single Row Matrix:

Input: matrix = [[1, 2, 3, 4]]
Output: [[1], [2], [3], [4]]
Explanation: 1x4 row vector becomes a 4x1 column vector.

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 1000
  • 1 <= m * n <= 105
  • -109 <= matrix[i][j] <= 109

Prerequisites

Before attempting this problem, you should be comfortable with:

  • 2D Array initialization and indexing in chosen language
  • Nested loops for grid traversal
  • Understanding matrix dimensions (rows vs columns)

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master 2D array dimension handling and reallocation.
  • Understand why rectangular matrices cannot be transposed in-place.
  • Formulate direct coordinate mapping formulas result[c][r] = matrix[r][c].

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Flipping rows to columns or columns to rows.
  • Dimensions change from R x C to C x R.
  • Access pattern where element at (r, c) must map directly to (c, r).

Algorithmic Decision Tree:

  • When transforming an R x C matrix into a C x R matrix: Allocate a new matrix result[C][R] and populate result[c][r] = matrix[r][c] via nested loops.

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Flat Array Copy & Re-indexing

Intuition

Flatten the M x N matrix into a 1D buffer, then reconstruct the N x M transposed matrix by reading transposed indices.

Algorithm

  1. 1. Let m = matrix.length, n = matrix[0].length.
  2. 2. Flatten matrix into 1D list flat of length m * n.
  3. 3. Create transposed grid of dimensions n x m.
  4. 4. For c from 0 to n-1 and r from 0 to m-1: transposed[c][r] = flat[r * n + c].
  5. 5. Return transposed.

Flat Array Copy & Re-indexing

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 4, 2, 5, 3, 6]
Current operationSTEP 1 OF 6
Phase 1 — Flatten Source Matrix: Read all elements in row-major order: [1, 2, 3, 4, 5, 6]
Visual state
Values and pointers at this exact step
array
S
1
2
3
4
5
6
0
↑ Row 0
1
2
3
4
5
Variables at this step
Buffer
[1, 2, 3, 4, 5, 6]
m
2
n
3
Check / comparison
Flatten 2x3 matrix into length-6 buffer.
Decision / next transition
buffer = [1, 2, 3, 4, 5, 6].
Why this step matters

Phase 1 — Flatten Source Matrix: Read all elements in row-major order: [1, 2, 3, 4, 5, 6]. Dimensions: m = 2, n = 3.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 vector<vector<int>> transpose(vector<vector<int>>& matrix) {
17 int m = matrix.size(), n = matrix[0].size();
18 vector<int> flat;
19 for (int r = 0; r < m; ++r) {
20 for (int c = 0; c < n; ++c) flat.push_back(matrix[r][c]);
21 }
22
23 vector<vector<int>> res(n, vector<int>(m));
24 for (int c = 0; c < n; ++c) {
25 for (int r = 0; r < m; ++r) {
26 res[c][r] = flat[r * n + c];
27 }
28 }
29 return res;
30 }
31};
32
33int main() {
34 Solution sol;
35 vector<vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}};
36 vector<vector<int>> res = sol.transpose(matrix);
37
38 cout << "Transposed Matrix:" << endl;
39 for (const auto& row : res) {
40 cout << "[";
41 for (size_t i = 0; i < row.size(); ++i) {
42 cout << row[i] << (i + 1 < row.size() ? ", " : "");
43 }
44 cout << "]" << endl;
45 }
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(M * N) — Flattens and reconstructs all M x N elements in O(M * N) time.
  • Space complexity: O(M * N) — Allocates auxiliary flat buffer of size M x N.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Column-First Traversal Row Building

Intuition

Iterate column by column, collecting each column into a new row of the transposed matrix.

Algorithm

  1. 1. Let m = matrix.length, n = matrix[0].length.
  2. 2. Initialize result list.
  3. 3. For c from 0 to n-1: - Create new row list. - For r from 0 to m-1: row.push(matrix[r][c]). - result.push(row).
  4. 4. Return result.

Column-First Traversal Row Building

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 4, 2, 5, 3, 6]
Current operationSTEP 1 OF 6
Phase 1 — Outer Loop Over Columns: Transposing means the c-th column of the original matrix becomes the c-th row of the result
Visual state
Values and pointers at this exact step
array
S
1
4
—
—
—
—
0
↑ Col 0
1
2
3
4
5
Variables at this step
Active Col c
0
Target Row
0
Check / comparison
c = 0: collect column 0 elements.
Decision / next transition
Begin extracting column 0.
Why this step matters

Phase 1 — Outer Loop Over Columns: Transposing means the c-th column of the original matrix becomes the c-th row of the result. Set c = 0.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 vector<vector<int>> transpose(vector<vector<int>>& matrix) {
17 int m = matrix.size(), n = matrix[0].size();
18 vector<vector<int>> res;
19 for (int c = 0; c < n; ++c) {
20 vector<int> row;
21 for (int r = 0; r < m; ++r) {
22 row.push_back(matrix[r][c]);
23 }
24 res.push_back(row);
25 }
26 return res;
27 }
28};
29
30int main() {
31 Solution sol;
32 vector<vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}};
33 vector<vector<int>> res = sol.transpose(matrix);
34
35 cout << "Transposed Matrix:" << endl;
36 for (const auto& row : res) {
37 cout << "[";
38 for (size_t i = 0; i < row.size(); ++i) {
39 cout << row[i] << (i + 1 < row.size() ? ", " : "");
40 }
41 cout << "]" << endl;
42 }
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(M * N) — Processes each cell in column-first order in O(M * N) time.
  • Space complexity: O(1) — Auxiliary space is O(1) beyond the output matrix.

3. Direct Coordinate Inversion (res[c][r] = matrix[r][c])

Intuition

Preallocate the N x M matrix and directly assign res[c][r] = matrix[r][c] with optimal cache efficiency.

Algorithm

  1. 1. Let m = matrix.length, n = matrix[0].length.
  2. 2. Allocate output matrix res of dimensions n x m.
  3. 3. For r from 0 to m-1: - For c from 0 to n-1: res[c][r] = matrix[r][c].
  4. 4. Return res.

Direct Coordinate Inversion (res[c][r] = matrix[r][c])

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 4, 2, 5, 3, 6]
Current operationSTEP 1 OF 6
Phase 1 — Setup Optimal Cache-Friendly Read: Pre-allocate result matrix res with inverted dimensions (cols x rows = 3 x 2)
Visual state
Values and pointers at this exact step
array
S
1
—
—
—
—
—
0
↑ r=0, c=0
1
2
3
4
5
Variables at this step
Source Shape
2x3
Target Shape
3x2
r
0
Check / comparison
res[c][r] = matrix[r][c]. Read sequentially from cache.
Decision / next transition
Allocate res[3][2]. Begin at r = 0.
Why this step matters

Phase 1 — Setup Optimal Cache-Friendly Read: Pre-allocate result matrix res with inverted dimensions (cols x rows = 3 x 2). Loop over r, then c to read source sequentially.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 vector<vector<int>> transpose(vector<vector<int>>& matrix) {
17 int m = matrix.size(), n = matrix[0].size();
18 vector<vector<int>> res(n, vector<int>(m));
19 for (int r = 0; r < m; ++r) {
20 for (int c = 0; c < n; ++c) {
21 res[c][r] = matrix[r][c];
22 }
23 }
24 return res;
25 }
26};
27
28int main() {
29 Solution sol;
30 vector<vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}};
31 vector<vector<int>> res = sol.transpose(matrix);
32
33 cout << "Transposed Matrix:" << endl;
34 for (const auto& row : res) {
35 cout << "[";
36 for (size_t i = 0; i < row.size(); ++i) {
37 cout << row[i] << (i + 1 < row.size() ? ", " : "");
38 }
39 cout << "]" << endl;
40 }
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(M * N) — Single nested loop visits every element once in O(M * N) time.
  • Space complexity: O(1) — Output matrix is required by the problem. Auxiliary memory is strictly O(1).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Approach 1: Flat Array Copy & Re-indexingO(M * N)O(M * N)Flatten the M x N matrix into a 1D buffer, then reconstruct the N x M transposed matrix by reading transposed indices.Repeated redundant scans over the input.
2.Approach 2: Column-First Traversal Row BuildingO(M * N)O(1)Iterate column by column, collecting each column into a new row of the transposed matrix.Auxiliary memory allocation or sorting step.
3.Approach 3: Direct Coordinate Inversion (res[c][r] = matrix[r][c])OptimalO(M * N)O(1)Preallocate the N x M matrix and directly assign res[c][r] = matrix[r][c] with optimal cache efficiency.None. Asymptotically optimal.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • 1 x N Single Row Matrix — Input: `, Expected: ` —
  • N x 1 Single Column Matrix — Input: `, Expected: ` —
  • 1 x 1 Single Cell Matrix — Input: `, Expected: ` —

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify whether the input matrix is guaranteed to be non-empty and rectangular.
  2. Mention to the interviewer why in-place transpose is impossible for non-square matrices without complex cycle leader algorithms.
  3. Highlight the difference between Transpose and Rotate 90 Degrees (Rotate 90 = Transpose + Reverse each row).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Transpose Matrix?

2.Why is the brute force approach suboptimal for large inputs in Transpose Matrix?

3.Which data structure or technique enables the optimal solution for Transpose Matrix?

Back to DSA Sheet