Heaps Top K
407. Kth Largest Element in an Array
You are given an array of integers nums and an integer k. Return the k-th largest element of nums.
The k-th largest element is the one in position k when nums is sorted from largest to smallest,
counting from 1. Equal values take separate places, so in [5,5,1] the first and the second largest are
both 5.
Example 1
Input: nums = [3, 9, -2, 7, 4, 9, 1], k = 3
7Explanation: From largest to smallest the elements are 9, 9, 7, 4, 3, 1, −2. The two 9s take the first two places, so the third largest is 7.
Example 2
Input: nums = [-5, -1, -8, -1], k = 4
-8Explanation: From largest to smallest the elements are −1, −1, −5, −8. When k equals the length of the array, the
answer is the smallest element.
Example 3
Input: nums = [2, 2, 2, 2], k = 3
2Explanation: Every element is 2, so every place holds 2.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 105-109 ≤ nums[i] ≤ 1091 ≤ k ≤ nums.length
Clarifying questions
What you would ask an interviewer before writing any code.