Leetcode 566. Reshape the Matrix

Problem Explanation

The problem is about reshaping a matrix into a new matrix with different dimensions. In this operation, we reshape the original matrix such that the row-traversal order of its elements remains unchanged. Specifically, we are given a two-dimensional array nums, representing the matrix, and two positive integers r and c that denote the number of rows and columns of the reshaped matrix, respectively.

If it is impossible to reshape the matrix according to the specified dimensions, we simply return the original matrix as the output.

Solution Approach

The solution first checks if the matrix is empty or if reshaping the matrix is not possible through check r * c != nums.size() * nums[0].size(). If either of the conditions hold true, we return the original matrix.

When we can reshape the matrix, we will then use a nested for loop. The outer loop goes through each row of the original list while the inner loop goes through each element of a row. The element is then placed in the result matrix using the row and column indices. The index of the element in the reshaped matrix is calculated using k / c (row index) and k % c (column index).

Example

If we have nums = [[1,2], [3,4]], r = 1, and c = 4, then we can reshape the matrix into [[1,2,3,4]]. The reshaped matrix still retains the row-traversal order of the original matrix ([1,2,3,4]).

If however, r = 2 and c = 4, then it is impossible to reshape the 2 * 2 matrix to a 2 * 4 matrix, so we return the original matrix.

Let's look into the solution in different languages:

Python Solution

1
2python
3class Solution:
4    def matrixReshape(self, nums: List[List[int]], r: int, c: int) -> List[List[int]]:
5      if len(nums) == 0 or r * c != len(nums) * len(nums[0]):
6          return nums
7
8      reshaped = [[0]*c for _ in range(r)]
9      count = 0
10
11      for i in range(len(nums)):
12          for j in range(len(nums[0])):
13              reshaped[count//c][count%c] = nums[i][j]
14              count += 1
15
16      return reshaped

Java Solution

1
2java
3class Solution {
4    public int[][] matrixReshape(int[][] nums, int r, int c) {
5        int n = nums.length, m = nums[0].length;
6        if (r*c != n*m)
7            return nums;
8        int[][] reshaped = new int[r][c];
9        for (int i = 0; i < r*c; i++)
10            reshaped[i/c][i%c] = nums[i/m][i%m];
11        return reshaped;
12    }
13}

JavaScript Solution

1
2javascript
3var matrixReshape = function(nums, r, c) {
4    var m = nums.length;
5    var n = nums[0].length;
6    if (m * n != r * c)
7        return nums;
8
9    var reshaped = Array.from(Array(r), () => new Array(c));
10    for (let i = 0; i < r * c; i++)
11        reshaped[Math.floor(i / c)][i % c] = nums[Math.floor(i / n)][i % n];
12
13    return reshaped;
14};

C++ Solution

1
2cpp
3class Solution {
4public:
5    vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {
6        if (nums.empty() || r * c != nums.size() * nums[0].size())
7            return nums;
8
9        vector<vector<int>> reshaped(r, vector<int>(c));
10        int k = 0;
11
12        for (const vector<int>& row : nums)
13            for (const int num : row) {
14                reshaped[k / c][k % c] = num;
15                ++k;
16            }
17
18        return reshaped;
19    }
20};

C# Solution

1
2csharp
3public class Solution {
4    public int[][] MatrixReshape(int[][] nums, int r, int c) {
5        int n = nums.Length, m = nums[0].Length;
6        if (r * c != n * m) 
7            return nums;
8
9        int[][] reshaped = new int[r][];
10        for (int i = 0; i < r; i++)
11            reshaped[i] = new int[c];
12        for (int i = 0; i < r * c; i++)
13            reshaped[i / c][i % c] = nums[i / m][i % m];
14        return reshaped;
15    }
16}

Let's conclude by summarizing these solutions. The above approaches are quite straightforward where first, we judge if the reshape is possible by checking if the number of elements in the original matrix equals the product of r and c. Next, notice how k (the total index of r * c) is used to find the new position of the element in the reshaped array and also the position of the current element in the original matrix.

This solution ensures we maintain the row-major order as specified in the problem statement. All the provided solutions have a time complexity of O(m*n), where m and n are the number of rows and columns of the given matrix, respectively.

The solutions are quite efficient and they do exactly what the problem asks for. These solutions are implemented in Python, Java, JavaScript, C++, and C#, covering some of the most commonly used programming languages among developers and coders. Each of these solutions follows a similar approach, thereby making it easy to understand and implement in any of these languages.

The basic understanding of handling multidimensional arrays or lists is all you need to solve this problem. It is a great problem to test basic programming skills and knowledge.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫