# Solution: Kth Largest Element in an Array

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

We'll cover the following

## Statement

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

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

Constraints:

• $1 \leq$ k $\leq$ nums.length $\leq 10^3$

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

## Solution

We can use a min-heap to efficiently return the $k^{th}$ largest number from our unsorted array. Min-heap ensures the minimum element is always at the root, and it will keep the $k$ 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 $k^{th}$ largest element.

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

• Insert the first $k$ 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 $k$ largest elements from the input array. The smallest of them, the $k^{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.