Kth Largest Element in an Array

Given an unsorted integer array, return the kth largest element. The solution should avoid full sorting when possible and use a heap of size k to keep the best candidates.

Input Format

nums = unsorted integer array, k = required rank

Output Format

kth largest value

Constraints

  • 1 <= k <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

Examples

Example 1:

Input:

nums = [3,2,1,5,6,4]
k = 2

Output:

5

Explanation:

The 2nd largest element is 5.

Example 2:

Input:

nums = [3,2,3,1,2,4,5,5,6]
k = 4

Output:

4

Explanation:

After ordering descending, the 4th largest is 4.

Loading...
Kth Largest Element in an Array - Heap