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
PreviewThe 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…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse a min-heap to store up to k elements. Iterate through nums, pushing each element onto the heap…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
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] |
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
To retrieve the kth largest element by returning the root of the min-heap after processing all elements.
1 more step with full analysis available on Pro.
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.
Full line-by-line criticality + rationale for all 6 lines available on Pro.
Test Your Understanding
Why does maintaining a min-heap of size k guarantee that the root is the kth largest element?
See the answer with Pro.
Related Problems
Heap / Priority Queue 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