Problem Description

You are given a 2D matrix mat with m rows and n columns, as well as two integers r and c representing the desired number of rows and columns for a new reshaped matrix.

Your task is to reshape mat into a new matrix with r rows and c columns, containing all the elements of mat in the same row-traversing order (left to right, top to bottom).

If the reshape operation with the given r and c is not possible (i.e., the total number of elements does not match), return mat as is.

• Do not reuse elements. Every element must appear exactly once in the reshaped matrix.
• Only one valid solution is possible if the reshape is feasible.
• Input: mat (2D list/array), r (int), c (int)
• Output: 2D list/array of size r x c with the same elements in row-wise order, or original mat if impossible.

Thought Process

Let's break down the problem step by step. First, we need to determine if reshaping is possible. The only way to reshape a matrix without losing or duplicating elements is if the total number of elements stays the same. So, m * n must equal r * c.

If reshaping is possible, we need to copy the elements from the original matrix into the new matrix, making sure they appear in the same order as they were traversed row-wise. We can think of "flattening" the original matrix into a single list, then filling up the new matrix row by row from this list.

A naive (brute-force) approach would be to flatten the matrix into a list, then fill the new matrix. But we can optimize this by calculating the mapping from the old position to the new one directly using indices, saving space and time.

In summary, the main challenges are:

• Checking if reshape is possible
• Preserving the order of elements
• Efficiently mapping elements from mat to the new shape

Solution Approach

Let's walk through the algorithm step by step:

1. Calculate sizes: Get the number of rows (m) and columns (n) in the original matrix. Compute the total number of elements (m * n).
2. Check feasibility: If m * n != r * c, return mat as is.
3. Reshape process:
   • Create a new matrix of size r x c, filled with zeroes or placeholders.
   • For every element in the original matrix (using a single loop over m * n), compute:
     • The element's value in mat at mat[i // n][i % n]
     • The corresponding position in the new matrix at reshaped[i // c][i % c]
   • Assign the value directly from the old to the new matrix based on this mapping.
4. Return the reshaped matrix.

This approach avoids extra space for flattening and is efficient. We use integer division and modulo to map 1D indices to 2D positions.

Example Walkthrough

Let's use the following example:

• mat = [[1, 2], [3, 4]]
• r = 1, c = 4

Step 1: The original matrix has 2 rows and 2 columns (2 * 2 = 4 elements). The target is 1 row and 4 columns (1 * 4 = 4). Reshape is possible.

Step 2: Flatten the original matrix in row-wise order: [1, 2, 3, 4].

Step 3: Fill the new matrix:

• i = 0: mat[0][0] (1) → reshaped[0][0]
• i = 1: mat[0][1] (2) → reshaped[0][1]
• i = 2: mat[1][0] (3) → reshaped[0][2]
• i = 3: mat[1][1] (4) → reshaped[0][3]

Result: [[1, 2, 3, 4]]

If r = 2, c = 4, reshape is not possible, so return the original matrix.

Time and Space Complexity

Brute-force approach:

• Flatten the matrix into a list: O(m * n) time, O(m * n) extra space
• Fill the new matrix: O(m * n) time

Optimized approach (direct mapping):

• Single pass over all elements: O(m * n) time
• New matrix of size r * c: O(r * c) space (which is O(m * n) if reshape is possible)
• No extra space for flattening

The time complexity is optimal, since every element must be visited at least once.

Summary

The key to solving the "Reshape the Matrix" problem is recognizing that reshaping is only possible if the total number of elements stays the same. By using index mapping (via division and modulo), we can efficiently move each element from its old position to its new one without extra space for flattening. This approach is both elegant and efficient, preserving the original order and meeting all constraints.

Code Implementation

class Solution:
    def matrixReshape(self, mat, r, c):
        m, n = len(mat), len(mat[0])
        if m * n != r * c:
            return mat
        reshaped = [[0 for _ in range(c)] for _ in range(r)]
        for i in range(m * n):
            reshaped[i // c][i % c] = mat[i // n][i % n]
        return reshaped
      

class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
        int m = mat.size(), n = mat[0].size();
        if (m * n != r * c) return mat;
        vector<vector<int>> reshaped(r, vector<int>(c));
        for (int i = 0; i < m * n; ++i) {
            reshaped[i / c][i % c] = mat[i / n][i % n];
        }
        return reshaped;
    }
};
      

class Solution {
    public int[][] matrixReshape(int[][] mat, int r, int c) {
        int m = mat.length, n = mat[0].length;
        if (m * n != r * c) return mat;
        int[][] reshaped = new int[r][c];
        for (int i = 0; i < m * n; i++) {
            reshaped[i / c][i % c] = mat[i / n][i % n];
        }
        return reshaped;
    }
}
      

var matrixReshape = function(mat, r, c) {
    let m = mat.length, n = mat[0].length;
    if (m * n !== r * c) return mat;
    let reshaped = Array.from({length: r}, () => Array(c));
    for (let i = 0; i < m * n; i++) {
        reshaped[Math.floor(i / c)][i % c] = mat[Math.floor(i / n)][i % n];
    }
    return reshaped;
};