99. Kth Largest Element in an Array

Medium · Heap

Given an unsorted array of integers and an integer k, find the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example, in the array [3, 2, 1, 5, 6, 4], the 1st largest is 6, the 2nd largest is 5, and the 3rd largest is 4.

You may assume k is always valid (1 ≤ k ≤ array length).

Examples

Example 1
Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5
Explanation: After sorting in descending order: [6, 5, 4, 3, 2, 1]. The 2nd largest element is 5.
Example 2
Input: nums = [1], k = 1
Output: 1
Explanation: The array has only one element, which is the 1st largest.

Constraints