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:
Input: mat = [[1,2],[3,4]], r = 1, c = 4 Output: [[1,2,3,4]]
Example 2:
Input: mat = [[1,2],[3,4]], r = 2, c = 4 Output: [[1,2],[3,4]]
Constraints:
m == mat.lengthn == mat[i].length1 <= m, n <= 100-1000 <= mat[i][j] <= 10001 <= r, c <= 300Problem Overview: You receive an m x n matrix and two integers r and c. The task is to reshape the matrix into an r x c matrix while preserving the original row‑major order of elements. If the reshape is impossible (because m * n != r * c), return the original matrix unchanged.
Approach 1: Flatten and Reconstruct (O(m*n) time, O(m*n) space)
The direct strategy is to first flatten the matrix into a 1D list, then rebuild the result matrix with the new dimensions. Iterate through every element of the input matrix row by row and append it to a temporary array. Once flattened, iterate through the array again and fill the new r x c matrix sequentially. This preserves row‑major order automatically. The approach is simple and readable, making it a good first implementation when working with array transformations or quick matrix restructuring tasks. The tradeoff is extra memory for the flattened array.
Approach 2: Index Mirroring (O(m*n) time, O(1) extra space)
A more efficient method avoids creating a temporary array. Treat the matrix as if it were a flattened sequence of length m*n. For each linear index k, compute its original position and its reshaped position using arithmetic. The original coordinates are row = k / n and col = k % n. The new coordinates become newRow = k / c and newCol = k % c. Copy the value directly from the original matrix to the reshaped matrix using these calculated indices. This technique mirrors indices between two matrix layouts and is common in problems involving matrix traversal and coordinate mapping. It achieves the same result while using only the output matrix as additional memory.
Recommended for interviews: Interviewers expect the index mirroring approach because it demonstrates a clear understanding of row‑major ordering and index mapping in a simulation style problem. Starting with the flatten‑and‑reconstruct idea shows you recognize the ordering requirement. Transitioning to index mirroring proves you can remove unnecessary memory and reason about element positions mathematically.
This approach involves two main steps: flattening the original matrix into a one-dimensional array and then reconstructing it into the desired dimensions. The flattening process collects all elements by iterating row-wise over the original matrix. Then, if the total number of elements matches the product of new dimensions r and c, the method distributes these elements row-wise into the new matrix. If the element count does not match, the original matrix is returned.
The C code first checks if the reshape can be performed by comparing the number of elements in the original and desired matrices. If possible, it allocates memory for the new matrix and reshapes by using modulus and division to determine the new indices based on flattened array index i.
Time Complexity: O(m * n) where m and n are the dimensions of the original matrix.
Space Complexity: O(r * c) for the reshaped matrix.
Index Mirroring leverages mathematical transformation to directly address elements from the original matrix into the new shape without explicitly flattening. It avoids extra space for a flat array and directly computes 2D indices in the new layout.
In this solution, we directly calculate the new position (index / c, index % c) for elements from the original position (i, j) in mat, avoiding the need for an intermediate one-dimensional array.
Time Complexity: O(m * n).
Space Complexity: O(r * c) for storing reshaped matrix.
First, we get the number of rows and columns of the original matrix, denoted as m and n respectively. If m times n neq r times c, then the matrix cannot be reshaped, and we return the original matrix directly.
Otherwise, we create a new matrix with r rows and c columns. Starting from the first element of the original matrix, we traverse all elements in row-major order and place the traversed elements into the new matrix in order.
After traversing all elements of the original matrix, we get the answer.
The time complexity is O(m times n), where m and n are the number of rows and columns of the original matrix, respectively. Ignoring the space consumption of the answer, the space complexity is O(1).
TypeScript
| Approach | Complexity |
|---|---|
| Flatten and Reconstruct | Time Complexity: O(m * n) where m and n are the dimensions of the original matrix. |
| Index Mirroring | Time Complexity: O(m * n). |
| Simulation | — |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Flatten and Reconstruct | O(m*n) | O(m*n) | Best for readability and quick implementation when extra memory is acceptable |
| Index Mirroring | O(m*n) | O(1) extra space | Preferred in interviews and memory‑constrained scenarios |
LeetCode 566. Reshape the Matrix Solution Explained - Java • Nick White • 14,357 views views
Watch 9 more video solutions →Practice Reshape the Matrix with our built-in code editor and test cases.
Practice on FleetCode