Short Problem Definition:
N voracious fish are moving along a river. Calculate how many fish are alive.
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N)
Put all downstream swimming fishes on a stack. Any upstream swimming fish has to fight(eat) all fishes on the stack. If there is no fish on the stack, the fish survives. If the stack has some downstream fishes at the end, they also survive.
def solution(A, B): survivals = 0 stack =  for idx in xrange(len(A)): if B[idx] == 0: while len(stack) != 0: if stack[-1] > A[idx]: break else: stack.pop() else: survivals += 1 else: stack.append(A[idx]) survivals += len(stack) return survivals
If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.