# Codility Passing Cars

#### Posted on October 18, 2013

##### Last updated on October 18, 2013

In this article I will provide a solution to the Passing Cars sample Codility problem. Refer to the link for an explanation of the problem. The gist of it is:

Given an array $$A$$ of $$N$$ integers from the set $$[0,1]$$, interpret $$0$$ as a car travelling east, and $$1$$ as a car travelling west. A car with index $$P$$ is said to pass car with index $$Q$$ when $$P \lt Q$$ and $$P$$ is travelling east and $$Q$$ is travelling west. Count the number of total pairs of cars passing each other.

The naive $$O(n^2)$$ is to go through every element that’s travelling east (a $$0$$), and then go through all the elements after it, checking how many are going west (a $$1$$).

This can be improved to $$O(N)$$ as follows: If we encounter a car going west (a $$1$$), we know that it passes with every car before it that was going east (a $$0$$). By keeping track of how many cars going east we’ve seen so far, we can easily compute the total number of passing cars. The following Java code scores 100/100 on Codility:

Markdown SHA1: 6fc0ac47055d8848da3bc6cdbdb41d947fc18162