Reshape the Matrix: Row-Major Index Mapping

You are given an m x n matrix and two integers r and c. Your job is to reshape the matrix into a new one with r rows and c columns, filling it with all the original elements in the same row-by-row reading order. If the reshape is impossible (the total number of elements does not match), return the original matrix unchanged.

This is LeetCode 566: Reshape the Matrix, and it is a clean introduction to how computers store 2D data in memory. The key idea is row-major index mapping, a pattern that shows up in dozens of matrix problems.

The problem

Given mat with dimensions m x n and target dimensions r x c:

• If m * n != r * c, the reshape is impossible. Return mat as-is.
• Otherwise, read every element from mat in row-major order (left to right, top to bottom) and place them into a new r x c matrix in the same order.

Example: mat = [[1,2,3],[4,5,6]], r = 3, c = 2 produces [[1,2],[3,4],[5,6]]. You read 1, 2, 3, 4, 5, 6 from the original and fill them into three rows of two.

The approach

The trick is to think of both matrices as flat 1D arrays. Every element has a linear index k ranging from 0 to m * n - 1. For any linear index k:

• Original position: row = k // n, column = k % n (where n is the number of columns in the original matrix).
• New position: row = k // c, column = k % c (where c is the number of columns in the reshaped matrix).

You do not need to actually flatten anything. You iterate k from 0 to m * n - 1, read from the original using the first pair of formulas, and write to the result using the second pair. That is the entire algorithm.

The validity check is simple: if the total number of elements in the original (m * n) does not equal the total in the target (r * c), you cannot reshape. Return the original matrix immediately.

The 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 k in range(m * n):
        result[k // c][k % c] = mat[k // n][k % n]

    return result

The function first checks whether reshaping is possible. If the element counts do not match, it returns the original. Otherwise, it creates a new r x c matrix filled with zeros and iterates through every linear index. For each k, it reads from the original at (k // n, k % n) and writes to the result at (k // c, k % c).

No flattening, no intermediate list, no extra passes. One loop does everything.

Step-by-step walkthrough

Let's trace through mat = [[1,2],[3,4]] with r = 1 and c = 4.

The valid case goes through four iterations, one per element. The invalid case never enters the loop because the element counts do not match, so the original matrix is returned immediately.

Complexity analysis

Time: you visit every element exactly once. The loop runs m * n iterations, each doing O(1) work (two integer divisions, two modulo operations, one read, one write).

Space: the result matrix holds r * c = m * n elements. That is the required output, not extra bookkeeping. If you count only auxiliary space beyond the output, it is O(1).

The building blocks

Row-major index mapping

The core pattern here is converting between a linear index and 2D coordinates. Given a matrix with cols columns:

row = k // cols
col = k % cols

This pair of formulas lets you treat any 2D matrix as a 1D array and vice versa. You will see this exact pattern in:

• Search a 2D Matrix (LeetCode 74): run binary search on a virtually flattened matrix using mid // cols and mid % cols to read values.
• Spiral Matrix (LeetCode 54): while the traversal logic differs, understanding row-major layout helps you reason about which cells have been visited.
• Set Matrix Zeroes (LeetCode 73): marking rows and columns by index requires fluency with how indices map to positions.

The conversion works in reverse too. If you have a position (i, j) in a matrix with cols columns, the linear index is i * cols + j. This round-trip between 1D and 2D is one of the most reusable micro-patterns in matrix problems.

Edge cases

Before submitting, make sure your solution handles these:

• Same dimensions: r = m and c = n. The element count matches, and the loop copies every element to the same position. The result is identical to the input.
• Single row: reshaping a 2x3 matrix into 1x6. All elements end up in one row. The formula still works because k // 6 is always 0 for k in range 0 to 5.
• Single column: reshaping into an n x 1 matrix. Each element gets its own row. k // 1 = k and k % 1 = 0, so each element lands at (k, 0).
• Invalid reshape: m * n != r * c. The function returns the original matrix immediately. No allocation, no copying.
• 1x1 matrix: [[5]] reshaped to 1x1 is [[5]]. One iteration, one element.

From understanding to recall

You have read through the solution and understand the index mapping. The formula k // c for the row and k % c for the column is not hard to derive. But under interview pressure, even simple things get second-guessed. Did you divide by rows or columns? Is it the original column count or the target column count?

Spaced repetition removes that hesitation. You write the reshape function from scratch today, again in two days, again in five. After a few reps, the index mapping flows automatically. You see a matrix reshaping problem and your hands type result[k // c][k % c] = mat[k // n][k % n] without your brain needing to rederive anything.

Row-major index mapping is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning these individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Spiral Matrix - Layer-by-layer traversal of a matrix, another essential 2D pattern
• Rotate Image - In-place matrix rotation using transpose and reverse, a different way to rearrange matrix elements
• Search a 2D Matrix - Binary search on a virtually flattened matrix, the same row-major index mapping applied to search

CodeBricks breaks Reshape the Matrix into its row-major index mapping building block and drills it independently with spaced repetition. You type the linear-index-to-coordinates conversion from scratch until it is automatic. When a matrix reshaping or indexing problem shows up in your interview, you do not think about it. You just write it.