algoadvance

Leetcode 566. Reshape the Matrix

Problem Statement

You are given a matrix represented as a 2D array of integers mat and two integers r and c representing the row and column dimensions of the desired reshaped matrix.

Your task is to reshape the matrix mat such that:

• The elements of mat are rearranged in row-major order into the new matrix with dimensions r x c.

If it is not possible to reshape the matrix to r x c dimensions, the function should return the original matrix.

---

Clarifying Questions

1. Input Constraints:
   • What is the range of the matrix dimensions and the values of elements within the matrix?

   Answer: The number of elements in mat will be between 1 and 100, inclusive. The matrix elements will be integers.

2. Values of r and c:
   • Is it guaranteed that r and c are always greater than zero?

   Answer: Yes, r and c will be positive integers.

3. Edge Cases:
   • How should the function handle if r and c are such that reshaping the matrix is not possible?

   Answer: The function should return the original matrix if reshaping is not possible.

---

Strategy

1. Validate Reshaping Possibility:
   • First, check if the total number of elements in mat equals r * c. If not, return mat unchanged.
2. Flatten the Original Matrix:
   • Convert the 2D matrix into a 1D list to simplify the element transfer.
3. Construct the New Matrix:
   • Create a new 2D matrix with dimensions r x c by filling it row by row using the elements from the flattened list.

---

Code

public class ReshapeMatrix {
    public int[][] matrixReshape(int[][] mat, int r, int c) {
        int rows = mat.length;
        int cols = mat[0].length;
        
        // Check if reshaping is possible
        if (rows * cols != r * c) {
            return mat;
        }
        
        int[][] reshapedMatrix = new int[r][c];
        int[] flatList = new int[rows * cols];
        int index = 0;
        
        // Flatten the original matrix
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                flatList[index++] = mat[i][j];
            }
        }
        
        // Fill the new reshaped matrix
        index = 0;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                reshapedMatrix[i][j] = flatList[index++];
            }
        }
        
        return reshapedMatrix;
    }

    public static void main(String[] args) {
        ReshapeMatrix solution = new ReshapeMatrix();
        
        // Example test case
        int[][] mat = // use example from above
        int r = 1, c = 4;
        int[][] result = solution.matrixReshape(mat, r, c);
        
        // Print the result
        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result[0].length; j++) {
                System.out.print(result[i][j] + " ");
            }
            System.out.println();
        }
    }
}

---

Time Complexity

• Time Complexity: (O(m \times n)), where (m) is the number of rows and (n) is the number of columns in the original matrix. This is because we iterate through all elements of the matrix exactly once to flatten and then fill the reshaped matrix.
• Space Complexity: (O(m \times n)) due to the additional space used for the flatList array and the reshaped matrix structure.

This approach ensures the task is completed efficiently and correctly, even for edge cases where reshaping might not be possible.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?