Heap / Priority Queue · 092Medium
Kth Largest Element in an Array
Given an integer array nums and an integer k, return the kth largest element. This is the kth largest in sorted ORDER, not the kth distinct element.
Constraints
- 1 <= k <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
Examples
findKthLargest([3, 2, 1, 5, 6, 4], 2) -> 5 findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4) -> 4 findKthLargest([1], 1) -> 1 findKthLargest([3, 2, 1, 5, 6, 4], 6) -> 1 // k = n is the minimum findKthLargest([2, 2, 2], 2) -> 2 // duplicates count separately findKthLargest([-1, -5, -3], 1) -> -1 // negatives are allowed
Edge cases
- Duplicates count separately — this is positional, not distinct.
- k = 1 is the maximum; k = n is the minimum.
- FOLLOW-UP
- Sorting works but is not the intended complexity.
Show the target complexity (spoiler)
- Naive
- O(n log n) time — sort descending and index k - 1.
- Target
- O(n log k) with a size-k min-heap, or O(n) average with Quickselect (partition and recurse into one side only).
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/13-heap-priority-queue/092-kth-largest-element-in-an-array.js ./practice c 092