Reshape the Matrix solution and explanation
Google
TCS
9 more videos on this problem
LeetCode 566. Reshape the Matrix Solution Explained - JavaNick White · 7:27 · 14K views
Leetcode Reshape The MatrixCode with Alisha · 5:44 · 13K views
Leetcode - Reshape the Matrix (Python)Timothy H Chang · 5:26 · 7K views
Reshape the Matrix | Leetcode 566 | Live coding sessionCoding Decoded · 8:00 · 4K views
Reshape The Matrix | Array | Matrix | 566 LeetCode | Day 05CodeWithSunny · 9:25 · 2K views
Reshape the Matrix - LeetCode 566 - Java | Division and Modulus ExplainedLeetCode University · 12:27 · 2K views
566. Reshape the Matrix | LEETCODE EASY | MATRIXcode Explainer · 7:18 · 1K views
566. Reshape the Matrix | Leetcode | PythonAbdullah Arshed · 5:24 · 415 views
Daily Leetcode #461: Jul 05, 2021 - 566. Reshape the MatrixProgramming Live with Larry · 7:21 · 412 views
Leetcode 566. Reshape the Matrix (Solution + Explanation)ultcode · 4:02 · 236 views
The problem
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 <= 300
Approach overview
Problem 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.
Approach 1: Flatten and Reconstruct
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.
def matrixReshape(mat, r, c):
m, n = len(mat), len(mat[0])
if m * n != r * c:
return mat
flat = [num for row in mat for num in row]
return [flat[i * c:(i + 1) * c] for i in range(r)]import java.util.Arrays;
public class Solution {
public int[][] matrixReshape(int[][] mat, int r, int c) {
int m = mat.length, n = mat[0].length;
if (m * n != r * c) return mat;
int[][] newMat = new int[r][c];
for (int i = 0; i < m * n; i++) {
newMat[i / c][i % c] = mat[i / n][i % n];
}
return newMat;
}
}#include <vector>
using namespace std;
vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
int m = mat.size(), n = mat[0].size();
if (m * n != r * c) return mat;
vector<vector<int>> newMat(r, vector<int>(c));
for (int i = 0; i < m * n; ++i) {
newMat[i / c][i % c] = mat[i / n][i % n];
}
return newMat;
}var matrixReshape = function(mat, r, c) {
const m = mat.length, n = mat[0].length;
if (m * n !== r * c) return mat;
const flat = [].concat(...mat);
const result = [];
for (let i = 0; i < r; i++) {
result.push(flat.slice(i * c, i * c + c));
}
return result;
};#include <stdio.h>
#include <stdlib.h>
int** matrixReshape(int** mat, int matSize, int* matColSize, int r, int c, int* returnSize, int** returnColumnSizes) {
int m = matSize, n = *matColSize;
if (m * n != r * c) {
*returnSize = m;
*returnColumnSizes = matColSize;
return mat;
}
int** newMat = (int**)malloc(sizeof(int*) * r);
*returnColumnSizes = (int*)malloc(sizeof(int) * r);
for (int i = 0; i < r; i++) {
newMat[i] = (int*)malloc(sizeof(int) * c);
(*returnColumnSizes)[i] = c;
}
*returnSize = r;
for (int i = 0; i < m * n; i++) {
newMat[i / c][i % c] = mat[i / n][i % n];
}
return newMat;
}public class Solution {
public int[][] MatrixReshape(int[][] mat, int r, int c) {
int m = mat.Length, n = mat[0].Length;
if (m * n != r * c) return mat;
int[][] newMat = new int[r][];
for (int i = 0; i < r; i++)
newMat[i] = new int[c];
for (int i = 0; i < m * n; i++) {
newMat[i / c][i % c] = mat[i / n][i % n];
}
return newMat;
}
}This Python code flattens the 2D matrix into a 1D list and then reconstructs the list into a reshaped 2D list if dimensional constraints allow. Otherwise, it returns the original matrix.
Time Complexity: O(m * n).
Space Complexity: O(m * n) due to the intermediate flat list.
Approach 2: Index Mirroring
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.
def matrixReshape(mat, r, c):
m, n = len(mat), len(mat[0])
if m * n != r * c:
return mat
newMat = [[0] * c for _ in range(r)]
for i in range(m):
for j in range(n):
index = i * n + j
newMat[index // c][index % c] = mat[i][j]
return newMatpublic class Solution {
public int[][] matrixReshape(int[][] mat, int r, int c) {
int m = mat.length, n = mat[0].length;
if (m * n != r * c) return mat;
int[][] newMat = new int[r][c];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int index = i * n + j;
newMat[index / c][index % c] = mat[i][j];
}
}
return newMat;
}
}#include <vector>
using namespace std;
vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
int m = mat.size(), n = mat[0].size();
if (m * n != r * c) return mat;
vector<vector<int>> newMat(r, vector<int>(c));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int index = i * n + j;
newMat[index / c][index % c] = mat[i][j];
}
}
return newMat;
}var matrixReshape = function(mat, r, c) {
const m = mat.length, n = mat[0].length;
if (m * n !== r * c) return mat;
const result = Array.from({length: r}, () => Array(c));
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
const index = i * n + j;
result[Math.floor(index / c)][index % c] = mat[i][j];
}
}
return result;
};#include <stdio.h>
#include <stdlib.h>
int** matrixReshape(int** mat, int matSize, int* matColSize, int r, int c, int* returnSize, int** returnColumnSizes) {
int m = matSize, n = *matColSize;
if (m * n != r * c) {
*returnSize = m;
*returnColumnSizes = matColSize;
return mat;
}
int** newMat = (int**)malloc(r * sizeof(int*));
*returnColumnSizes = (int*)malloc(r * sizeof(int));
*returnSize = r;
for (int i = 0; i < r; ++i) {
newMat[i] = (int*)malloc(c * sizeof(int));
(*returnColumnSizes)[i] = c;
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int index = i * n + j;
newMat[index / c][index % c] = mat[i][j];
}
}
return newMat;
}public class Solution {
public int[][] MatrixReshape(int[][] mat, int r, int c) {
int m = mat.Length, n = mat[0].Length;
if (m * n != r * c) return mat;
int[][] newMat = new int[r][];
for (int i = 0; i < r; ++i) {
newMat[i] = new int[c];
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int index = i * n + j;
newMat[index / c][index % c] = mat[i][j];
}
}
return newMat;
}
}Python’s approach involves nested loops iterating the original matrix, directly moving each element to a calculated destination in the new matrix using linear indexing equivalence.
Time Complexity: O(m * n).
Space Complexity: O(r * c) for the resulting reshaped matrix.
Approach 3: Simulation
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).
function matrixReshape(mat: number[][], r: number, c: number): number[][] {
let m = mat.length,
n = mat[0].length;
if (m * n != r * c) return mat;
let ans = Array.from({ length: r }, v => new Array(c).fill(0));
let k = 0;
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
ans[Math.floor(k / c)][k % c] = mat[i][j];
++k;
}
}
return ans;
}func matrixReshape(mat [][]int, r int, c int) [][]int {
m, n := len(mat), len(mat[0])
if m*n != r*c {
return mat
}
ans := make([][]int, r)
for i := range ans {
ans[i] = make([]int, c)
}
for i := 0; i < m*n; i++ {
ans[i/c][i%c] = mat[i/n][i%n]
}
return ans
}impl Solution {
pub fn matrix_reshape(mat: Vec<Vec<i32>>, r: i32, c: i32) -> Vec<Vec<i32>> {
let r = r as usize;
let c = c as usize;
let m = mat.len();
let n = mat[0].len();
if m * n != r * c {
return mat;
}
let mut i = 0;
let mut j = 0;
(0..r)
.into_iter()
.map(|_| {
(0..c)
.into_iter()
.map(|_| {
let res = mat[i][j];
j += 1;
if j == n {
j = 0;
i += 1;
}
res
})
.collect()
})
.collect()
}
}Approach 4: Default Approach
function matrixReshape(mat: number[][], r: number, c: number): number[][] {
const m = mat.length;
const n = mat[0].length;
if (m * n !== r * c) {
return mat;
}
const ans = Array.from({ length: r }, () => new Array(c).fill(0));
for (let i = 0; i < r * c; i++) {
ans[Math.floor(i / c)][i % c] = mat[Math.floor(i / n)][i % n];
}
return ans;
}Complexity comparison
| Approach | Complexity |
|---|---|
| Flatten and Reconstruct | Time Complexity: O(m * n). |
| Index Mirroring | Time Complexity: O(m * n). |
| Simulation | – |
| Default Approach | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Reshape the Matrix easy or hard?
Reshape the Matrix is classified as an Easy problem on LeetCode with an acceptance rate around 65%. The main challenge is recognizing that the reshape is only valid when the total element count stays the same and preserving row-major order during the transformation.
Reshape the Matrix Python/Java solution
Python and Java implementations usually follow either the flatten-and-reconstruct method using a list or array, or the index mirroring technique using arithmetic mapping. Both versions run in O(m*n) time and are straightforward to implement with nested loops or a single linear loop.
How to solve Reshape the Matrix in O(n)?
Treat the matrix as a linear array of length m*n. Iterate over indices from 0 to m*n-1, compute the original coordinates with k/n and k%n, and compute the reshaped coordinates with k/c and k%c. Copy the value directly, producing an O(m*n) time solution with constant extra space.
What is the best approach for Reshape the Matrix?
Index mirroring is typically the best approach. It treats the matrix as a linear sequence and maps each element to its new coordinates using division and modulo operations. The algorithm runs in O(m*n) time and uses O(1) extra space beyond the output matrix.
Is Reshape the Matrix asked at Google/Amazon/Meta?
Reshape-style matrix transformation problems appear in coding interviews at large tech companies including Amazon and Google. They test understanding of matrix traversal, row-major ordering, and index mapping rather than advanced algorithms.
What data structure is used in Reshape the Matrix?
The core data structure is a 2D array (matrix). The solution relies on sequential traversal and sometimes a temporary 1D array for flattening, along with arithmetic index calculations to map elements between matrix shapes.
What is the time complexity of Reshape the Matrix?
Both common solutions run in O(m*n) time because every element of the matrix must be visited exactly once. The flatten-and-reconstruct method also uses O(m*n) extra space, while the index mirroring approach reduces extra space to O(1).