phpalgorithmstacktime-complexity

Fish codility excercise


Trying to solve this challenge on codility fish challenge I cannot understand why not all the tests are passed by my code.

function solution($A, $B) {
  // write your code in PHP7.0
  $stack =[];

  foreach($A as $key =>$value) {
    if(empty($stack)){
      array_push($stack,$key);
    }
    else if($B[count($stack)-1] == 1 && $B[$key]==0 )
    {
      if($value > $A[count($stack)-1])
      {
        array_pop($stack);
        array_push($stack,$key);
      }
    }
    else array_push($stack,$key);
  }
  return count($stack);
}

Solution

  • There are two problems with your code.

    1. The code does not reference items on the stack correctly. Use $B[$stack[count($stack)-1]] instead of $B[count($stack)-1]. Use $A[$stack[count($stack)-1]] not $A[count($stack)-1].

    2. Fish going upstream must fight every fish coming downstream, not just the first one that they meet.

    The following is a successful solution:

    function solution($A, $B) {
      // write your code in PHP7.0
      $stack = [];
      $key = 0;
      while($key < count($A)) {
        if(empty($stack)){
          array_push($stack,$key);
          $key++;
        }
        else if($B[$stack[count($stack)-1]] == 1 && $B[$key] == 0){
          if($A[$key] > $A[$stack[count($stack)-1]])
          {
            // fish going upstream eats fish going downstream
            array_pop($stack);
          } else {
            // fish going downstream eats fish going upstream
            $key++;
          }
        }
        else {
          array_push($stack,$key);
          $key++;
        }
      }
      return count($stack);
    }