# Find pivot from a stream

This is also an interesting result, although it's quite simple.

You are given a stream of distinct numbers $$x[0], x[1], \ldots, x[n-1]$$, and you are to find a pivot number from them, i.e. $$x[i]$$ such that $$x[j]\lt x[i]$$ iff $$j\lt i$$. If there is no such number, report it. How to do it in $$O(n)$$ time with $$O(1)$$ space? Since it's a stream, each number can only be accessed once unless it's stored.

Solution:
Report the smallest possible pivot number: keep a candidate $$p$$ initialized to $$x[0]$$. It is invalidated whenever we see a number smaller than itself, which will be then initialized to the next number bigger than the max we have seen so far.