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: 3 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(int A[], int B[], int N);
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 (lesson) for this test is, Stack and Queue, so it should occur to the candidate that stack or queue is needed. Actually, stack is used in the code below.An empty Stack object with name, stack 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
The C stack developed in the lesson for this task (problem) is used here. A program with the solution function is as follows (read through the code and comments). Pay particular attention to the solution function definition and to the user code in the main() function.#include <stdio.h>The output is:
#include <stdlib.h>
struct Element {
int value;
struct Element *previous;
};
struct Stack {
int size;
struct Element *back;
int (*top)();
void (*push)(int);
void (*pop)();
} stack;
int top() {
if (stack.size > 0) //stack has at least 1 element
return stack.back->value; //use -> to obtain value from a pointer
else
printf("Error: No element to remove from stack!\n");
}
void push(int inte) {
struct Element *element = malloc(sizeof(struct Element)); //declaring and creating the object, element
if (element != 0) { //check whether allocation of memory element was successful
element->value = inte;
if (stack.size == 0) { //first element
element->previous = 0;
stack.back = element;
stack.size = stack.size + 1; //add 1 to size
}
else {
element->previous = stack.back; //previous points to previous element
stack.back = element; //stack points to new element
stack.size = stack.size + 1; //add 1 to size
}
}
else {
printf("Error: New element could not be created!\n");
exit(1);
}
}
void pop() {
if (stack.size > 0) { //stack has at least 1 element
struct Element *lastElement = stack.back;
stack.back = lastElement->previous; //point to previous element
free(lastElement); //free last (top) element from memory
stack.size = stack.size - 1; //subtract 1 from size
}
else {
printf("Error: No element to remove from stack!\n");
exit(1);
}
}
int solution(int A[], int B[], int N) {
int survivors = N;
for(unsigned int i=0; i<N; i++) {
if(B[i]==1)
stack.push(i);
else
{
while(stack.size>0)
{
if(A[stack.top()] > A[i]) { //downstream eats next upstream
survivors--;
break; //breaks while-loop
}
else {
stack.pop(); //upstream eats previous downstream
survivors--;
}
}
}
}
return survivors;
}
int main(int argc, char **argv)
{
//Assigning stack attributes and methods (functions)
stack.size = 0;
stack.top = top;
stack.push = push;
stack.pop = pop;
//user code begins
int A[] = {4, 3, 2, 1, 5};
int B[] = {0, 1, 0, 0, 0};
int N = sizeof(A)/sizeof(A[0]); //divide size of array by size of one (first) element
int ret = solution(A, B, N);
printf("%i\n", ret);
//user code begins
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 array 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 array, A are upstream, because of their corresponding values of 0 in the array B, then there will be no collision. If all the fish in the given array, A are downstream, because of their corresponding values of 1 in the array B, then there will be no collision.
If all the fish in the first half of array A are upstream and all the fish in the second half of array A are downstream, then no collision will take place.