In an array A[1], A[2], ..., A[n] of distinct numbers, A[p] is called a pivot if all numbers to left of A[p] are less than A[p] and all numbers to right of A[p] are greater than A[p].
i.e. for any i < p, A[i] < A[p] and for any j > p, A[p] < A[j].
Basically, if we sort the sub-array A[1], A[2], ..., A[p-1] and sub-array A[p+1], .., A[n] independently, then whole array will be sorted (this must remind you of quicksort).
Now suppose you were given the array A as a stream of numbers A[1], A[2], ... i.e. you can access A by accessing only A[1] first, then A[2], and so on. Once you access A[5], you cannot access A[4] again (unless you save it) etc.
Given a stream of distinct numbers, can you find a pivot (or say if there is none) using an algorithm which uses sub-linear space?
[The optimal algorithm will use O(1) space, and O(n) time total: Solution]
i.e. for any i < p, A[i] < A[p] and for any j > p, A[p] < A[j].
Basically, if we sort the sub-array A[1], A[2], ..., A[p-1] and sub-array A[p+1], .., A[n] independently, then whole array will be sorted (this must remind you of quicksort).
Now suppose you were given the array A as a stream of numbers A[1], A[2], ... i.e. you can access A by accessing only A[1] first, then A[2], and so on. Once you access A[5], you cannot access A[4] again (unless you save it) etc.
Given a stream of distinct numbers, can you find a pivot (or say if there is none) using an algorithm which uses sub-linear space?
[The optimal algorithm will use O(1) space, and O(n) time total: Solution]
No comments:
Post a Comment