Reshape The Matrix - Leetcode Solution

Problem Statement:

You’re given a matrix represented by a two-dimensional array, and two positive integers r and c representing the row number and column number of the wanted reshaped matrix, respectively.

The reshaped matrix needs to 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:

nums = [[1,2], [3,4]] r = 1 c = 4

Output:

[[1,2,3,4]]

Explanation:

The input matrix is 2 x 2, while we are required to reshape it to 1 × 4, so we flattened the input 2 x 2 matrix to form a 1D array, traversing it in the row-wise order, and then reshaped it as a 1 × 4 matrix.

Solution:

To solve this problem, we will first need to check if the reshape operation is possible or not. If possible, we will create an output matrix with the given dimensions and fill it with the elements of the input matrix in row-traversing order.

To check if the reshape operation is possible, we will need to calculate the total number of elements in the input matrix and compare it with the product of the given row and column values.

If the product of row and column values is not equal to the total number of elements in the input matrix, then the reshape operation is not possible, and we simply return the input matrix as it is.

Otherwise, we create an empty output matrix with the given dimensions and fill it with the elements of the input matrix in row-traversing order.

Code:

The following is the Python implementation of the above approach.

def matrixReshape(nums, r, c):
    rows = len(nums)
    cols = len(nums[0])
    size = rows * cols
    
    # Check if reshape is possible
    if r * c != size:
        return nums
    
    # Fill output matrix with input elements in row-traversing order
    output = [[None] * c for _ in range(r)]
    row, col = 0, 0
    
    for i in range(rows):
        for j in range(cols):
            output[row][col] = nums[i][j]
            col += 1
            
            # Move to next row if current row is filled
            if col == c:
                row += 1
                col = 0
    
    return output

Time Complexity:

The time complexity of this code is O(m * n), where m and n are the dimensions of the input matrix. We need to traverse the entire input matrix once to check if reshape is possible and again to fill the output matrix.

1