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

• 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  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 > 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 < 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.

StackExchange Code Review Q#74279, answer score: 7