Reshape the Matrix - Video Solutions

Problem Overview: You receive an m x n matrix and two integers r and c. The task is to reshape the matrix into an r x c matrix while preserving the original row‑major order of elements. If the reshape is impossible (because m * n != r * c), return the original matrix unchanged.

Approach 1: Flatten and Reconstruct (O(m*n) time, O(m*n) space)

The direct strategy is to first flatten the matrix into a 1D list, then rebuild the result matrix with the new dimensions. Iterate through every element of the input matrix row by row and append it to a temporary array. Once flattened, iterate through the array again and fill the new r x c matrix sequentially. This preserves row‑major order automatically. The approach is simple and readable, making it a good first implementation when working with array transformations or quick matrix restructuring tasks. The tradeoff is extra memory for the flattened array.

Approach 2: Index Mirroring (O(m*n) time, O(1) extra space)

A more efficient method avoids creating a temporary array. Treat the matrix as if it were a flattened sequence of length m*n. For each linear index k, compute its original position and its reshaped position using arithmetic. The original coordinates are row = k / n and col = k % n. The new coordinates become newRow = k / c and newCol = k % c. Copy the value directly from the original matrix to the reshaped matrix using these calculated indices. This technique mirrors indices between two matrix layouts and is common in problems involving matrix traversal and coordinate mapping. It achieves the same result while using only the output matrix as additional memory.

Recommended for interviews: Interviewers expect the index mirroring approach because it demonstrates a clear understanding of row‑major ordering and index mapping in a simulation style problem. Starting with the flatten‑and‑reconstruct idea shows you recognize the ordering requirement. Transitioning to index mirroring proves you can remove unnecessary memory and reason about element positions mathematically.