Log inSign up
easyLeetCodeNot Started

Reshape the Matrix

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

Arrays
Solve on LeetCode
Lesson

Problem Statement

In MATLAB, there is a handy function called reshape which can reshape an m x n matrix into a new one with a different size r x c keeping its original data.

You are given an m x n matrix mat and two integers r and c representing the number of rows and the number of columns of the wanted reshaped matrix.

The reshaped matrix should be filled with all the elements of the original matrix in the same row-traversing order as they were.

If the reshape operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.

Example 1 · Valid 2x2 to 1x4 Reshape:

Input: mat = [[1, 2], [3, 4]], r = 1, c = 4
Output: [[1, 2, 3, 4]]
Explanation: The row-traversal of mat is [1, 2, 3, 4]. The new reshaped matrix is a 1 x 4 matrix, filled with elements row by row.

Example 2 · Invalid Dimensions (Total Elements Mismatch):

Input: mat = [[1, 2], [3, 4]], r = 2, c = 4
Output: [[1, 2], [3, 4]]
Explanation: There is no way to reshape a 2 x 2 matrix (4 elements) into a 2 x 4 matrix (8 elements). Output is the original matrix.

Example 3 · 2x2 to 4x1 Column Vector Reshape:

Input: mat = [[1, 2], [3, 4]], r = 4, c = 1
Output: [[1], [2], [3], [4]]
Explanation: The 4 elements are arranged into 4 rows with 1 column each.

Constraints:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 100
  • -1000 <= mat[i][j] <= 1000
  • 1 <= r, c <= 300

Prerequisites

Before attempting this problem, you should be comfortable with:

  • 2D array grid traversal (row-major order)
  • Integer division / for row calculation and modulo % for column calculation
  • Matrix dimension validation

What You'll Learn

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

  • Master 2D-to-1D and 1D-to-2D coordinate transformations: row = k / cols, col = k % cols.
  • Validate matrix dimension invariants before allocation.
  • Eliminate intermediate flat lists to achieve O(1) auxiliary space.
  • Write clean implementations across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

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

Signals to Look For:

  • Transforming a matrix from dimension (m, n) to dimension (r, c) in row-major order.
  • Need mathematical mapping between 2D coordinates (i, j) and 1D index k.
  • Requires O(1) auxiliary space beyond the output container.

Algorithmic Decision Tree:

  • First validate m * n == r * c. If false, return mat.
  • Map 1D index k: mat[k / n][k % n] -> result[k / c][k % c].

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Flatten to 1D Array then Populate Reshaped Matrix

Intuition

Flatten the m x n matrix into a 1D array of size m*n, then fill the target r x c matrix sequentially.

Algorithm

  1. 1. Let m = mat.length, n = mat[0].length. If m * n != r * c, return mat.
  2. 2. Flatten: Push all m*n elements into a 1D list flat.
  3. 3. Create new matrix reshaped of dimensions r x c.
  4. 4. Fill reshaped: For k from 0 to m*n-1, reshaped[floor(k / c)][k % c] = flat[k].
  5. 5. Return reshaped.

Flatten to 1D Buffer then Populate Reshaped Matrix

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3, 4]
Current operationSTEP 1 OF 6
Phase 1 — Flattening First Row: Traverse mat[0] = [1, 2]
Visual state
Values and pointers at this exact step
matrix
Input mat (2 × 2)2 × 2
c0
c1
r0
1
↑ Row 0
2
r1
3
4
Reshape
Reshaped res (1 × 4)1 × 4
c0
c1
c2
c3
r0
—
—
—
—
Variables at this step
Source Row
0
Buffer
[1, 2]
Buffer Size
2
Check / comparison
mat[0][0]=1, mat[0][1]=2 appended to flat buffer.
Decision / next transition
buffer.push(1), buffer.push(2).
Why this step matters

Phase 1 — Flattening First Row: Traverse mat[0] = [1, 2]. Extract elements into a temporary flat array: buffer = [1, 2].

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>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
17 int m = mat.size(), n = mat[0].size();
18 if (m * n != r * c) return mat;
19
20 vector<int> flat;
21 for (int i = 0; i < m; ++i) {
22 for (int j = 0; j < n; ++j) flat.push_back(mat[i][j]);
23 }
24
25 vector<vector<int>> res(r, vector<int>(c));
26 for (int k = 0; k < m * n; ++k) {
27 res[k / c][k % c] = flat[k];
28 }
29 return res;
30 }
31};
32
33int main() {
34 Solution sol;
35 vector<vector<int>> mat = {{1, 2}, {3, 4}};
36 int r = 1, c = 4;
37 vector<vector<int>> res = sol.matrixReshape(mat, r, c);
38
39 cout << "Reshaped Matrix:" << endl;
40 for (const auto& row : res) {
41 cout << "[";
42 for (size_t i = 0; i < row.size(); ++i) {
43 cout << row[i] << (i + 1 < row.size() ? ", " : "");
44 }
45 cout << "]" << endl;
46 }
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(M * N) — Iterates through all M x N elements twice in O(M * N) time.
  • Space complexity: O(M * N) — Allocates an auxiliary 1D array of size M x N, consuming O(M * N) memory.

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. Two-Pointer Row and Col Incrementor

Intuition

Traverse input matrix and maintain destination row and column pointers (dstRow, dstCol) in O(1) auxiliary space.

Algorithm

  1. 1. If m * n != r * c, return mat.
  2. 2. Initialize dstRow = 0, dstCol = 0, reshaped = new matrix of size r x c.
  3. 3. For i from 0 to m-1: - For j from 0 to n-1: - reshaped[dstRow][dstCol] = mat[i][j] - dstCol++ - If dstCol == c: dstCol = 0, dstRow++.
  4. 4. Return reshaped.

Two-Pointer (Row, Col) In-Flight Traversal

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3, 4]
Current operationSTEP 1 OF 6
Phase 1 — Initialize Target Coordinate Pointers: Maintain write pointers (outRow = 0, outCol = 0) without allocating an intermediate flat buffer
Visual state
Values and pointers at this exact step
matrix
Input mat (2 × 2)2 × 2
c0
c1
r0
1
↑ in (0,0)
2
r1
3
4
Reshape
Reshaped res (1 × 4)1 × 4
c0
c1
c2
c3
r0
—
↑ out (0,0)
—
—
—
Variables at this step
outRow
0
outCol
0
res
[[—, —, —, —]]
Check / comparison
Start at outRow = 0, outCol = 0.
Decision / next transition
Allocate res[1][4]. Begin streaming directly.
Why this step matters

Phase 1 — Initialize Target Coordinate Pointers: Maintain write pointers (outRow = 0, outCol = 0) without allocating an intermediate flat buffer.

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>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
17 int m = mat.size(), n = mat[0].size();
18 if (m * n != r * c) return mat;
19
20 vector<vector<int>> res(r, vector<int>(c));
21 int dstRow = 0, dstCol = 0;
22 for (int i = 0; i < m; ++i) {
23 for (int j = 0; j < n; ++j) {
24 res[dstRow][dstCol++] = mat[i][j];
25 if (dstCol == c) {
26 dstCol = 0;
27 dstRow++;
28 }
29 }
30 }
31 return res;
32 }
33};
34
35int main() {
36 Solution sol;
37 vector<vector<int>> mat = {{1, 2}, {3, 4}};
38 int r = 1, c = 4;
39 vector<vector<int>> res = sol.matrixReshape(mat, r, c);
40
41 cout << "Reshaped Matrix:" << endl;
42 for (const auto& row : res) {
43 cout << "[";
44 for (size_t i = 0; i < row.size(); ++i) {
45 cout << row[i] << (i + 1 < row.size() ? ", " : "");
46 }
47 cout << "]" << endl;
48 }
49 return 0;
50}

Time & Space Complexity

  • Time complexity: O(M * N) — Single pass through all M x N elements in O(M * N) time.
  • Space complexity: O(1) — Only uses two scalar destination pointers. Space is O(1).

3. Direct 1D Index Mapping (Modulo & Division Arithmetic)

Intuition

Map 1D index k from 0 to m*n-1 directly: source is mat[k / n][k % n], target is res[k / c][k % c].

Algorithm

  1. 1. Let m = mat.length, n = mat[0].length.
  2. 2. If m * n != r * c, return mat.
  3. 3. Allocate reshaped matrix of size r x c.
  4. 4. For k from 0 to m * n - 1: - reshaped[k / c][k % c] = mat[k / n][k % n].
  5. 5. Return reshaped.

Direct 1D Arithmetic Index Mapping (Modulo & Division)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3, 4]
Current operationSTEP 1 OF 6
Phase 1 — Mathematical Invariant Formulation: Any flat index i maps to 2D coordinates via: row = i / cols, col = i % cols
Visual state
Values and pointers at this exact step
matrix
Input mat (2 × 2)2 × 2
c0
c1
r0
1
↑ i=0: (0,0)
2
r1
3
4
Reshape
Reshaped res (1 × 4)1 × 4
c0
c1
c2
c3
r0
—
↑ i=0: (0,0)
—
—
—
Variables at this step
Formula
mat[i/2][i%2] -> res[i/4][i%4]
i
0
Check / comparison
Formula: mat[i / 2][i % 2] -> res[i / 4][i % 4].
Decision / next transition
Begin loop i from 0 to 3.
Why this step matters

Phase 1 — Mathematical Invariant Formulation: Any flat index i maps to 2D coordinates via: row = i / cols, col = i % cols. Source has n = 2 cols, target has c = 4 cols.

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>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
17 int m = mat.size(), n = mat[0].size();
18 if (m * n != r * c) return mat;
19
20 vector<vector<int>> res(r, vector<int>(c));
21 for (int k = 0; k < m * n; ++k) {
22 res[k / c][k % c] = mat[k / n][k % n];
23 }
24 return res;
25 }
26};
27
28int main() {
29 Solution sol;
30 vector<vector<int>> mat = {{1, 2}, {3, 4}};
31 int r = 1, c = 4;
32 vector<vector<int>> res = sol.matrixReshape(mat, r, c);
33
34 cout << "Reshaped Matrix:" << endl;
35 for (const auto& row : res) {
36 cout << "[";
37 for (size_t i = 0; i < row.size(); ++i) {
38 cout << row[i] << (i + 1 < row.size() ? ", " : "");
39 }
40 cout << "]" << endl;
41 }
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(M * N) — Single loop iterates exactly M * N times, performing O(1) arithmetic mappings per step.
  • Space complexity: O(1) — Output matrix does not count toward auxiliary space. Extra space is 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: Flatten to 1D Array then Populate Reshaped MatrixO(M * N)O(M * N)Flatten the m x n matrix into a 1D array of size m*n, then fill the target r x c matrix sequentially.Repeated redundant scans over the input.
2.Approach 2: Two-Pointer Row and Col IncrementorO(M * N)O(1)Traverse input matrix and maintain destination row and column pointers (dstRow, dstCol) in O(1) auxiliary space.Auxiliary memory allocation or sorting step.
3.Approach 3: Direct 1D Index Mapping (Modulo & Division Arithmetic)OptimalO(M * N)O(1)Map 1D index k from 0 to m*n-1 directly: source is mat[k / n][k % n], target is res[k / c][k % c].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:

  • Dimension Mismatch (Illegal Reshape) — Input: mat = [[1, 2], [3, 4]], r = 2, c = 4, Expected: [[1, 2], [3, 4]] — Total elements 4 != 8; original matrix must be returned immediately.
  • Identical Reshape Dimensions (r == m and c == n) — Input: mat = [[1, 2], [3, 4]], r = 2, c = 2, Expected: [[1, 2], [3, 4]] — Valid reshape returning identical matrix.
  • Single Element Matrix — Input: mat = [[5]], r = 1, c = 1, Expected: [[5]] — 1x1 matrix returns [[5]].

Interview Tips & Best Practices

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

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

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 Reshape the Matrix?

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

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

Back to DSA Sheet