The Fish Codility challenge was a fun algo to solve. Still falls in the easy category on the site and I agree with the rating.
I found a solution with O(N) complexity.
We will use a stack with a pair of values.
If we encounter fish that move upstream (the B value is 0) then if goes onto the stack ( the fish swimming upstreams won’t eat each other) and a fish swimming downstream will not bother the fish that were upstream from it.
When we encounter a fish swimming downstream we start comparing the next elements to it, and decide if it gets replaced on top of the stack by a fish swimming upstream which is bigger, or if it consumes the next fish swimming upstream because it is simply bigger than it.
If the next fish is also swimming downstream (1) then we add it on top of the stack.
We repeat all this until the end of the array and at the end we return the length of the stack.
And the report here.
Do you have another solution? Write it in the comments below!
Your solution gave me an idea for a simpler one, so I thought I may as well share it. It’s O(N), 14 lines of code and uses only one stack: https://app.codility.com/demo/results/trainingDQRD9R-76K/