Count cars passing in opposite directions The problem comes from codility, whose coding problems I'm starting to enjoy as their evaluation criteria really looks at runtime. 

Task description


  A non-empty zero-indexed array A consisting of N integers is
  given. The consecutive elements of array A represent consecutive
  cars on a road.
  
  Array A contains only 0s and/or 1s:
  
  
  0 represents a car traveling east,  
  1 represents a car traveling west.  
  
  
  The goal is to count passing cars. We say that a pair of cars (P, Q),
  where 0 ≤ P &lt; Q &lt; N, is passing when P is traveling to the east and
  Q is traveling to the west.
  
  For example, consider array A such that:  

  A[0] = 0  
  A[1] = 1  
  A[2] = 0  
  A[3] = 1  
  A[4] = 1  

  
  We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3),
  (2, 4).
  
  Write a function:  

def solution(a)

  
  that, given a non-empty zero-indexed array A of N integers, returns the number of passing cars.
  
  The function should return −1 if the number of passing cars exceeds
  1,000,000,000.  
  
  For example, given:  

  A[0] = 0  
  A[1] = 1  
  A[2] = 0  
  A[3] = 1  
  A[4] = 1  

  
  the function should return 5, as explained above.  
  
  Assume that:  
  
  
  N is an integer within the range [1..100,000];  
  each element of array A is an integer that can have one of the following values: 0, 1.  
  
  
  Complexity:  
  
  
  expected worst-case time complexity is \$O(N)\$;  
  expected worst-case space complexity is \$O(1)\$, beyond input storage (not counting the storage required for input arguments).  
  
  
  Elements of input arrays can be modified.


Solution

I've tried my hand at 2 different solutions, one where I delete elements from the array but that was slower than my first pass like this:

def solution(a)
  results = 0
  a.each_with_index do |el, i|
    if el == 0
      j = i
      while j &lt;= a.size-1
        results += 1 if a[j] != 0
        j += 1
      end
    end
    return -1 if results &gt; 1000000000
  end
  results
end


I understand why this is \$O(n^2)\$, but I'm unsure how to make this faster.
def solution(a)
  results = 0
  east_count = 0
  a.each do |el|
    if el == 0
      east_count += 1
    else
      results += east_count
    end
    return -1 if results &gt; 1000000000
  end
  results
end


Note that you don't have to compare each car to every other car.  You just have to track how many are traveling east and each time you find someone going west, increment your results by the eastbound count.  I find this easier to understand than tracking the westbound cars backwards.  

r | c
--+--
0 | 0
0 | 1
1 | 1 (0,1)
1 | 2
3 | 2 (0,3), (2,3)
5 | 2 (0,4), (2,4)


In the table, r stands for results and c stands for east_count.  The pairs found at any point are to the right.  

This will not find the pairs that pass, but it does count them.  It maintains the required \$P &lt; Q\$ by order of iteration.  

I don't know much about Ruby, so I won't try to make syntactic comments.  Apologies if my own syntax is weak.  

This iterates through the array once, so it's \$O(n)\$ in time.  It defines a constant number of scalar variables, so it's \$O(1)\$ memory beyond the input array.