Reshape Matrix LeetCode 566 Guide

LeetCode 566 Reshape the Matrix asks you to convert an m x n matrix mat into a new r x c matrix. The elements must be filled in the same row-traversal order as they appear in the original — left to right, top to bottom — so the relative order of all elements is preserved.

If m * n does not equal r * c, the reshape is impossible and you must return the original matrix mat unchanged. This is the single edge case to handle before doing any real work. When the total element count matches, a valid reshape always exists.

The problem is a classic index mapping exercise. Understanding how to move between 2D coordinates and a flat linear index is the core skill tested, and it applies to many other matrix manipulation problems.

Every element at position (i, j) in an m x n matrix has a unique linear index: index = i * n + j. This maps the 2D grid to a flat sequence numbered 0 through m*n-1, following the same row-major order that the problem requires.

Given a linear index and the new column count c, the new row and column are: newRow = index // c and newCol = index % c. This is integer division and modulo — often called divmod. Together, these two formulas connect the original 2D position to the reshaped 2D position without ever constructing an intermediate flat array.

The relationship is bijective when m*n == r*c: every index maps to exactly one source cell and exactly one destination cell. This is why the check comes first — without it the mapping would produce out-of-bounds indices.

The algorithm is a straightforward nested loop over the original matrix. For each cell (i, j), compute its linear index, then derive the destination row and column in the new matrix using divmod. Write the value and continue.

Because each element is visited exactly once and each write goes to a unique destination cell, the algorithm is correct for any valid (r, c) pair. The output matrix is filled completely after one pass through the input.

Time complexity is O(m*n) — one pass over every element. Space complexity is O(1) extra beyond the output matrix, which the problem expects as the return value and does not count against the space budget.

Python allows a compact one-liner using list comprehension and itertools.chain: flat = list(itertools.chain.from_iterable(mat)); return [flat[i*c:(i+1)*c] for i in range(r)]. This is Pythonic and readable but does allocate an intermediate flat list of size m*n.

An alternative without itertools: flat = [mat[i][j] for i in range(m) for j in range(n)]. The slicing approach [flat[i*c:(i+1)*c] for i in range(r)] then rebuilds the rows. Both variants are O(m*n) time and O(m*n) extra space for the flat list.

The divmod nested-loop approach avoids the extra flat list entirely and writes directly to the result matrix, making it more memory-efficient in practice even though the asymptotic space class is the same since the output is O(m*n) regardless.

Consider mat = [[1, 2], [3, 4]], r = 1, c = 4. Check: m*n = 2*2 = 4, r*c = 1*4 = 4 — equal, so reshape is valid. Create result = [[0, 0, 0, 0]].

Iterate: (i=0, j=0): index=0, result[0//4][0%4] = result[0][0] = 1. (i=0, j=1): index=1, result[0][1] = 2. (i=1, j=0): index=2, result[0][2] = 3. (i=1, j=1): index=3, result[0][3] = 4.

Result = [[1, 2, 3, 4]]. All four elements appear in row-traversal order in a single row of four columns, which is exactly what r=1, c=4 specifies.

Python solution: def matrixReshape(mat, r, c): 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): idx = i*n+j; result[idx//c][idx%c] = mat[i][j]; return result. The nested loop with divmod is about 8 lines and handles all cases cleanly.

Java solution: if (m*n != r*c) return mat; int[][] result = new int[r][c]; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) { int idx = i*n+j; result[idx/c][idx%c] = mat[i][j]; } return result. Java uses / for integer division and % for modulo, so the arithmetic is identical.

Time complexity: O(m*n) — every element is read once and written once. Space complexity: O(1) extra — the output matrix is the return value and does not count as extra space. No intermediate data structures are used beyond the result array.

Rotate Image (LeetCode 48) transforms a matrix in-place by rotating 90 degrees clockwise. Like Reshape, it requires careful index mapping — specifically transposing and then reversing rows. Both problems build intuition for thinking in 2D coordinates and their arithmetic relationships.

Spiral Matrix (LeetCode 54) and Spiral Matrix II (LeetCode 59) traverse or fill a matrix in spiral order. These require tracking direction and boundaries rather than divmod, but the underlying theme of mapping a linear traversal order to 2D positions is shared with Reshape.

Set Matrix Zeroes (LeetCode 73) and the broader matrix transformation family — including transposing, flipping, and rotating — all reward the same index-arithmetic thinking. Mastering the 1D-to-2D divmod mapping in Reshape provides a reusable mental model for the entire matrix problem family.