Reshape the Matrix

LeetCode 566 | Difficulty: Easy

Easy

Problem Description

In MATLAB, there is a handy function called reshape which can reshape an m x n matrix into a new one with a different size r x c keeping its original data.

You are given an m x n matrix mat and two integers r and c representing the number of rows and the number of columns of the wanted reshaped matrix.

The reshaped matrix should be filled with all the elements of the original matrix in the same row-traversing order as they were.

If the reshape operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.

Example 1:

Input: mat = [[1,2],[3,4]], r = 1, c = 4
Output: [[1,2,3,4]]

Example 2:

Input: mat = [[1,2],[3,4]], r = 2, c = 4
Output: [[1,2],[3,4]]

Constraints:

- `m == mat.length`

- `n == mat[i].length`

- `1 <= m, n <= 100`

- `-1000 <= mat[i][j] <= 1000`

- `1 <= r, c <= 300`

Topics: Array, Matrix, Simulation

---

Approach

Matrix

Treat the matrix as a 2D grid. Common techniques: directional arrays (dx, dy) for movement, BFS/DFS for connected regions, in-place marking for visited cells, boundary traversal for spiral patterns.

When to use

Grid traversal, island problems, path finding, rotating/transforming matrices.

---

Solutions

Solution 1: C# (Best: 264 ms)

Metric	Value
Runtime	264 ms
Memory	33.2 MB
Date	2019-12-06

Solution

public class Solution {
    public int[][] MatrixReshape(int[][] nums, int r, int c) {
            int m = nums.GetLength(0);
    int n = nums[0].Length;

    if (r * c > m * n)
    {
        return nums;
    }

    int[][] res = new int[r][];
    for (int i = 0; i < r; i++)
    {
        res[i] = new int[c];
    }
    for (int i = 0; i < r * c; i++)
    {
        res[i/c][i%c] = nums[i/n][i%n];
    }
    
    return res;
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• LeetCode provides 4 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Do you know how 2d matrix is stored in 1d memory? Try to map 2-dimensions into one.

Hint 2: M[i][j]=M[n*i+j] , where n is the number of cols. This is the one way of converting 2-d indices into one 1-d index.
Now, how will you convert 1-d index into 2-d indices?

Hint 3: Try to use division and modulus to convert 1-d index into 2-d indices.

Hint 4: M[i] => M[i/n][i%n] Will it result in right mapping? Take some example and check this formula.