1. Reshape the Matrix (LeetCode)
Model answer
The task
Rearrange a matrix’s elements in row-major order into a matrix with the requested dimensions. If the new dimensions cannot hold exactly the same number of elements, return the original matrix unchanged.
Key idea
Reshaping changes where elements are placed, not their order. The element at flat index k belongs at row k // c and column k % c in the reshaped matrix.
Approach
- Read the original row and column counts.
- If the requested shape has a different total number of cells, return the original matrix.
- Create an empty result with the requested number of rows.
- Visit source elements in row-major order, tracking their flat index.
- Place each element at the corresponding destination row and column.
from typing import List
class Solution:
def matrixReshape(
self, mat: List[List[int]], r: int, c: int
) -> List[List[int]]:
# Handle an empty matrix safely.
if not mat or not mat[0]:
return mat if r * c == 0 else mat
rows, cols = len(mat), len(mat[0])
# A reshape is possible only if the element counts match.
if rows * cols != r * c:
return mat
result = [[0] * c for _ in range(r)]
# Map each source element's row-major index to its new position.
for i in range(rows):
for j in range(cols):
index = i * cols + j
result[index // c][index % c] = mat[i][j]
return result
Complexity:
- Time: O(mn), where
m × nis the original matrix size; each element is visited once. - Space: O(mn) for the reshaped result.
Common follow-ups
- What if the requested dimensions do not match the element count? Return the original matrix without changing it.
- Can the reshape be done without allocating another matrix? Only if modifying storage in place is allowed; the mapping is more involved.
- How would you support a stream of elements? Buffer elements until a full destination row is available, then emit that row.