Arunachalam,
Giving a quick thought... i felt duplicates are not going to affect my algorithm... If you have duplicate minimums you can select any one (may be the most central one) as the pivot and proceed...
Am i correct?
On 6/27/06, Googmeister <[EMAIL PROTECTED]> wrote:
Arunachalam wrote:
> Gene's solution also works fine. But this will also be n^2. since we have
> to scan back to get the upper and lower bound. for each element i, we have
> to go through all the elements and get the lower and upper bound. ( Huh...
> same problem again).
Gene uses balanced BST to compute the interval containing
the ith largest element. This is an elegant O(n log n) solution
to the problem.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
