Codility 'PassingCars' Solution

Martin Kysel · June 10, 2014

Short Problem Definition:

Count the number of passing cars on the road.



expected worst-case time complexity is O(N)

expected worst-case space complexity is O(1)


Count all cars heading in one direction (west). Each car heading the other direction (east) passes all cars that went west so far. Note that east cars at the beginning of the list pass no cars! Also do not forget the upper limit!


def solution(A):
    west_cars = 0
    cnt_passings = 0

    for idx in xrange(len(A)-1, -1, -1):
        if A[idx] == 0:
            cnt_passings += west_cars
            if cnt_passings > 1000000000:
                return -1
            west_cars += 1

    return cnt_passings

Twitter, Facebook