Reshape the Matrix — Solution

Problem

Given an m×n matrix and a target shape of r rows and c columns, return a new matrix containing all the same elements in row-major (left-to-right, top-to-bottom) order. If the total element count doesn't match (m×n ≠ r×c), return the original matrix unchanged.

• Input: mat = [[1,2],[3,4]], r = 1, c = 4
• Output: [[1,2,3,4]]
• Explanation: The four elements are read left-to-right, top-to-bottom from the 2×2 source and placed into a single 1×4 row.

Counter-example: mat = [[1,2],[3,4]], r = 2, c = 4 has no valid reshape because 2×2 = 4 ≠ 2×4 = 8; return the original matrix.

Intuition

Every element occupies a unique position k in a flat, row-major sequence regardless of the matrix's shape. Knowing k, the source coordinates are (k // n, k % n) and the destination coordinates are (k // c, k % c). A single loop over all m×n indices remaps each element without ever building an intermediate 1D array.

Solution — Index Arithmetic

Check feasibility first, then use integer division and modulo to map each flat index to its source and destination coordinates.

1. Compute m = len(mat) and n = len(mat[0]).
2. If m * n != r * c, return mat immediately — reshape would change the element count.
3. Allocate the result grid of size r × c.
4. For each flat index k from 0 to m*n − 1, read from mat[k // n][k % n] and write to result[k // c][k % c].
5. Return the result.

1def matrixReshape(mat: list[list[int]], r: int, c: int) -> list[list[int]]:
2    m, n = len(mat), len(mat[0])
3    if m * n != r * c:  # reshape would change element count, which is illegal
4        return mat
5
6    result = [[0] * c for _ in range(r)]
7    for k in range(m * n):
8        result[k // c][k % c] = mat[k // n][k % n]
9    return result

Time: O(m×n) — each element is visited exactly once.
Space: O(r×c) — the output matrix is the only allocation beyond input.

Complexity Summary

Common Mistakes

• Skipping the feasibility check — attempting the reshape when m*n != r*c causes an index out-of-bounds error when writing into result; the check must come first.
• Mixing up n and c in the source formula — the source read uses k // n and k % n (divided by the original column count), while the destination write uses k // c and k % c (divided by the target column count); using c for both silently reads from wrong source cells.
• Returning None or [] on failure instead of mat — the problem contract requires returning the original matrix when reshape is impossible, not an empty or null result.
• Building an intermediate flat list — flattening to a 1D array first and then rebuilding the result doubles the memory allocation unnecessarily; the index formula eliminates that intermediate step.

Related Problems

• Search a 2D Matrix — also exploits row-major ordering to treat a 2D matrix as a virtual flat sorted array using the same index arithmetic
• Spiral Matrix — traverses a 2D matrix in non-row-major order, requiring careful directional index tracking
• Rotate Image — transforms a square matrix in-place by remapping (row, col) to (col, m−1−row), a harder in-place variant of 2D index manipulation
• Set Matrix Zeroes — iterates a 2D matrix and modifies it based on discovered indices, requiring careful ordering to avoid overwriting sentinel values
• Matrix Diagonal Sum — uses index arithmetic to selectively access specific positions in a 2D grid without a full traversal