Codility Passing Cars

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:

public int passing_cars(int[] A) {
   int zCount = 0;  // how many going east 
   int passing = 0; // total passing pairs
   
   for(int i : A){
       if(i == 1){
           passing += zCount;
       }
       else zCount++;
   }
   if(passing > 1e9 || passing < 0) return -1;
   else return passing;
}