128. Matrix Reshape

Why this mechanism works

Reshaping changes coordinates but not the flattened position of an element. A flat position k maps to new coordinates (k//c,k%c). Verify equal element counts before copying so every source position has a destination and no destination is missing.

State and boundaries

index counts consumed values in row-major order. output uses the requested dimensions; input remains unchanged.

Protocol

1. Compare old and new element counts.
2. Return the original object if incompatible.
3. Allocate independent output rows.
4. Walk original values and map each flat index to its new coordinates.
5. Return output.

Visualization

[[1,2],[3,4]] -> flat positions 0,1,2,3
reshape 1x4 -> [[1,2,3,4]]
reshape 3x2 rejected: element counts differ

Python implementation

def reshape_matrix(matrix, r, c):
    rows = len(matrix)
    cols = len(matrix[0]) if rows else 0
    if rows * cols != r * c:
        return matrix
    output = [[0] * c for _ in range(r)]
    index = 0
    for row in matrix:
        for value in row:
            output[index // c][index % c] = value
            index += 1
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 reshape_matrix: rows = len(matrix)
matrix=[[1, 2], [3, 4]]; r=1; c=4; rows=2

L3 reshape_matrix: cols = len(matrix[0]) if rows else 0
matrix=[[1, 2], [3, 4]]; r=1; c=4; rows=2; cols=2

L6 reshape_matrix: output = [[0] * c for _ in range(r)]
matrix=[[1, 2], [3, 4]]; r=1; c=4; rows=2; cols=2; _=0

L6 reshape_matrix: output = [[0] * c for _ in range(r)]
matrix=[[1, 2], [3, 4]]; r=1; c=4; rows=2; cols=2; output=[[0, 0, 0, 0]]

L7 reshape_matrix: index = 0
matrix=[[1, 2], [3, 4]]; r=1; c=4; rows=2; cols=2; output=[[0, 0, 0, 0]]; index=0

L8 reshape_matrix: for row in matrix:
matrix=[[1, 2], [3, 4]]; r=1; c=4; rows=2; cols=2; output=[[0, 0, 0, 0]]; index=0; row=[1, 2]

L9 reshape_matrix: for value in row:
matrix=[[1, 2], [3, 4]]; r=1; c=4; rows=2; cols=2; output=[[0, 0, 0, 0]]; index=0; row=[1, 2]; value=1

L10 reshape_matrix: output[index // c][index % c] = value
matrix=[[1, 2], [3, 4]]; r=1; c=4; rows=2; cols=2; output=[[1, 0, 0, 0]]; index=0; row=[1, 2]; value=1

... 7 intermediate state changes omitted ...

L11 reshape_matrix: index += 1
matrix=[[1, 2], [3, 4]]; r=1; c=4; rows=2; cols=2; output=[[1, 2, 3, 0]]; index=3; row=[3, 4]; value=3

L9 reshape_matrix: for value in row:
matrix=[[1, 2], [3, 4]]; r=1; c=4; rows=2; cols=2; output=[[1, 2, 3, 0]]; index=3; row=[3, 4]; value=4

L10 reshape_matrix: output[index // c][index % c] = value
matrix=[[1, 2], [3, 4]]; r=1; c=4; rows=2; cols=2; output=[[1, 2, 3, 4]]; index=3; row=[3, 4]; value=4

L11 reshape_matrix: index += 1
matrix=[[1, 2], [3, 4]]; r=1; c=4; rows=2; cols=2; output=[[1, 2, 3, 4]]; index=4; row=[3, 4]; value=4

L2 reshape_matrix: rows = len(matrix)
matrix=[[1, 2], [3, 4]]; r=3; c=2; rows=2

L3 reshape_matrix: cols = len(matrix[0]) if rows else 0
matrix=[[1, 2], [3, 4]]; r=3; c=2; rows=2; cols=2

Why the solution is correct

Equal element counts make the row-major index mapping a bijection between source and destination cells. Copying in that order therefore preserves the flattened sequence exactly. An incompatible request is rejected before mutation or copying.

Time and space

O(N) time and O(N+r) returned storage for N values and r output row objects; incompatible requests take O(1) after dimensions are read.

Common mistakes

Reshaping by rows alone may reorder values. Repeated-list allocation aliases output rows. A zero target column count is safe only when no value needs mapping.

Reasoning card

Transfer exercise

Return a lazy view based on index arithmetic and discuss how later mutations of the original matrix should be reflected.