Fish Codility 100% correct javascript solution

Fish Codility 100% Correct Javascript Solution

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.

Solution in javascript

function solution(A, B) {
  // write your code in JavaScript (Node.js 8.9.4)
  let C = [];
  let D = [];
  let index = 1;
  let finish = false;
  C[0] = A[0];
  D[0] = B[0];
  //fill the 0s

  while (index < A.length) {
    if (D[D.length - 1] === 0) {
      //if the last pushed element was 0, we will anyway add the new one (they stack or don't meet)
      C.push(A[index]);
      D.push(B[index]);
      index++;
    } else {
      //if the last element is 1, we start to navigate, be careful about reaching the end
      if (B[index] === 1) {
        C.push(A[index]);
        D.push(B[index]);
        index++;
      } else {
        let stop = 0;
        while (D[D.length - 1] === 1 && stop !== 1) {
          if (A[index] > C[C.length - 1]) {
            C.pop();
            D.pop();
            //if we are at the end place the big fish in the stack, to avoid an infinite loop
            if (C.length === 0) {
              index++;
              stop = 1;
              C.push(A[index]);
              D.push(B[index]);
            }
          } else {
            index++;
            stop = 1;
          }
        }
      }
    }
  }
  return C.length;

And the report here.
Do you have another solution? Write it in the comments below!

Leave a Reply