Problem Description

You need to implement a function that reshapes a matrix, similar to MATLAB's reshape function. Given an m x n matrix mat and two integers r and c, you should reshape the matrix into a new matrix with r rows and c columns.

The reshaping process should follow these rules:

1. Element Order Preservation: All elements from the original matrix should be read in row-traversing order (left to right, top to bottom) and placed into the new matrix in the same row-traversing order.

2. Validity Check: The reshape operation is only valid if the total number of elements remains the same. That means m * n must equal r * c. If this condition is not met, return the original matrix unchanged.

3. Output: If reshaping is possible, return the new reshaped matrix with dimensions r x c. Otherwise, return the original matrix.

For example, if you have a 2x2 matrix [[1,2],[3,4]] and want to reshape it to 1x4, the elements would be read as 1, 2, 3, 4 and placed into the new matrix as [[1,2,3,4]].

The solution uses index mapping to efficiently transfer elements from the original matrix to the reshaped matrix. For any linear index i (from 0 to m*n-1), the element at position [i // n][i % n] in the original matrix is placed at position [i // c][i % c] in the new matrix.

Intuition

The key insight is that reshaping a matrix is essentially about reinterpreting how we group the same sequence of elements. When we read a 2D matrix in row-major order, we get a linear sequence of elements. This same sequence can then be regrouped into different dimensions.

Think of the matrix elements as beads on a string. When we flatten a 2D matrix by reading row by row, we get all elements in a single line. Now we can take this same string of beads and arrange them into a new rectangular pattern with different dimensions.

The mathematical trick here is using index conversion. Any element in a 2D matrix can be mapped to a unique position in a 1D array and vice versa. For a matrix with n columns:

• A 2D position (row, col) maps to 1D index: row * n + col
• A 1D index i maps back to 2D: row = i // n, col = i % n

Since we're transforming from one 2D shape to another, we can use a single loop counter i from 0 to m*n-1 to represent the position in the flattened sequence. Then:

• To read from the original matrix with n columns: position is [i // n][i % n]
• To write to the new matrix with c columns: position is [i // c][i % c]

This avoids explicitly flattening the matrix into a 1D array and then reshaping it, making the solution more efficient with direct element-to-element mapping.

The prerequisite check m * n != r * c ensures we have the exact same number of elements to work with - you can't create more elements or lose elements during reshaping, just rearrange them.

Solution Approach

The implementation follows a simulation approach where we directly map elements from the original matrix to their new positions in the reshaped matrix.

Step 1: Validate the Reshape Operation

First, we extract the dimensions of the original matrix:

• m = len(mat) - number of rows
• n = len(mat[0]) - number of columns

Then we check if reshaping is valid by comparing the total number of elements:

if m * n != r * c:
    return mat

If the total elements don't match, we cannot reshape and return the original matrix.

Step 2: Create the Result Matrix

We initialize a new matrix with the desired dimensions:

ans = [[0] * c for _ in range(r)]

This creates r rows, each containing c columns, all initialized to 0.

Step 3: Transfer Elements Using Index Mapping

The core of the algorithm uses a single loop to iterate through all m * n elements:

for i in range(m * n):
    ans[i // c][i % c] = mat[i // n][i % n]

For each linear index i:

• Reading from original matrix: The position [i // n][i % n] gives us the element at the i-th position when reading the original matrix in row-major order

  • i // n gives the row index (how many complete rows of size n we've passed)
  • i % n gives the column index (position within the current row)

• Writing to new matrix: The position [i // c][i % c] determines where this element should go in the reshaped matrix

  • i // c gives the row index in the new matrix (how many complete rows of size c we've filled)
  • i % c gives the column index in the new matrix (position within the current row)

Step 4: Return the Result

After all elements have been transferred, we return the reshaped matrix ans.

The time complexity is O(m * n) as we visit each element exactly once. The space complexity is O(r * c) for the new matrix, which equals O(m * n) since r * c = m * n for valid reshapes.

Example Walkthrough

Let's walk through reshaping a 2×3 matrix into a 3×2 matrix.

Given:

• Original matrix mat = [[1,2,3],[4,5,6]] with dimensions m=2, n=3
• Target dimensions: r=3, c=2

Step 1: Validate

• Total elements in original: 2 × 3 = 6
• Total elements in target: 3 × 2 = 6
• Since they match, reshaping is valid ✓

Step 2: Create result matrix

ans = [[0,0],
       [0,0],
       [0,0]]

Step 3: Transfer elements using index mapping

For each linear index i from 0 to 5:

• i = 0:

  • Read from mat[0//3][0%3] = mat[0][0] = 1
  • Write to ans[0//2][0%2] = ans[0][0]
  • Result: ans[0][0] = 1

• i = 1:

  • Read from mat[1//3][1%3] = mat[0][1] = 2
  • Write to ans[1//2][1%2] = ans[0][1]
  • Result: ans[0][1] = 2

• i = 2:

  • Read from mat[2//3][2%3] = mat[0][2] = 3
  • Write to ans[2//2][2%2] = ans[1][0]
  • Result: ans[1][0] = 3

• i = 3:

  • Read from mat[3//3][3%3] = mat[1][0] = 4
  • Write to ans[3//2][3%2] = ans[1][1]
  • Result: ans[1][1] = 4

• i = 4:

  • Read from mat[4//3][4%3] = mat[1][1] = 5
  • Write to ans[4//2][4%2] = ans[2][0]
  • Result: ans[2][0] = 5

• i = 5:

  • Read from mat[5//3][5%3] = mat[1][2] = 6
  • Write to ans[5//2][5%2] = ans[2][1]
  • Result: ans[2][1] = 6

Final Result:

ans = [[1,2],
       [3,4],
       [5,6]]

The elements 1,2,3,4,5,6 were read in row-major order from the original 2×3 matrix and placed into the new 3×2 matrix maintaining the same sequential order.

Solution Implementation

Time and Space Complexity

The time complexity is O(m × n), where m and n are the number of rows and columns of the original matrix, respectively. This is because the algorithm iterates through all m × n elements exactly once in the for loop, performing constant-time operations for each element (calculating indices and assigning values).

The space complexity is O(r × c) for the output matrix ans. However, if we exclude the space required for the output (as it's necessary for returning the result), the space complexity is O(1). This means the algorithm uses only a constant amount of extra space beyond the input and output, with just a few variables (m, n, i) that don't scale with the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Index Calculation for Source Matrix

A frequent mistake is using the wrong divisor when calculating the source indices. Developers often mistakenly use the target dimensions instead of the source dimensions:

Wrong:

# Using 'c' (target columns) instead of 'cols' (source columns)
source_row = index // c  # Incorrect!
source_col = index % c   # Incorrect!

Correct:

source_row = index // cols  # Use original column count
source_col = index % cols   # Use original column count

This error occurs because it's easy to confuse which dimension belongs to which matrix when working with multiple coordinate systems simultaneously.

2. Empty Matrix Handling

The code assumes mat[0] exists to get the column count. If an empty matrix is passed, this will cause an IndexError:

Problem:

cols = len(mat[0])  # Fails if mat is empty []

Solution:

if not mat or not mat[0]:
    return mat
rows, cols = len(mat), len(mat[0])

3. Using Wrong Variables in the Loop

When using the compact one-liner approach, it's easy to mix up the variables:

Wrong:

# Swapping n and c in the denominators
ans[i // n][i % n] = mat[i // c][i % c]  # Variables are swapped!

Correct:

ans[i // c][i % c] = mat[i // n][i % n]  # n for source, c for target

4. Modifying the Original Matrix

Some developers try to optimize space by reusing the original matrix when dimensions match:

Problematic approach:

if r == rows:  # Same number of rows
    return mat  # Wrong! Columns might be different

Even if the row count matches, the column structure needs to change unless both dimensions match exactly.

5. Integer Division Confusion in Different Languages

If translating this solution to other languages, be aware that division operators behave differently:

Python 2 vs Python 3:

# Python 2: / performs integer division for integers
# Python 3: // is needed for integer division
index // cols  # Correct for Python 3

In languages like JavaScript:

// Wrong: JavaScript uses floating-point division
Math.floor(index / cols)  // Need explicit floor operation

The safest approach is to always use explicit integer division or floor operations to ensure consistent behavior across different environments.