566. Reshape the Matrix
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 0
Acceptance rate: 61.1%
Problem Breakdown
The problem asks us to reshape a given matrix into a new one with specified dimensions while maintaining the original data’s row-traversing order. If the reshaping is not possible (e.g., due to mismatched element counts), we should return the original matrix.
Inputs:
nums: A 2D array representing the original matrix.r: An integer representing the desired number of rows in the reshaped matrix.c: An integer representing the desired number of columns in the reshaped matrix.
Outputs:
- A 2D array representing the reshaped matrix if possible; otherwise, the original matrix.
Implicit Constraints/Edge Cases:
- The dimensions of the new matrix must match the total number of elements in the original matrix.
- If
r * cis not equal to the total number of elements innums, return the original matrix. - Handle cases where
numsis empty or has only one row/column.
Intuition
A brute-force approach would involve iterating through the original matrix, collecting all elements into a list, and then filling the new matrix row by row. However, this approach is inefficient as it requires additional space to store the intermediate list of elements.
The key insight is to directly map the indices of the original matrix to the reshaped matrix without using an intermediate list. This can be achieved by calculating the corresponding indices in the original matrix for each element in the new matrix.
Approach
- Calculate Total Elements: Compute the total number of elements in the original matrix (
total_elements = len(nums) * len(nums[0])). - Check Reshape Possibility: If
r * cis not equal tototal_elements, return the original matrix. - Initialize Result Matrix: Create a new 2D array with dimensions
r x c. - Fill Result Matrix:
- Iterate through each element in the reshaped matrix using nested loops.
- For each element at position
(i, j)in the reshaped matrix, calculate its corresponding position(original_row, original_col)in the original matrix. - Assign the value from the original matrix to the reshaped matrix.
Complexity Analysis
- Time Complexity: O(n), where n is the total number of elements in the matrix. We iterate through each element once.
- Space Complexity: O(r * c) for storing the reshaped matrix. If we consider the input and output matrices, the space complexity remains O(n).
Solution
def matrixReshape(nums, r, c):
# Calculate total number of elements in the original matrix
if not nums or not nums[0]:
return nums
total_elements = len(nums) * len(nums[0])
# Check if reshaping is possible
if total_elements != r * c:
return nums
# Initialize the result matrix with dimensions r x c
reshaped_matrix = [[0] * c for _ in range(r)]
# Fill the reshaped matrix
for i in range(total_elements):
original_row, original_col = divmod(i, len(nums[0]))
new_row, new_col = divmod(i, c)
reshaped_matrix[new_row][new_col] = nums[original_row][original_col]
return reshaped_matrix
Edge Cases Handled
- Empty Input: If
numsis empty or contains an empty list, the function will return the original matrix. - Single Row/Column: The function correctly handles cases where
numshas only one row or column. - Mismatched Dimensions: If
r * cdoes not match the total number of elements innums, the original matrix is returned.