Fish at app.codility.com/programmers in C++ Explained: N voracious fish are moving along a river. Calculate how many fish are alive.
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N)
Lesson 7 at app.codility.com/programmers
The solution and its explanation are given below.
Category of Article : Technology | Computers and Software | Algorithm
By: Chrysanthus Date Published: 4 Jul 2025
Problem
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.
Write a function:
int solution(vector<int> &A, vector<int> &B);
that, given two non-empty arrays A and B consisting of N integers, returns the number of fish that will stay alive.
For example, given the arrays shown above, the function should return 2, as explained above.
Write an efficient algorithm for the following assumptions:
• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [0..1,000,000,000];
• each element of array B is an integer that can have one of the following values: 0, 1;
• the elements of A are all distinct.
Note:
Assume that all the fish, whether going upstream or downstream, are on the same vertical straight line.Fish number Q is also represented by A[Q] and B[Q].
Before the start of the movement (race) the index variable, P simply identifies a fish that is positioned upstream, relative to the index variable, Q that identifies a fish that is positioned downstream. That is, an array index variable, P is less than an array index variable, Q. Note that P and Q do not refer to the point (index) of collision.
For two fish to collide and one eats the other, fish P has to be going downstream and fish Q has to be going upstream. In other words, B[P] has to be 1 and B[Q] has to be 0.
If B[P] is 0 and B[Q] is 1, then though the two fish they represent will never collide, one or both of them may still collide with one or two other fish. If no such collision takes place, then both fish will stay alive, going in opposite directions.
At the end of the “eating-race”, the one or more fish that remain alive, will be moving in the directions: either all upstream or all downstream, or in opposite directions.
Strategy for O(N) Time Complexity
The topic for this test is, Stacks and Queues, so it should occur to the candidate that stack or queue is needed. Actually, stack is used in the code below.An empty stack with the name, dsfish is created. The fish indexes for downstream fish will be entering this stack, from the top, one-by-one as the “eating-race” is going on. A fish that can be eaten next, is the one at the top of the stack, and has to be removed (popped out). On the other hand, if this fish eats an upstream fish, then it remains in the stack until it is possibly eaten.
The number of survivors is assumed to be the total number of fish in the given array, A, at the beginning of the solution code. This number is reduced for any fish that is eaten, in a for-loop with a nested while-loop.
The variable for survivors in the code, is survivors.
Solution in O(N) Time
A program with the solution function is (read through the code and read the comments):#include <iostream>The output is:
#include <vector>
#include <stack>
using namespace std;
int solution(vector<int> &A, vector<int> &B) {
stack<int> dsfish;
int survivors = A.size();
for(unsigned int i=0; i<A.size(); i++)
{
if(B[i]==1)
dsfish.push(i);
else
{
while(dsfish.size()>0)
{
if(A[dsfish.top()] > A[i]) { //downstream eats next upstream
survivors--;
break; //breaks while-loop
}
else {
dsfish.pop(); //upstream eats previous downstream
survivors--;
}
}
}
}
return survivors;
}
int main(int argc, char **argv)
{
vector<int> A{4, 3, 2, 1, 5};
vector<int> B{0, 1, 0, 0, 0};
int ret = solution(A, B);
cout << ret << endl;
return 0;
}
2
At app.codility.com/programmers the scoring and detected time complexity for this solution() is:
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N)
Note that fish going upstream does not have to be pushed onto the stack; it does not have to.
Conclusion
As the given vector A is scanned, the indexes for downstream fish are sent to the stack. The fish for the last index sent to the stack, while the scanning is continuing, is the one to confront the next fish upstream, and eating must take place, since all the fish are of different sizes. Without the use of the stack, more operations will be needed, leading to low efficiency of coding (high time complexity).If all the fish in the given vector, A are upstream, because of their corresponding values of 0 in the vector B, then there will be no collision. If all the fish in the given vector, A are downstream, because of their corresponding values of 1 in the vector B, then there will be no collision.
If all the fish in the first half of vector A are upstream and all the fish in the second half of vector A are downstream, then no collision will take place.