Reshape the Matrix

Difficulty: Easy | Acceptance: 64.90% | Paid: No Topics: Array, Matrix, Simulation

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’re given a matrix represented by a 2D array, and two integers r and c representing the number of rows and 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.

• Examples
• Constraints
• Flatten and Reshape
• Direct Index Mapping
• Two Pointer Simulation

Examples

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

Flatten and Reshape

Intuition First flatten the 2D matrix into a 1D array, then construct the new matrix by taking elements from this array in order.

Steps

• Check if reshape is possible by comparing total elements
• Flatten the matrix into a 1D array
• Create the new matrix by filling elements from the 1D array

from typing import List

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
        
        flat = [mat[i][j] for i in range(m) for j in range(n)]
        result = []
        for i in range(r):
            result.append(flat[i * c:(i + 1) * c])
        return result

Complexity

• Time: O(m × n)
• Space: O(m × n)
• Notes: Uses extra space for the flattened array

Direct Index Mapping

Intuition Map each element’s position in the original matrix directly to its position in the reshaped matrix using mathematical formulas.

Steps

• Check if reshape is possible
• For each element at (i, j) in original matrix, calculate its position in new matrix
• Position in new matrix: row = k // c, col = k % c where k = i × n + j

from typing import List

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
        
        result = [[0] * c for _ in range(r)]
        for i in range(m):
            for j in range(n):
                k = i * n + j
                result[k // c][k % c] = mat[i][j]
        return result

Complexity

• Time: O(m × n)
• Space: O(r × c)
• Notes: More space-efficient as it doesn’t use a separate flattened array

Two Pointer Simulation

Intuition Simulate the reshape process by iterating through both matrices simultaneously using two pointers.

Steps

• Check if reshape is possible
• Use two pointers to track positions in original and new matrices
• Copy elements one by one from original to new matrix

from typing import List

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
        
        result = [[0] * c for _ in range(r)]
        row, col = 0, 0
        
        for i in range(m):
            for j in range(n):
                result[row][col] = mat[i][j]
                col += 1
                if col == c:
                    col = 0
                    row += 1
        return result

Complexity

• Time: O(m × n)
• Space: O(r × c)
• Notes: Intuitive approach that simulates the actual reshape process