Question

Find the kth-largest number in an array of size more than 1,000,000 in O(N).

Answer 1

1. Take a Min Heap of size K.
2. One by one iterate on each element of array. There can be various scenarios as below:
        i) If the heap size is less than k, then insert the element to heap.
        ii) Else, If the element is less than the root node of heap, then ignore it.
        ii) Else, Remove an element from heap, and then add current element to the heap.
3. After pushing k largest element of the array to the heap, We need to get the maximum element from the heap.
4. To get max element of heap, Remove k elements one by one and the last removed element will be our result.

This algorithm is an O(N) algorithm, because K is considered very small compared to N, As N is array size.. So Insertion and deletion from the heap are considered to be O(1), and as the algorithm checks N element, It becomes an O(N) algorithm.

**************************************************

Thanks for your question. We try our best to help you with detailed answers, But in any case, if you need any modification or have a query/issue with respect to above answer, Please ask that in the comment section. We will surely try to address your query ASAP and resolve the issue.

Please consider providing a thumbs up to this question if it helps you. by Doing that, You will help other students, who are facing similar issue.