noodleProblems/
Kth Largest Element in an Array
#161

Kth Largest Element in an Array

AlgorithmmediumArraySortingHeap Priority QueueDivide And Conquer

Given an integer array nums and an integer k, return the kth largest element in the array.

Rank by **sorted order, not distinct value** — if nums sorted in descending order is [6, 5, 5, 4, ...], the 1st largest is 6, the 2nd largest is 5, and the 3rd largest is also 5 (the second copy), not 4. Equivalently, it's the element that lands at index k - 1 after sorting nums in descending order.

You must solve it without sorting the whole array whenever possible — a full O(n log n) sort works, but the intended solution runs faster on average.

Example cases

  • kth largest, no ties
    in nums = [3,2,1,5,6,4], k = 2
    out 5
    Sorted descending: [6, 5, 4, 3, 2, 1]. The 2nd largest is 5.
  • kth largest, duplicates by position
    in nums = [3,2,3,1,2,4,5,5,6], k = 4
    out 4
    Sorted descending: [6, 5, 5, 4, 3, 3, 2, 2, 1]. The 4th position (index 3) holds 4, even though 5 appears twice.

Constraints

  • 1 <= k <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
Saved
nums =
[3,2,1,5,6,4]
k =
2