1
$\begingroup$

This is a rather well known solution to the $k$-th order statistic problem which requires us to find the $k$-th largest number in an unsorted array with $n$ elements where $1 \leq k \leq n$:

public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
        
        for (int num: nums) {
            heap.add(num);
            
            if (heap.size() > k) {
                heap.remove();
            }
        }
        
        return heap.remove();
    }

A brief summary of this approach is that we maintain a min heap and keep polling from this heap each time its size exceeds $k$. This way, our final heap will contain $k$ elements, and these $k$ elements are guaranteed to be last $k$ elements in the sorted array (since we have been polling minimums). Within these last $k$ elements, the minimum element is guaranteed to be the $k$-th largest so we extract the min and return that as a result.

What I don't particularly understand is why this problem is $\mathcal{O}(n \lg{(k)})$. For instance, after $\mathcal{O}(n)$ creation of the heap, we do an extraction of the minimum $n - k $ times, which would require sifting up in the heap $n - k$ times and hence, shouldn't this solution be $\mathcal{O}(n \lg{(n - k)})$?

Thanks!

New contributor
AbdulSohu is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
0
$\begingroup$

The maximum number of elements in the heap at any given time is upper bounded by $k+1$.

Since each insertion or deletion from an heap requires $O(\log \eta)$ time where $\eta$ is the number of elements in the heap at the time of the operation, and $\eta \le k+1$, we know that each heap operation can be performed in time $O(\log (k+1) ) = O( \log k )$.

How many heap operations does the algorithm perform? Each element is inserted once, so there are $n$ insertions. In addition all but the largest $k-1$ elements are extracted. This yields a total of $n + (n-(k-1)) = 2n-k+1 = O(n)$ operations.

By multiplying the number of operations with our upper bound on the time required by each operation of $O(\log k)$ we obtain an overall time complexity of $O(n \log k)$.

$\endgroup$

Your Answer

AbdulSohu is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.