LeetCode 566题重塑矩阵解法的时间复杂度分析及优化可行性问询

Great call on your time complexity assessment! You’re absolutely right that this solution runs in O(N) time, where N is the total number of elements in the original matrix. Let’s break down why that’s the case, then dive into some optimizations to make it even better.

Time Complexity Breakdown #

Let’s walk through each part of the code to confirm the O(N) runtime:

• The initial check (mat.length * mat[0].length !== r * c) is O(1) — we’re just doing simple arithmetic with fixed values, no iteration needed.
• The reduce step flattens the matrix into a single array. This loops through every element in the original matrix exactly once, so that’s O(N) time.
• The final loop splits the flattened array into chunks of size c. Each slice operation takes time proportional to the chunk size, but when you add up all slices, we’re covering every element in the flattened array exactly once. This means this loop is also O(N).
• Adding all these together, the total time complexity is indeed O(N) — your initial thought was spot-on!

Optimization Opportunities #

The original solution works perfectly, but we can optimize it to cut down on extra space usage and reduce some overhead. Here’s how:

Avoid the Intermediate Flattened Array #

Instead of first flattening the matrix, we can map each element directly to its position in the new matrix using basic arithmetic. This eliminates the need for the extra flattened array, saving us O(N) extra space (while keeping time complexity still O(N)).

Here’s the optimized code:

var matrixReshape = function(mat, r, c) {
    const originalRows = mat.length;
    const originalCols = mat[0].length;
    
    // Early exit if reshape isn't possible
    if (originalRows * originalCols !== r * c) return mat;
    
    // Initialize the result matrix
    const result = Array(r).fill().map(() => Array(c));
    let currentIndex = 0;
    
    // Iterate through original matrix and place elements directly in result
    for (let i = 0; i < originalRows; i++) {
        for (let j = 0; j < originalCols; j++) {
            // Calculate position in result matrix
            const resultRow = Math.floor(currentIndex / c);
            const resultCol = currentIndex % c;
            result[resultRow][resultCol] = mat[i][j];
            currentIndex++;
        }
    }
    
    return result;
};

Why this is better: #

• Space efficiency: The original solution uses O(N) space for the flattened array plus O(N) for the result matrix. This optimized version only uses O(N) space for the result (since we have to create it anyway), cutting the extra memory usage in half.
• Lower constant factors: Skipping the reduce and slice operations eliminates function call overhead and unnecessary array manipulation. While the time complexity remains O(N), the actual runtime can be faster for large matrices due to these smaller constant costs.

A tiny optional tweak: instead of calculating resultRow with Math.floor(currentIndex / c) each time, you can track the current result row explicitly and increment it whenever currentIndex is a multiple of c. This saves a bit of computation, but the difference is negligible for most use cases.

Edge Case Handling #

Both solutions handle the critical edge case correctly: immediately returning the original matrix if the total number of elements doesn’t match the desired reshaped dimensions. This avoids wasting time on unnecessary processing when reshape isn’t possible.

内容的提问来源于stack exchange，提问作者MohamedGelsaffy