How do you solve Reshape the Matrix on LeetCode?

Reshape the Matrix (LeetCode #566) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Reshaping is only possible if the total number of elements matches the desired dimensions.

What is the brute force solution for Reshape the Matrix?

The brute force approach for Reshape the Matrix is Brute Force, with O(n²) time complexity and O(n) space complexity. The brute force approach involves flattening the 2D matrix into a 1D list and then reshaping it back into the desired dimensions. This is straightforward but not the most efficient way to handle the problem. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Reshape the Matrix?

Reshape the Matrix uses the following concepts: Array, Matrix, Simulation. The recommended patterns to study are: Array, Matrix.

What are the interview tips for Reshape the Matrix?

Always validate input constraints before processing. Explain your thought process clearly, especially when transitioning from brute force to optimal solutions. Practice writing clean and efficient code, as readability is key in interviews.

What are common mistakes when solving Reshape the Matrix?

Failing to check if the reshape is possible before proceeding. Not correctly calculating the original indices when filling the new matrix.

#566

Reshape the Matrix

Easy

ArrayMatrixSimulationArrayMatrix

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(n)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution directly calculates the indices for the reshaped matrix without needing to create an intermediate flattened array. This is more efficient in terms of space.

⚙️

Algorithm

3 steps

1Step 1: Check if the total number of elements in the original matrix equals r * c. If not, return the original matrix.
2Step 2: Create a new 2D list of size r x c.
3Step 3: Fill the new matrix by calculating the original indices using the formula: original_row = index / original_columns, original_col = index % original_columns.

solution.py12 lines

1# Full working Python code
2
3def reshape(mat, r, c):
4    m, n = len(mat), len(mat[0])
5    if m * n != r * c:
6        return mat
7    reshaped = [[0] * c for _ in range(r)]
8    for index in range(r * c):
9        original_row = index // n
10        original_col = index % n
11        reshaped[index // c][index % c] = mat[original_row][original_col]
12    return reshaped

ℹ

Complexity note: The time complexity is O(n) since we only iterate through the elements once to fill the new matrix. The space complexity remains O(n) for the new reshaped matrix.

1Reshaping is only possible if the total number of elements matches the desired dimensions.
2Directly calculating indices can save space and improve efficiency.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.