566. Reshape the Matrix

Problem Description

Given an m x n matrix mat and two integers r and c representing the number of rows and columns of the wanted reshaped matrix, reshape the matrix into a new one with the dimensions r x c while maintaining the original data in row-traversing order. If the reshape is impossible, return the original matrix.

Solution Explanation

The core idea is to check if reshaping is possible and then perform the reshaping operation.

1. Feasibility Check:

The reshaping is only possible if the total number of elements in the original matrix (m * n) is equal to the total number of elements in the reshaped matrix (r * c). If they are not equal, reshaping is impossible, and we return the original matrix.

2. Reshaping:

If the reshaping is possible, we create a new matrix with dimensions r x c. We then iterate through the original matrix in row-major order (row by row, left to right) and fill the new matrix with the elements from the original matrix. The index calculation for the new matrix involves integer division (/) and modulo (%) operations to map the linear index of the original matrix to the 2D index of the new matrix.

Time and Space Complexity

Time Complexity: O(m*n), where 'm' and 'n' are the dimensions of the input matrix. We iterate through all the elements of the input matrix once to copy them into the reshaped matrix.

Space Complexity: O(r*c), where 'r' and 'c' are the dimensions of the reshaped matrix. This is the space used to store the new reshaped matrix. If we ignore the space used for the output, the space complexity is O(1).

Code Implementation (Python)

def matrixReshape(mat, r, c):
    """
    Reshapes a matrix.
 
    Args:
      mat: The original matrix (list of lists).
      r: The number of rows in the reshaped matrix.
      c: The number of columns in the reshaped matrix.
 
    Returns:
      The reshaped matrix, or the original matrix if reshaping is impossible.
    """
    m, n = len(mat), len(mat[0])  # Get dimensions of original matrix
    if m * n != r * c:
        return mat  # Reshaping impossible
 
    reshaped_matrix = [[0] * c for _ in range(r)]  # Initialize reshaped matrix
 
    for i in range(m * n):  # Iterate through elements in row-major order
        row = i // n  # Calculate row index in original matrix
        col = i % n  # Calculate column index in original matrix
        new_row = i // c  # Calculate row index in reshaped matrix
        new_col = i % c  # Calculate column index in reshaped matrix
        reshaped_matrix[new_row][new_col] = mat[row][col]
 
    return reshaped_matrix

Code Implementation (Other Languages)

The logic remains largely the same for other languages; the primary difference lies in syntax and data structure handling. The Python solution above can serve as a clear template for adapting the code to Java, C++, Javascript, TypeScript, Go, Rust, and C. The key differences would be in array/matrix creation and handling. For example:

• Java: Uses int[][] for the matrix.
• C++: Uses vector<vector<int>>.
• Javascript/TypeScript: Uses nested arrays.
• Go: Uses [][]int.
• Rust: Uses Vec<Vec<i32>>.
• C: Requires manual memory management with malloc and free.

Remember to handle memory allocation and deallocation appropriately in languages like C and C++. The core algorithm remains consistent across all languages.