Kth Largest Element In An Array

Medium · Heap / Priority Queue

You are given an array of integers and a positive integer k. Return the value that would sit in position k if the array were sorted from largest to smallest, so k=1 gives the maximum. Duplicate values count individually as separate ranks. Do not just sort and take the first element for full credit; think about doing it faster.

Examples

Input:  nums = [3,2,1,5,6,4], k = 2
Output: 5
Why:    Sorted descending: 6,5,4,3,2,1, the 2nd value is 5.

Input:  nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
Why:    Sorted descending: 6,5,5,4,3,3,2,2,1, the 4th value is 4.

Input:  nums = [7], k = 1
Output: 7
Why:    Only one element, so it is both the largest and the kth largest.

Constraints

1 <= nums.length <= 10^5, -10^4 <= nums[i] <= 10^4, 1 <= k <= nums.length

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Kth Largest Element In An Array

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Kth Largest Element In An Array. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.