def solution(fish, direction):
  stack = []
  count = 0

  for i in range(len(fish)):
    if direction[i] == 1:
      stack.append(i)
    else:
      # continually feed previous fish to current fish
      while len(stack) > 0 and fish[stack[-1]] < fish[i]:
        stack.pop()
      if len(stack) == 0: # current fish won
        count += 1
  return count + len(stack)

#Challenge

You are given two non-empty arrays A and B consisting of N integers. Arrays A and B represent N voracious fish in a river, ordered downstream along the flow of the river.

The fish are numbered from 0 to \(N-1\). If P and Q are two fish and \(P < Q\), then fish P is initially upstream of fish Q. Initially, each fish has a unique position.

Fish number P is represented by \(A[P]\) and \(B[P]\). Array A contains the sizes of the fish. All its elements are unique. Array B contains the directions of the fish. It contains only 0s and/or 1s, where:

• 0 represents a fish flowing upstream
• 1 represents a fish flowing downstream

If two fish move in opposite directions and there are no other (living) fish between them, they will eventually meet each other. Then only one fish can stay alive − the larger fish eats the smaller one. More precisely, we say that two fish P and Q meet each other when \(P < Q\), \(B[P] = 1\) and \(B[Q] = 0\), and there are no living fish between them. After they meet:

• If \(A[P] > A[Q]\) then P eats Q, and P will still be flowing downstream,
• If \(A[Q] > A[P]\) then Q eats P, and Q will still be flowing upstream.

We assume that all the fish are flowing at the same speed. That is, fish moving in the same direction never meet. The goal is to calculate the number of fish that will stay alive.

For example, consider arrays A and B such that:

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

Initially all the fish are alive and all except fish number 1 are moving upstream. Fish number 1 meets fish number 2 and eats it, then it meets fish number 3 and eats it too. Finally, it meets fish number 4 and is eaten by it. The remaining two fish, number 0 and 4, never meet and therefore stay alive.

#Solution

The thing to notice about this problem is that the fish are flowing in two directions and fish we encounter later into the array have a higher intersection precedence compare to fish earlier in the array. For example:

2~> 3~> <~1 <~5

In this sequence there's two fishes with values 2 and 3 and opposing fishes with values 1 and 5. The last fish we encounter before meeting the fish with value 1 is 3, they collide and fish 1 is eaten. Then fish 5 eats fish 3, followed by eating fish 2 as well. The only surviving fish left is 5. And the function returns 1.

The idea here is that opposing fish come in a stream, with the most recent fish being at the top of the stream. When the fish encounters an opponent, that fish, and each fish before, it is considered until either the incoming fishes overpower the current fish or all incoming fishes are eaten.

We can represent this LAST-IN FIRST-OUT relationship using a stack. When we encounter a fish going in one direction, we add it to the stack as part of the stream. When we encounter a fish going in the opposite direction, we run through the stack until either the stack is exhausted or we find a fish that overpowers the current fish. If the stack is exhausted, we increment a counter to indicate that the current fish survived its journey.

The final survived fish is count is the sum of the stack and this counter.