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.<\/p>\n\n\n\n
I found a solution with O(N) complexity.<\/p>\n\n\n\n
We will use a stack with a pair of values.<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
If the next fish is also swimming downstream (1) then we add it on top of the stack.<\/p>\n\n\n\n
We repeat all this until the end of the array and at the end we return the length of the stack.<\/p>\n\n\n\n
function solution(A, B) {\n \/\/ write your code in JavaScript (Node.js 8.9.4)\n let C = [];\n let D = [];\n let index = 1;\n let finish = false;\n C[0] = A[0];\n D[0] = B[0];\n \/\/fill the 0s\n\n while (index < A.length) {\n if (D[D.length - 1] === 0) {\n \/\/if the last pushed element was 0, we will anyway add the new one (they stack or don't meet)\n C.push(A[index]);\n D.push(B[index]);\n index++;\n } else {\n \/\/if the last element is 1, we start to navigate, be careful about reaching the end\n if (B[index] === 1) {\n C.push(A[index]);\n D.push(B[index]);\n index++;\n } else {\n let stop = 0;\n while (D[D.length - 1] === 1 && stop !== 1) {\n if (A[index] > C[C.length - 1]) {\n C.pop();\n D.pop();\n \/\/if we are at the end place the big fish in the stack, to avoid an infinite loop\n if (C.length === 0) {\n index++;\n stop = 1;\n C.push(A[index]);\n D.push(B[index]);\n }\n } else {\n index++;\n stop = 1;\n }\n }\n }\n }\n }\n return C.length;<\/code><\/pre>\n\n\n\n