algoadvance

Leetcode 566. Reshape the Matrix

Problem Statement

You are given a matrix represented by a 2D array, and you need to reshape the matrix into a different size, specified by the number of rows r and columns c. The reshaping should maintain the original order of elements. If it’s not possible to reshape the matrix to the given dimensions, return the original matrix.

Example:

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

However, if the reshape operation is not possible:

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

Clarifying Questions

1. Will the matrix contain only integers?
2. Can we assume the input dimensions r and c will always be non-negative?

Strategy

1. Check Total Elements: First, compute the total number of elements in the original matrix. This is necessary to determine whether reshaping is feasible.
2. Reshape Feasibility: Check if the total number of elements in the original matrix equals r * c. If not, return the original matrix.
3. Transform Elements: If reshaping is possible, flatten the original matrix into a single list of elements.
4. Populate New Matrix: Populate the new matrix of shape r by c using the flattened list of elements, maintaining the original element order.

Time Complexity

• Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the original matrix. This is because we are essentially iterating through all elements once.
• Space Complexity: O(m * n) for the reshaped matrix, although this is typically space used to store the result.

Code

#include <vector>

std::vector<std::vector<int>> matrixReshape(std::vector<std::vector<int>>& nums, int r, int c) {
    int m = nums.size();
    int n = nums[0].size();
    int total_elements = m * n;
    
    // Check if reshape is possible
    if (total_elements != r * c) {
        return nums; // Reshape not possible, return original matrix
    }
    
    // Initialize the new reshaped matrix
    std::vector<std::vector<int>> reshaped(r, std::vector<int>(c));
    
    // Flatten matrix and reshape
    for (int i = 0; i < total_elements; ++i) {
        reshaped[i / c][i % c] = nums[i / n][i % n];
    }
    
    return reshaped;
}

This code will reshape the matrix nums into the dimensions specified by r and c, if possible, preserving the order of elements, or return the original matrix if reshaping is not feasible.

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?