Given an integer array nums and an integer k, return the kth largest element. This means the kth largest in sorted order, not the kth distinct value, so duplicates count separately. Try to do better than sorting the whole array.
Example 1
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Sorted descending: 6, 5, 4, 3, 2, 1. The 2nd one is 5.
Example 2
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
Sorted descending: 6, 5, 5, 4, ... The 4th one is 4.
Constraints
- 1 <= k <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
Hints
Frequently asked at: Meta, Amazon, Microsoft, LinkedIn, Goldman Sachs
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Sorting gives the answer at index n - k in O(n log n). But we never need the full order, only the top k. A min-heap of size k holds the k largest values seen so far, and its smallest element (the top) is exactly the kth largest. Each new number is pushed, and if the heap has more than k items we pop the smallest, so the heap never grows beyond k.
Algorithm
- Create an empty min-heap.
- For each number, push it into the heap.
- If the heap size exceeds
k, pop the smallest element. - After all numbers, return the top of the heap.
Time:
O(n log k)Space: O(k)Interview tip: Interviewers often ask for the average O(n) approach: Quickselect, which partitions like quicksort but recurses into only one side. Mention that its worst case is O(n^2) unless you pick a random pivot.
class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: heap = [] # min-heap of the k largest values for x in nums: heapq.heappush(heap, x) if len(heap) > k: heapq.heappop(heap) # drop the smallest return heap[0]Ctrl + Enter runs the examples