Codility中PassingCars问题Python优化及算法思路咨询

Hey there! I see you're gearing up for a Codility interview challenge, and you're stuck on boosting that performance score for the Passing Cars problem. Let's break this down step by step.

First, let's diagnose why your original code is hitting O(N²) time complexity:
Your code works correctly for correctness, but every time you encounter a 0, you slice the array and sum the remaining elements. Both slicing and summing are O(N) operations, and doing this N times leads to an overall O(N²) cost—way too slow for large input sizes, hence the 0% performance score.

The O(N) Solution #

Instead of recalculating the sum of 1s after each 0, we can flip our perspective: track how many 0s we've seen so far. Every time we hit a 1, all those previous 0s form a valid passing pair with this 1. We just add the count of 0s to our total pairs. This only requires a single pass through the array, no repeated calculations.

Here's the optimized code:

def solution(A):
    count_zeros = 0
    passing_pairs = 0
    # Handle the problem's hidden constraint: return -1 if pairs exceed 1e9
    max_limit = 10**9
    
    for num in A:
        if num == 0:
            count_zeros += 1
        else:
            passing_pairs += count_zeros
            if passing_pairs > max_limit:
                return -1
    
    return passing_pairs

• Time Complexity: O(N) — we iterate through the array exactly once.
• Space Complexity: O(1) — we only use two integer variables, no extra data structures.
• Bonus: Added the check for the 1e9 limit, which is a hidden requirement in the Codility problem that can cost you correctness points if missed.

Here's a framework I use for tackling algorithm problems (especially for platforms like Codility):

• First, fully understand the problem:
  • Clarify input/output requirements, edge cases (e.g., all 0s, all 1s, empty array), and hidden constraints (like the 1e9 limit here).
• Start with a brute-force solution, but don't stop there:
  • Brute-force helps you confirm you understand the problem, but always ask: What am I calculating repeatedly that I can cache or track in a single pass?
• Look for patterns or reverse your perspective:
  • Many O(N²) problems can be optimized by shifting focus (like we did here: from "count 1s after each 0" to "count 0s before each 1").
• Leverage common algorithmic tricks:
  • Prefix sums, hash maps, two pointers, or running totals are your friends for reducing time complexity. For Codility's prefix sum lessons, mastering running totals is key.
• Test edge cases explicitly:
  • Always test inputs that push the limits (max size, min size, boundary values) — these are often where correctness or performance issues pop up.
• Validate time/space complexity:
  • After writing code, do a quick check: a single loop is O(N), nested loops are almost always O(N²), hash map lookups are O(1) average case. Make sure your solution aligns with the problem's requirements.

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