CareerCup

scan the arrays, when encountering downstream fish (B[i]==1) push the fish into a stack. Otherwise (upstream fish), compare the top of the stack to the current fish, and if the current fish is larger, pop the top of the stack, otherwise increase the "eaten" count by 1. Simple O(N) time & space.

Here is pseudo code I cooked up...

fishes_alive	= 0;
fish_upstream	= (dequeue(b) == 0);
fish_size 	= dequeue(a);

while (q_not_empty(b)) {

	if (fish_upstream) {
		fishes_alive++;
		fish_upstream	= dequeue(b);
		fish_size	= dequeue(a);
	} else {
		// fish is going downstream...check if it can eat anything else.
		next_fish_upstream 	= peek(b);
		next_fish_size		= peek(a);

		if (fish_upstream == next_fish_upstream) {
			// both fishes int the same direction...no need to compare sizes
			fishes_alive++;
			fish_upstream	= dequeue(b);
			fish_size	= dequeue(a);
		} else {
			// next fish is upstream, curr fish is downstream....compare sizes
			if (fish_size < next_fish_size) {
				// fish gets eaten by next fish
				fish_upstream = dequeue(b);
				fish_size     = dequeue(a);
			} else {
				// next fish gets eaten by current fish
				dequeue(b);
				dequeue(a);	// not storing return value => fish dies
			}
		}				
			
	}
}

if (fish_upstream != true) {
	// we had a downstream fish and it gobble up all the way to the end
	// i.e. it is alive and we need to count it
	fishes_alive++;
}

return (fishes_alive);

small-changes you need to use a stack...... go away with your wrong solutions.....

Code in python based on my answer above:

def countFish(a, b):
  l=list()
  n=len(a)
  cnt=0

  for i in range(n):
    if b[i]==1:
      l.append(a[i])
    elif len(l)>0:
      n-=1
      if l[-1]<a[i]:
        l.pop()

  return n

def main():
  a=[4,3,2,1,5]
  b=[0,1,0,0,0]
  print(a,b)
  print(countFish(a,b))

if __name__ == "__main__":
  main()

package com.mohit.stack;

import java.util.Stack;

public class fish {

    private Stack<Integer> stack = null;
    
    public fish() {
        int[] A = new int[5];
        int[] B = new int[5];
        A[0] = 4;    B[0] = 1;
        A[1] = 3;    B[1] = 0;
        A[2] = 2 ;   B[2] = 0;
        A[3] = 10  ;  B[3] = 1;
        A[4] = 5   ; B[4] = 0;
        
        System.out.println(solution(A,B));
    }

    public int solution(int[] A, int[] B) {
        int result = 0;
        if (A.length == 0 || B.length == 0)
            result = 0;

        stack = new Stack<Integer>();
        checkAndPush(A, B);
        System.out.println("input = " + A.length + " and result = " + stack.size());
        return stack.size();
    }

    private void checkAndPush(int[] A, int[] B) {

        for (int i = 0; i < B.length; i++) {

            stack.push(i);
            while (stack.size() > 1) {
                int pop = stack.pop();
                int peek = stack.peek();

                if (B[pop] == 0 && B[peek] == 1) {
                    if (A[pop] > A[peek]) {
                        stack.pop();
                        stack.push(pop);
                    }
                } else {
                    stack.push(pop);
                    break;
                }
            }
        }

    }

}

package com.mohit.stack;

import java.util.Stack;

public class fish {

    private Stack<Integer> stack = null;
    
    public fish() {
        int[] A = new int[5];
        int[] B = new int[5];
        A[0] = 4;    B[0] = 1;
        A[1] = 3;    B[1] = 0;
        A[2] = 2 ;   B[2] = 0;
        A[3] = 10  ;  B[3] = 1;
        A[4] = 5   ; B[4] = 0;
        
        System.out.println(solution(A,B));
    }

    public int solution(int[] A, int[] B) {
        int result = 0;
        if (A.length == 0 || B.length == 0)
            result = 0;

        stack = new Stack<Integer>();
        checkAndPush(A, B);
        System.out.println("input = " + A.length + " and result = " + stack.size());
        return stack.size();
    }

    private void checkAndPush(int[] A, int[] B) {

        for (int i = 0; i < B.length; i++) {

            stack.push(i);
            while (stack.size() > 1) {
                int pop = stack.pop();
                int peek = stack.peek();

                if (B[pop] == 0 && B[peek] == 1) {
                    if (A[pop] > A[peek]) {
                        stack.pop();
                        stack.push(pop);
                    }
                } else {
                    stack.push(pop);
                    break;
                }
            }
        }

    }

}