The problem was posted earlier.
A brief description:
Find a pivot in a stream of distinct numbers, using sub-linear space.
Pivot = all numbers that came before it are smaller than it, all numbers that came after it are greater.
Solution
The algorithm will find the leftmost/earliest pivot, if a pivot exists.
If A[j] is a pivot, then A[j] = maximum of A[1], A[2], ..., A[j].
We keep track of the maximum seen so far, and a candidate leftmost pivot, which has the above property.
Once we have a candidate leftmost pivot, we check each subsequent number against that candidate. If we get a number which is smaller than the candidate pivot, then none of the numbers seen so far can be the leftmost pivot! Now we reset and look for a new leftmost candidate using the maximum seen so far property.
This gives us an O(1) space algorithm.
A brief description:
Find a pivot in a stream of distinct numbers, using sub-linear space.
Pivot = all numbers that came before it are smaller than it, all numbers that came after it are greater.
Solution
The algorithm will find the leftmost/earliest pivot, if a pivot exists.
If A[j] is a pivot, then A[j] = maximum of A[1], A[2], ..., A[j].
We keep track of the maximum seen so far, and a candidate leftmost pivot, which has the above property.
Once we have a candidate leftmost pivot, we check each subsequent number against that candidate. If we get a number which is smaller than the candidate pivot, then none of the numbers seen so far can be the leftmost pivot! Now we reset and look for a new leftmost candidate using the maximum seen so far property.
This gives us an O(1) space algorithm.
No comments:
Post a Comment