Kth Largest Element in an Array
Problem
Given an integer array nums and an integer k, return the kth largest element in the array.
- 1 ≤ k ≤ nums.length ≤ 10⁵
- −10⁴ ≤ nums[i] ≤ 10⁴
Example
nums = [3,2,1,5,6,4], k = 25A brute-force approach would sort the entire array and return the element at index len(nums) - k, which is correct but inefficient for large inputs. Instead, the algorithm maintains a min-heap of size k to track the k largest elements seen so far. For the example, the heap evolves as follows: 1. Insert 3 → heap = [3] 2. Insert 2 → heap = [2,3] 3. Insert 1 → heap = [1,3,2] 4. Insert 5 → heap size exceeds k=2, pop smallest (1), heap = [2,3,5] 5. Insert 6 → pop smallest (2), heap = [3,5,6] 6. Insert 4 → pop smallest (3), heap = [4,5,6] After processing all elements, the heap contains the 2 largest elements [4,5,6], and the smallest element in the heap (4) is the 2nd largest element in the array. The algorithm returns 5, which is the root of the heap after all insertions and removals.
Approach
Straightforward Solution
Sorting the entire array and returning the element at index len(nums) - k is straightforward but requires O(n log n) time, which is inefficient for large arrays.
Core Observation
The kth largest element is the smallest element in the set of the k largest elements. Maintaining a data structure that efficiently tracks the k largest elements allows retrieval of the kth largest in O(1) time after processing.
Path to Optimal
The key recognition signals are 'kth largest element' and 'partial ordering'. These indicate a heap or priority queue approach because a min-heap of size k can maintain the k largest elements seen so far. This avoids sorting the entire array and reduces time complexity to O(n log k).
Optimal Approach
Use a min-heap to store up to k elements. Iterate through nums, pushing each element onto the heap. If the heap size exceeds k, pop the smallest element. After processing all elements, the heap root is the kth largest element. This approach guarantees O(n log k) time and O(k) space.
Time
O(n log k)
Each of the n elements is pushed onto the heap once, and when the heap size exceeds k, the smallest element is popped. Both push and pop operations take O(log k) time, resulting in O(n log k) total time.
Space
O(k)
The heap stores at most k elements at any time, so auxiliary space scales linearly with k, which is typically much smaller than n.
Pattern Spotlight
Heap / Priority Queue (Fixed-Size Min-Heap for Top K Elements)
Maintain a min-heap of size k to track the k largest elements seen so far; the heap root always represents the kth largest element, enabling efficient insertion and removal to discard smaller elements.
Solution
| 1 | import heapq
|
| 2 |
|
| 3 | class Solution:
|
| 4 | def findKthLargest(self, nums: list[int], k: int) -> int:
|
| 5 | min_heap = []
|
| 6 | for num in nums:
|
| 7 | heapq.heappush(min_heap, num)
|
| 8 | if len(min_heap) > k:
|
| 9 | heapq.heappop(min_heap)
|
| 10 |
|
| 11 | return min_heap[0] |
| 1 | import java.util.PriorityQueue; |
| 2 | |
| 3 | class Solution { |
| 4 | public int findKthLargest(int[] nums, int k) { |
| 5 | PriorityQueue<Integer> minHeap = new PriorityQueue<>(); |
| 6 | for (int num : nums) { |
| 7 | minHeap.offer(num); |
| 8 | if (minHeap.size() > k) { |
| 9 | minHeap.poll(); |
| 10 | } |
| 11 | } |
| 12 | return minHeap.peek(); |
| 13 | } |
| 14 | } |
| 1 | #include <vector> |
| 2 | #include <queue> |
| 3 | |
| 4 | using namespace std; |
| 5 | |
| 6 | class Solution { |
| 7 | public: |
| 8 | int findKthLargest(vector<int>& nums, int k) { |
| 9 | priority_queue<int, vector<int>, greater<int>> minHeap; |
| 10 | for (int num : nums) { |
| 11 | minHeap.push(num); |
| 12 | if ((int)minHeap.size() > k) { |
| 13 | minHeap.pop(); |
| 14 | } |
| 15 | } |
| 16 | return minHeap.top(); |
| 17 | } |
| 18 | }; |
| 1 | class Solution { |
| 2 | findKthLargest(nums, k) { |
| 3 | const minHeap = []; |
| 4 | |
| 5 | function heapPush(heap, val) { |
| 6 | heap.push(val); |
| 7 | let i = heap.length - 1; |
| 8 | while (i > 0) { |
| 9 | let parent = Math.floor((i - 1) / 2); |
| 10 | if (heap[parent] <= heap[i]) break; |
| 11 | [heap[parent], heap[i]] = [heap[i], heap[parent]]; |
| 12 | i = parent; |
| 13 | } |
| 14 | } |
| 15 | |
| 16 | function heapPop(heap) { |
| 17 | const top = heap[0]; |
| 18 | const end = heap.pop(); |
| 19 | if (heap.length === 0) return top; |
| 20 | heap[0] = end; |
| 21 | let i = 0; |
| 22 | const n = heap.length; |
| 23 | while (true) { |
| 24 | let left = 2 * i + 1; |
| 25 | let right = 2 * i + 2; |
| 26 | let smallest = i; |
| 27 | if (left < n && heap[left] < heap[smallest]) smallest = left; |
| 28 | if (right < n && heap[right] < heap[smallest]) smallest = right; |
| 29 | if (smallest === i) break; |
| 30 | [heap[i], heap[smallest]] = [heap[smallest], heap[i]]; |
| 31 | i = smallest; |
| 32 | } |
| 33 | return top; |
| 34 | } |
| 35 | |
| 36 | for (const num of nums) { |
| 37 | heapPush(minHeap, num); |
| 38 | if (minHeap.length > k) { |
| 39 | heapPop(minHeap); |
| 40 | } |
| 41 | } |
| 42 | |
| 43 | return minHeap[0]; |
| 44 | } |
| 45 | } |
Step-by-Step Solution
Build and Maintain a Min-Heap of Size k
| 5 | min_heap = []
|
| 6 | for num in nums:
|
| 7 | heapq.heappush(min_heap, num)
|
| 8 | if len(min_heap) > k:
|
| 9 | heapq.heappop(min_heap)
|
Objective
To track the k largest elements efficiently by pushing each number onto a min-heap and removing the smallest when the heap exceeds size k.
Key Insight
A min-heap of size k keeps the k largest elements because when a new element is added, if the heap grows beyond k, the smallest element is removed. This ensures that after processing all elements, the heap contains exactly the k largest elements, with the smallest among them at the root. This approach avoids sorting the entire array and reduces time complexity significantly.
Interview Quick-Check
Core Logic
Push each element onto the min-heap and pop the smallest element if the heap size exceeds k, maintaining the k largest elements.
State & Boundaries
The heap size is always at most k, ensuring O(log k) insertion and removal times.
Common Pitfalls & Bugs
Forgetting to pop the smallest element when the heap size exceeds k leads to incorrect results and increased space usage.
Complexity
This approach achieves O(n log k) time complexity, which is efficient when k is much smaller than n.
Return the kth Largest Element from the Heap Root
| 11 | return min_heap[0] |
Objective
To retrieve the kth largest element by returning the root of the min-heap after processing all elements.
Key Insight
Because the min-heap contains the k largest elements, the smallest among them (the root) is the kth largest element in the entire array. Returning the root is an O(1) operation and completes the solution efficiently.
Interview Quick-Check
Core Logic
Return the root of the min-heap, which represents the kth largest element after all insertions and removals.
State & Boundaries
Ensure the heap is not empty before accessing the root to avoid runtime errors.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
heapq.heappop(min_heap)Remove the smallest element from the heap to maintain size k.
Popping the smallest element ensures the heap only contains the k largest elements, preserving the invariant that the root is the kth largest element.
heapq.heappush(min_heap, num)Push the current number onto the min-heap.
Adding the number to the heap maintains the current set of candidates for the k largest elements, leveraging the heap's O(log k) insertion time.
return min_heap[0]Return the root element of the min-heap as the kth largest element.
The root of the min-heap is the smallest among the k largest elements, which by definition is the kth largest element in the entire array.
min_heap = []Initialize an empty list to serve as the min-heap.
This list will be used with heapq to efficiently maintain the k largest elements seen so far, enabling O(log k) insertions and removals.
if len(min_heap) > k:Check if the heap size exceeds k.
This condition detects when the heap contains more than k elements, indicating that the smallest element must be removed to maintain the heap size constraint.
for num in nums:Iterate through each number in the input array.
Processing each element ensures that all candidates are considered for inclusion in the heap of k largest elements.
Test Your Understanding
Why does maintaining a min-heap of size k guarantee that the root is the kth largest element?
Because the heap always contains the k largest elements seen so far, the smallest among them (the root) is the kth largest overall; any smaller element is discarded, ensuring the heap root accurately reflects the kth largest.
Related Problems
Heaps pattern
Don't just read it. Drill it.
Reconstruct Kth Largest Element in an Array from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Kth Largest Element in an Array drill