Short Problem Definition:
Count the number of passing cars on the road.
expected worst-case time complexity is
expected worst-case space complexity is
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 else: west_cars += 1 return cnt_passings