Skip to main content
Talentd

Reshape the Matrix - Solution & Explanation

EasyArrayMatrixSimulation20 min readAsked at: Amazon, Meta, Google +2
Practice this problem

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:

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.length
  • n == mat[i].length
  • 1 <= m, n <= 100
  • -1000 <= mat[i][j] <= 1000
  • 1 <= 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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n).
Space Complexity: O(r * c) for storing reshaped matrix.

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Approach 4: Default Approach

Code

TypeScript

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Flatten and Reconstruct

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

Time Complexity: O(m * n).
Space Complexity: O(r * c) for storing reshaped matrix.

Simulation—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Flatten and ReconstructO(m*n)O(m*n)Best for readability and quick implementation when extra memory is acceptable
Index MirroringO(m*n)O(1) extra spacePreferred in interviews and memory‑constrained scenarios

Video Solution

LeetCode 566. Reshape the Matrix Solution Explained - Java • Nick White • 14,540 views views

Watch 9 more video solutions →

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).

Ready to solve this problem?

Practice Reshape the Matrix with our built-in code editor and test cases.

Practice on FleetCode
Previous

Convert 1D Array Into 2D Array