#566

Easy

LeetCode Problem Workspace

Reshape the Matrix

Reshape the Matrix involves transforming a 2D matrix into a new matrix with the same elements in row-major order, following specific dimensions.

array matrix simulation

Problem Statement

You are given an m x n matrix and two integers r and c, which represent the number of rows and columns of the reshaped matrix. Your task is to reshape the matrix into a new matrix of the specified dimensions, while maintaining the original data in the same row-major order.

If it is impossible to reshape the matrix, return the original matrix. The solution requires you to manage the mapping between the original 2D indices and the new reshaped matrix dimensions, ensuring that no data is lost or misplaced.

Examples

Example 1

Input: mat = [[1,2],[3,4]], r = 1, c = 4

Output: [[1,2,3,4]]

Example details omitted.

Example 2

Input: mat = [[1,2],[3,4]], r = 2, c = 4

Output: [[1,2],[3,4]]

Example details omitted.

Constraints

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

Solution Approach

Flatten the Matrix

Convert the matrix into a 1D array by traversing it row by row. This helps in simplifying the reshaping process, as you can map elements directly from this array to the new reshaped matrix.

Check for Valid Reshape

Before proceeding with reshaping, ensure that the total number of elements in the original matrix matches the product of r and c. If they don’t match, return the original matrix.

Rebuild the Matrix

Using the flattened array, reconstruct the new matrix row by row, ensuring that each row has exactly c elements. This step completes the reshaping process while keeping the data in row-major order.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(m * n) for flattening the matrix and rebuilding it, where m is the number of rows and n is the number of columns. The space complexity is O(m * n) for storing the flattened 1D array and the reshaped matrix.

What Interviewers Usually Probe

The candidate should recognize the importance of handling array indexing correctly when reshaping the matrix.
Look for the candidate's ability to validate the reshaping dimensions before proceeding.
Expect the candidate to explain the time and space complexity of their approach.

Common Pitfalls or Variants

Common pitfalls

Failing to check if the reshape dimensions are valid before attempting to reshape.
Incorrectly mapping the 1D array back into a 2D matrix, potentially losing elements.
Not considering edge cases where the reshape operation is impossible.

Follow-up variants

Given a 2D matrix, reshape it to match any specified dimensions, with varying boundary conditions (e.g., non-matching dimensions).
Reshape a matrix and also transpose it simultaneously.
Implement an in-place reshape operation that modifies the original matrix.

FAQ

What is the key concept behind reshaping a matrix in this problem?

The key concept is converting the matrix from a 2D structure into a 1D array, and then mapping this 1D array back into the new reshaped matrix while maintaining the original row-major order.

How can I handle the case when reshaping is not possible?

If reshaping is not possible (i.e., the total number of elements does not match the product of the desired dimensions), you should return the original matrix.

What is the time complexity of reshaping the matrix?

The time complexity is O(m * n), where m is the number of rows and n is the number of columns in the matrix, due to the need to traverse all elements for reshaping.

Can the matrix be reshaped in-place?

No, reshaping the matrix requires creating a new matrix since the dimensions change. In-place reshaping is not possible for this problem.

What is the role of the primary pattern 'Array plus Matrix' in this problem?

The 'Array plus Matrix' pattern helps in understanding how to flatten a 2D matrix into a 1D array and then rebuild it into a new matrix, ensuring proper data order and efficient memory use.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

class Solution:
    def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        if m * n != r * c:
            return mat
        ans = [[0] * c for _ in range(r)]
        for i in range(m * n):
            ans[i // c][i % c] = mat[i // n][i % n]
        return ans

Solution 2

#### TypeScript

1

2

3

4

5

6

7

8

9

class Solution:
    def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        if m * n != r * c:
            return mat
        ans = [[0] * c for _ in range(r)]
        for i in range(m * n):
            ans[i // c][i % c] = mat[i // n][i % n]
        return ans

Continue Practicing

#498 diagonal traverse #749 contain virus #832 flipping an image