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.
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.
post by Shen-Fu Tsai