Solution: Kth Largest Element in an Array

Let's solve the Kth Largest Element in an Array problem using the Top K Elements pattern.

Statement

Find the kthk^{th} largest element in an unsorted array.

Note: We need to find the kthk^{th} largest element in the sorted order, not the kthk^{th} distinct element.

Constraints:

  • 11 \leq k \leq nums.length 103\leq 10^3

  • 104-10^4 \leq nums[i] 104\leq 10^4

Solution

We can use a min-heap to efficiently return the kthk^{th} largest number from our unsorted array. Min-heap ensures the minimum element is always at the root, and it will keep the kk largest elements on top. Once we have inserted all the elements from the array onto the min-heap, we can simply return the root as our kthk^{th} largest element.

The algorithm above can be broken down into simpler steps as follows:

  • Insert the first kk elements onto the min-heap.

  • For each subsequent element in the array, compare it with the root (minimum element) of the min-heap.

    • If the current element in the array is greater than the root element in our min-heap, remove the root element and insert the current element from the array.

    • Continue inserting and removing elements in the min-heap until we have processed all elements in the array.

  • After processing all the elements, the min-heap will contain the kk largest elements from the input array. The smallest of them, the kthk^{th} largest element, will be at the root of the min-heap.

For a better understanding of the algorithm, let’s look at the illustration below:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.