CODEWITHSUNDEEP
javaalgorithm
cdev
cdev

Reputation: 93

Finding nth largest number (many times) when the array size is increasing

We can easily find the nth largest using the Median of Medians Algorithm in O(n) time complexity.
If we have to find multiple times the nth largest numbers in the same array the best would be to sort O(NlogN) and then find the number in O(1) time complexity.
But what will be the efficient algorithm when the array size is increasing and
we have to find the nth largest number say array.length/3 th largest or array.length/2 th largest.
Example 

Array- 1,3,2,4,5 n=2 Answer-4   
New Array 1,3,2,4,5,7  n=2 answer-5  
New Array 1,3,2,4,5,7,3 n=2 answer-5

Note
n depends upon length of the array.
Please do help me.

Upvotes: 1

Views: 2768

Answers (2)

smocking
smocking

Reputation: 3709

Interesting problem. It depends on how many of the values are unique and how often you start with a new array, search and insert.

For many of n being unique, rarely starting with a new array with frequent insertion/searching, my first hunch would be:

  • Create a max-heap tip and a max-heap bulk, let n be the rank you want (nth value)
  • Insert: push new node into tip; if tip.size() >= (n-1), pop tip.top() and push into bulk
  • Search: return bulk.top()

That should give you O(N log(N)) for startup, O(log(N)) for insertion (much faster than sorting) and O(1) for searching.

If the number of unique values is much smaller than N, I would probably use counting sort and then sort the bins by value.

EDIT: Looking at Louis Wasserman's answer in some more detail, it seems to overlap almost completely with my first algorithm. However, would still like to suggest that instead of pulling "something out of the smaller-elements queue", you can make the search O(1) by picking the max element as the one to push into the min-heap.

Upvotes: 0

Louis Wasserman
Louis Wasserman

Reputation: 198103

I'm convinced that you have to keep track of the entire array at all times. Suppose that we receive 100, 99, 98, ..., 1, 0, -1, ... Then the nth-largest number will follow the same sequence, albeit slowed down: 100, 100, 99, 99, 98, 98...

Essentially, we can't forget any numbers from the input, because in this scenario each number will eventually be chosen as the nth largest.

That said, there's an O(log N) algorithm (for N, the number of elements overall) to "update" the nth largest element each time we read in a new element, which seems probably optimal. More or less, just keep a min priority queue of the n largest elements, and a max priority queue of the N-n smaller elements. Whenever n increases (array.length / 3 increases, for example), pull something out of the smaller-elements queue into the larger-elements queue; every time we read a new element, put it into the appropriate queue, possibly bumping an element out of the "larger-elements" queue into the "smaller-elements" queue.

Upvotes: 8

Related Questions