Codility - Fish

Solution to Codility lesson5-exercise2 Fish problem, link to Codility problem and complete solution at the end of the post.

Definitions:
\mathbf{A} = \{x \in \mathbb{N}\ |0\leq x \leq 1,000,000,000\land |A| = N\}
\mathbf{B} = \{x \in \mathbb{N}\ |0\leq x \leq 1\land |B| = N\},\mathbf{B}\, is\, a\, multiset.
\{N \in \mathbb{N}\ |\ 0\leq N \leq 100,000\}

Context (from Codility):

  • You are given two non-empty zero-indexed 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.

Problem:
Define a function solution with input A and B , such that solution returns the number of fishes that will stay alive.

  • Expected worst-case time complexity is O(N);
  • Expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Analysis:

To solve this we will visit every element on the downstream direction and take action depending on the direction of the last alive fish and the current one. This gives us four cases to analyse.
The first case: If the current fish is coming upstream and also the last alive visited. Since we are traversing the array downstream if the last alive fish is going upstream this can only mean one thing, if there was any fish before going downstream it got eaten by the one coming upstream, so no fish that is coming upstream will find a fish going downstream, so we can add these fishes to the result. Notice that this is valid also if the first fish of the array is coming upstream.

The second case: If the current fish is coming upstream and the last alive visited is going downstream. So this is an encounter, and as stated in the problem there is two outcomes. If the fish going downstream is bigger it eats the one coming upstream. And we wait for the next fish. Otherwise the one coming upstream wins and keep coming upstream, eating all the fishes going downstream until it finds a bigger fish, or it eats all the fishes going downstream. And them we can visit the next one. Later we are going to explain how we can compare the size of the fish with the ones going downstream.

The third case: If the current fish is going downstream and also the last alive visited. This case is similar to the first one, only here we don't account the fish going downstream to the result yet because it can find one coming upstream bigger than him. So what we have to do is put it on a stack. This stack will contain the fishes going downstream in order and this is the stack used on the second case to compare with the fish coming upstream.
The fourth case: If the current fish is going downstream and the last alive is coming upstream. In this case we can see that it won't result in a encounter either, because the last fish has a smaller index than the current one. So the fourth and third case can be merged in one case where the current fish is going downstream.

The final result will the sum of the fishes coming upstream with the ones going downstream.

Visiting every element of B gives us a time complexity of O(N). But we have the while loop inside our for loop. This while loop can add to our time complexity in the worst case only N - 1 iterations. Because it iterates in the size of the stack, the stack will never be bigger than and we stop the loop as soon as we find a fish bigger than the one coming upstream. So if we complete the iteration the stack will remain empty. And new fishes that haven't been visited yet will be added. To illustrate our worst case, imagine an array with N - 1 fishes going downstream and the last fish coming upstream, if this fish is bigger than all of the fishes on the stack this gives us time complexity O(N - 1) = O(N) in the while loop.  And the total time complexity is O(N) + O(N) = O(N) .
For the space complexity we have O(N) in the worst case when we have to store all the fishes of the array into the stack.

Complete Solution:

Time Complexity O(N)
Space Complexity O(N)

Link to GitHub solution here .
Link to Codility problem here .

/*Comment here*/