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 else: west_cars += 1 return cnt_passings
If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.