Introduction

The Codility Passing Cars problem looks like a pair-counting problem, but the direct nested-loop approach is too slow for large inputs. The key observation is that every westbound car passes all eastbound cars that appeared earlier in the array. Once you see that, the solution becomes a simple linear scan.

Understand the Pair Definition

The array contains only two values:

• '0 means a car traveling east'
• '1 means a car traveling west'

A passing pair is any index pair (P, Q) where:

• 'P < Q'
• 'A[P] == 0'
• 'A[Q] == 1'

So every time you encounter a 1, you want to know how many 0 values appeared before it.

That suggests a running counter rather than a brute-force comparison of every pair.

The Linear-Time Idea

Keep two variables:

• 'east_count: how many eastbound cars have been seen so far'
• 'pairs: total number of passing pairs so far'

Then scan left to right:

• if the current value is 0, increment east_count
• if the current value is 1, add east_count to pairs

That works because each westbound car forms a passing pair with every earlier eastbound car.

Python Implementation

1def solution(A):
2    east_count = 0
3    pairs = 0
4
5    for car in A:
6        if car == 0:
7            east_count += 1
8        else:
9            pairs += east_count
10            if pairs > 1_000_000_000:
11                return -1
12
13    return pairs
14
15
16print(solution([0, 1, 0, 1, 1]))

For the example [0, 1, 0, 1, 1], the answer is 5.

The passing pairs are:

• first 0 with first 1
• first 0 with second 1
• first 0 with third 1
• second 0 with second 1
• second 0 with third 1

Why This Is Better Than Nested Loops

A brute-force solution would test every pair of positions, which takes O(n^2) time.

For large arrays, that is too slow.

The running-counter solution touches each element once, so it runs in O(n) time and uses O(1) extra space.

That is exactly the kind of optimization interview and coding-platform problems are usually looking for: identify the cumulative information you need and update it incrementally.

Walk Through the Example

Take:

A = [0, 1, 0, 1, 1]

Step by step:

1. see 0, so east_count = 1
2. see 1, so pairs += 1, now pairs = 1
3. see 0, so east_count = 2
4. see 1, so pairs += 2, now pairs = 3
5. see 1, so pairs += 2, now pairs = 5

Done.

The trick is that the earlier eastbound cars do not need to be revisited. Their contribution is summarized in east_count.

Handling the Limit Condition

Codility adds one more rule: if the number of passing pairs exceeds 1,000,000,000, return -1.

That is easy to incorporate during the scan:

if pairs > 1_000_000_000:
    return -1

Doing this check as you go is cleaner than computing an enormous count first and checking later.

A More Formal View

You can think of the algorithm as counting inversions of a special kind. But you do not need a full inversion-counting algorithm because the array values are only 0 and 1.

The binary nature of the input simplifies the problem dramatically:

• all you need to remember is how many 0s have appeared
• every 1 consumes that count immediately

This is why the linear pass is enough.

Edge Cases

A few edge cases are worth checking mentally:

• all 0s, answer is 0
• all 1s, answer is 0
• empty array, answer is 0
• one eastbound car followed by many westbound cars, answer grows quickly

Example:

print(solution([0, 0, 0]))
print(solution([1, 1, 1]))
print(solution([]))

The logic handles all of these naturally.

Common Pitfalls

The biggest pitfall is reaching for nested loops immediately. They are easy to write and too slow.

Another issue is counting westbound cars first and then trying to reason backward, which usually complicates the logic unnecessarily.

Developers also sometimes forget the overflow-style rule that requires returning -1 after 1,000,000,000 pairs.

Finally, be clear that the pair must satisfy P < Q. The order in the array matters.

Summary

• Count eastbound cars as you scan from left to right.
• Every westbound car adds one passing pair for each earlier eastbound car.
• This gives an O(n) time, O(1) space solution.
• Check the 1,000,000,000 limit during the scan and return -1 if exceeded.
• The core insight is to replace explicit pair testing with a running count of earlier 0 values.