LeetCode 566 - Reshape the Matrix

Difficulty: 🟢 Easy
Topics: Array, Matrix, Simulation

Solution

Problem Understanding

The problem is asking us to take an existing m x n matrix and "reshape" it into a new matrix with r rows and c columns. Reshaping means rearranging the elements in the matrix in row-major order (left-to-right, top-to-bottom) without changing the order of the elements themselves. If the number of elements in the original matrix (m * n) does not match the number of elements in the target matrix (r * c), the reshape operation is invalid, and we must return the original matrix unchanged.

The input is a 2D list (or slice in Go) mat representing the original matrix, and integers r and c representing the target dimensions. The output is a 2D list of integers (or 2D slice in Go) representing either the reshaped matrix or the original if reshaping is impossible.

Constraints tell us that the matrix can have up to 100 rows and 100 columns, and the values range from -1000 to 1000. The target dimensions can be as large as 300, which means we must check the total number of elements carefully to avoid invalid reshapes. Edge cases include situations where r or c are larger than the total number of elements, or where r * c equals m * n but one of the dimensions is 1 (flattening into a single row or column).

Approaches

The most straightforward method is the brute-force approach. In this approach, we flatten the original matrix into a single list, then rebuild a new matrix row by row using slices of size c. This guarantees correctness because it preserves row-traversing order, but it uses extra space proportional to the total number of elements.

A more optimal solution avoids creating a separate flattened list. By using integer division and modulo arithmetic, we can calculate the position in the reshaped matrix directly from the index in the original matrix. The key insight is that for element index i in a flattened view of the original matrix, its position in the new matrix is (i // c, i % c). This eliminates the extra space needed for flattening and produces the result in a single pass.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m * n)	O(m * n)	Flatten the matrix into a list then reconstruct the new matrix.
Optimal	O(m * n)	O(1) extra	Map each element's index from original to reshaped matrix directly, no extra list needed.

Algorithm Walkthrough

Determine the dimensions m and n of the original matrix by checking its length and the length of the first row.
If the product m * n is not equal to r * c, return the original matrix because reshaping is impossible.
Initialize an empty matrix reshaped with r rows and c columns.
Iterate over all elements of the original matrix using nested loops or a single counter i.
For each element, compute its position in the reshaped matrix: the row is i // c and the column is i % c.
Place the element at the calculated position in the reshaped matrix.
After all elements are placed, return the reshaped matrix.

Why it works: The algorithm works because the flattening order of the original matrix matches row-traversing order. By using division and modulo operations, the mapping from the linear index to the 2D reshaped index preserves this order without any additional storage.

Python Solution

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

The code first calculates the original matrix dimensions. If reshaping is impossible, it returns the original matrix. Then it constructs the reshaped matrix and uses a single loop over all elements, mapping each index in the flattened view to the correct position in both the original and reshaped matrices using integer division and modulo arithmetic.

Go Solution

func matrixReshape(mat [][]int, r int, c int) [][]int {
    m, n := len(mat), len(mat[0])
    if m*n != r*c {
        return mat
    }
    
    reshaped := make([][]int, r)
    for i := range reshaped {
        reshaped[i] = make([]int, c)
    }
    
    for i := 0; i < m*n; i++ {
        reshaped[i/c][i%c] = mat[i/n][i%n]
    }
    
    return reshaped
}

In Go, we explicitly initialize each row of the reshaped slice. The logic of mapping indices is identical to Python, with integer division and modulo handling the position mapping. The difference lies in slice allocation and type declarations.

Worked Examples

Example 1

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

Iteration through elements:

i	mat[i//2][i%2]	reshaped[i//4][i%4]
0	1	1
1	2	2
2	3	3
3	4	4

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

Example 2

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

Since 2*2 != 2*4, reshaping is impossible. Output: [[1,2],[3,4]]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m * n)	Each element is visited once to place it in the reshaped matrix.
Space	O(1) extra	No additional data structures proportional to input size are used; reshaped matrix is output space.

The linear scan ensures we only visit each element once, and the index mapping eliminates the need for temporary flattening.

Test Cases

# Provided examples
assert Solution().matrixReshape([[1,2],[3,4]], 1, 4) == [[1,2,3,4]]  # reshape into 1 row
assert Solution().matrixReshape([[1,2],[3,4]], 2, 4) == [[1,2],[3,4]]  # invalid reshape

# Edge cases
assert Solution().matrixReshape([[1]], 1, 1) == [[1]]  # 1x1 matrix, same size
assert Solution().matrixReshape([[1,2,3]], 3, 1) == [[1],[2],[3]]  # flatten 1 row to 3 rows
assert Solution().matrixReshape([[1],[2],[3]], 1, 3) == [[1,2,3]]  # flatten 3 rows to 1 row
assert Solution().matrixReshape([[1,2],[3,4]], 4, 1) == [[1],[2],[3],[4]]  # 2x2 to 4x1
assert Solution().matrixReshape([[1,2],[3,4]], 1, 5) == [[1,2],[3,4]]  # impossible reshape

Test	Why
1x1 matrix	Minimal input size
1 row to multiple rows	Tests row-to-column flattening
Multiple rows to 1 row	Tests column-to-row flattening
2x2 to 4x1	Reshape to a column vector
Impossible reshape	Confirms correct handling of invalid reshapes

Edge Cases

Single-element matrix: A matrix with only one element should be handled correctly regardless of target dimensions. Since m * n equals 1, reshaping to 1x1 works, but anything else should return the original matrix.

Reshape to a single row or column: Flattening a matrix to a single row or a single column can reveal off-by-one errors in index calculations. Using integer division and modulo ensures that both i // c and i % c map correctly.

Impossible reshape: When r * c does not equal m * n, it is easy to forget to check this condition and attempt to build an invalid matrix. Returning the original matrix immediately avoids unnecessary computations and errors.