Count cars passing in opposite directions

Question

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 < Q < 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 <= a.size-1
        results += 1 if a[j] != 0
        j += 1
      end
    end
    return -1 if results > 1000000000
  end
  results
end

I understand why this is \$O(n^2)\$, but I'm unsure how to make this faster.

Answer 1

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.

Answer 2

Edit: Brythan's solution is better, as it requires only a single iteration of the input rather than two iterations. The explanation is still relevant, so I'll leave the answer up.

You're counting the number of cars traveling westwards using a loop, but that's unnecessary. It's more efficient to loop trough the input once and count the number of westwards traveling cars (total_west).

Then in your main loop - When you encounter an eastward traveling car, subtract 1 from the total number of eastward traveling cars (total_west). All westwards traveling cars that could pass this car have already passed. - When you encounter an eastward traveling car, you add the total number of westward traveling cars to your total (total).

def solution(input)
  total_west = input.count(1)
  total      = 0

  input.each do |direction|
    if direction == 1
      total_west -= 1
    else
      total += total_west
    end

    if total > 10e8
      return -1
    end
  end

  return total
end

Time complexity is O(n), space complexity is O(1).

Answer 3

I wouldn't take an imperative approach for this kind of problems (no each, while, +=, inline conditionals nor early returns). A functional solution using a hash as state variable would look like this:

def solution(cars)
  passing = cars.reduce(going_east: 0, passing: 0) do |state, car|
    if car == 0 # car going to the east
      state.merge(going_east: state[:going_east] + 1)
    else
      state.merge(passing: state[:passing] + state[:going_east])
    end
  end[:passing] 
  passing > 1e9 ? -1 : passing
end

Answer 4

[Edit: I'm not happy with my solution after reflecting on it. Constructing the array cum_east is wasteful, as one can just maintain a running count, as others have done.]

Here's a slightly different way of looking at it. Let i be a car position, west to east. First compute an array cum_east, such that:

• if the car in position i is westbound (a[i]=>1), cum_east[i] is the number of cars that will pass that westbound car; and
• if the car in position i is eastbound (a[i]=>0), cum_east[i] is the number of eastbound cars that are led by (and include) that eastbound car.

It is then a simple matter of summing the values of cum_east for the westbound cars.

Code

def nbr_passed(a)
  cum_east = a[1..-1].reduce([1-a.first]) { |cum, c| cum << cum.last + 1-c }
  n = a.zip(cum_east).reduce(0) { |t,(cum_east, direction)| t + cum_east*direction }
  n > 1e9 ? -1 : n
end

Example

a = [0, 1, 0, 1, 1]  
nbr_passed(a)
  #=> 5

Explanation

For the example above, the following steps are performed.

cum_east = a[1..-1].reduce([1-a.first]) { |cum, c| cum << cum.last + 1-c }
  #=> [1, 1, 2, 2, 2]
b = a.zip(cum_east)
  #=> [[0, 1], [1, 1], [0, 2], [1, 2], [1, 2]]

The third element of b ([0, 2]) shows that the eastbound car in that position is being followed by one other eastbound car. The fourth element ([1, 2]) indicates that the westbound car in that position will pass two eastbound cars.

n = b.reduce(0) { |t,(cum_east, direction)| t + cum_east*direction }
  #=> 5

This simply sums the cumulative values for the westbound cars, as direction => 1 (0) for westbound (eastbound) cars.

  n > 1e9 ? -1 : n
    #=> 5