Codility Passing Cars任务代码性能优化求助：正确性100%但超时

Hey there! Let's break down why your current code is hitting timeouts and how to fix it to grab that 100% performance score.

What's Causing the Timeouts? #

Your current code uses a nested loop: every time it finds a 0, it iterates through all elements after it to count 1s. This gives a time complexity of O(n²). For large input sizes (like 100,000 elements), that means 10 billion operations—way too slow for the tight time limit.

The Optimized O(n) Approach #

Instead of rechecking the rest of the array every time you see a 0, we can track the number of 0s we've encountered so far as we iterate through the array. Every time we hit a 1, we add the current count of 0s to our total (since each of those 0s will form a valid passing pair with this 1).

We also add an early exit: if the total exceeds 1,000,000,000 at any step, we immediately return -1 to avoid unnecessary calculations.

Optimized Code #

function solution(A) {
    let zeroCount = 0;
    let totalPairs = 0;
    const maxAllowed = 1000000000;

    for (const num of A) {
        if (num === 0) {
            zeroCount++;
        } else {
            totalPairs += zeroCount;
            // Early exit if we exceed the limit
            if (totalPairs > maxAllowed) {
                return -1;
            }
        }
    }

    return totalPairs;
}

Key Details to Note: #

• Single Pass Efficiency: We only loop through the array once, cutting the time complexity to O(n)—this handles even the largest input sizes with ease.
• Space Savings: We only use a couple of variables, so space complexity stays at O(1).
• Early Termination: As soon as the total pairs exceed the 1e9 limit, we stop processing and return -1 right away, saving extra work.

Quick Example Walkthrough #

Let's test with A = [0, 1, 0, 1, 1]:

1. First element is 0 → zeroCount becomes 1.
2. Second element is 1 → total pairs += 1 (total = 1).
3. Third element is 0 → zeroCount becomes 2.
4. Fourth element is 1 → total pairs += 2 (total = 3).
5. Fifth element is 1 → total pairs += 2 (total = 5).
   Final total is 5, which matches the correct number of passing pairs.

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