algoadvance

You are given a matrix represented by a two-dimensional array and two positive integers r and c representing the number of rows and columns of the desired reshaped matrix, respectively. 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 reshaping operation is not possible and the original matrix should be returned.

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]]

Clarifying Questions

  1. Can the input matrix be empty?
  2. Are there constraints on the input matrix dimensions, such as a maximum size?
  3. What should be returned in case of invalid transformation dimensions?

Strategy

  1. Flatten the Matrix: First, we need to flatten the original matrix into a single list of elements while maintaining the original row-traversing order.
  2. Check Dimensions: Verify if the reshaping process is possible. If the total number of elements in the original matrix does not match the product of r and c, return the original matrix.
  3. Reshape the Matrix: Populate the reshaped matrix using the flattened list.

Code

def matrixReshape(mat, r, c):
    # Number of elements in original matrix
    m = len(mat)
    n = len(mat[0]) if m > 0 else 0
    total_elements = m * n
    
    # Check if reshape is possible
    if total_elements != r * c:
        return mat
    
    # Flatten the original matrix
    flattened = [elem for row in mat for elem in row]
    
    # Create the new reshaped matrix
    reshaped = []
    for i in range(r):
        row = flattened[i * c:(i + 1) * c]
        reshaped.append(row)
    
    return reshaped

# Example usage:
mat = [[1,2],[3,4]]
r = 1
c = 4
print(matrixReshape(mat, r, c))  # Output: [[1,2,3,4]]

Time Complexity

Therefore, the overall time complexity is O(m * n).

Feel free to ask more questions or for further clarifications!

Try our interview co-pilot at AlgoAdvance.com