Leetcode – Reshape the Matrix Solution in Python

Spread the love

Reshape the Matrix is an interesting problem on Leetcode that tests your knowledge of matrix manipulation. This article will guide you through the Reshape the Matrix problem, explaining its different aspects, and teaching you how to solve it using Python.

Problem Statement

Leetcode problem #566 is titled “Reshape the Matrix” and it states:

In MATLAB, there is a handy function called reshape which can reshape an m x n matrix into a new one with 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:

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

Approaches to Solve the Problem

1. Queue Based Approach

One approach is to simulate the process of filling up the new matrix using a queue. First, we enqueue all elements of the original matrix, and then dequeue them to fill the new matrix.

from collections import deque

def matrixReshape(mat, r, c):
    if not mat or r * c != len(mat) * len(mat[0]):
        return mat

    queue = deque()
    for row in mat:
        for elem in row:
            queue.append(elem)

    new_mat = [[0] * c for _ in range(r)]
    for i in range(r):
        for j in range(c):
            new_mat[i][j] = queue.popleft()

    return new_mat

Explanation:

  1. Check if the reshape operation is possible by comparing r * c with the total number of elements in the original matrix. If not, return the original matrix.
  2. Enqueue all elements of the original matrix into a queue.
  3. Create a new matrix with dimensions r x c initialized with zeros.
  4. Dequeue elements from the queue and fill in the new matrix in a row-major order.

Time Complexity:

The time complexity is O(m * n), where m and n are the dimensions of the original matrix. The space complexity is also O(m * n) due to the additional queue.

2. Index Mapping Approach

We can observe that each cell in the matrix can be represented using a single index. Specifically, the cell at the i-th row and the j-th column in an m x n matrix can be represented using the index i * n + j. We can use this mapping to directly place each element from the original matrix into the correct position in the reshaped matrix.

def matrixReshape(mat, r, c):
    m, n = len(mat), len(mat[0])
    
    if r * c != m * n:
        return mat

    new_mat = [[0] * c for _ in range(r)]
    for i in range(m):
        for j in range(n):
            index = i * n + j
            new_row = index // c
            new_col = index % c
            new_mat[new_row][new_col] = mat[i][j]

    return new_mat

Explanation:

  1. Check if the reshape operation is possible by comparing r * c with the total number of elements in the original matrix. If not, return the original matrix.
  2. Create a new matrix with dimensions r x c initialized with zeros.
  3. For each element in the original matrix, calculate its index in the new matrix using the formula index = i * n + j, and place it in the corresponding position in the new matrix.

Time Complexity:

The time complexity is O(m * n), where m and n are the dimensions of the original matrix. The space complexity is O(r * c) which is required for the reshaped matrix.

Conclusion

We have explored two different approaches to solve the Reshape the Matrix problem on LeetCode using Python. The queue-based approach simulates the filling process but requires additional space for the queue. The index mapping approach efficiently calculates the new position for each element in the reshaped matrix without using additional space. Both approaches have linear time complexity. The choice between the two approaches can be made based on space constraints and personal preference. This problem is a good practice for understanding matrix manipulation and can be useful in various real-world applications.

Leave a Reply