Kth Largest Element in an Array
Asked at Meta, Walmart
Problem
Find the kth largest element in an unsorted array. Note that it is the kth largest in sorted order, not the kth distinct element. This problem tests your knowledge of Quickselect and heap-based selection algorithms.
Asked At
| Company | Difficulty | |
|---|---|---|
| Meta | Medium | View all Meta questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
Brute force: sort the array in descending order and return the element at index k-1. Time: O(n log n). Works but wastes time sorting everything when you only need one element.
Min-heap approach: maintain a min-heap of size k. Push each element. If heap size exceeds k, pop the smallest. At the end, the heap root is the kth largest. Time: O(n log k), space: O(k). Good when k is small relative to n.
Quickselect (optimal): like quicksort but only recurse into the partition that contains the kth element. Average O(n) time, worst case O(n²) (mitigated by random pivot). Space: O(1).
Visual walkthrough for nums = [3,2,1,5,6,4], k = 2 (min-heap of size 2):
- Push 3: heap = [3]
- Push 2: heap = [2, 3]
- Push 1: heap size > 2, pop 1. heap = [2, 3]
- Push 5: heap size > 2, pop 2. heap = [3, 5]
- Push 6: heap size > 2, pop 3. heap = [5, 6]
- Push 4: heap size > 2, pop 4. heap = [5, 6]
Root = 5. Result: 5 (2nd largest)
Quickselect walkthrough for same array, k = 2 (find 2nd largest = index n-k = 4 in sorted order):
Pivot = 3 (random). Partition: [2,1,3] [4] [5,6]
Pivot index = 3. Target index = 4. Recurse right: [5,6]
Pivot = 5. Partition: [] [5] [6]. Pivot index = 4. Found at index 4. Result: 5.
Optimal Approach
Min-heap approach: build a min-heap of size k from the first k elements. For each remaining element, if it is larger than the heap root, replace the root and heapify. The heap root at the end is the kth largest element.
Walkthrough with nums = [3,2,1,5,6,4], k = 2:
- Build heap from [3,2]: min-heap = [2,3]
- 1 < 2: skip. Heap = [2,3]
- 5 > 2: replace. Heap = [3,5]
- 6 > 3: replace. Heap = [5,6]
- 4 < 5: skip. Heap = [5,6]
- Root = 5. Result: 5
Quickselect approach: find element at index n-k (0-indexed from smallest). Partition around a random pivot. If pivot index == target, return. If pivot index < target, recurse right. If pivot index > target, recurse left.
Time: heap is O(n log k), quickselect is O(n) average. Space: heap is O(k), quickselect is O(1).
What Trips People Up in Real Interviews
Confusing kth largest with kth smallest. kth largest = element at index n-k in sorted order, or use min-heap of size k. If the problem meant kth smallest, you would use a max-heap of size k.
Using a max-heap and popping k times. That is O(n + k log n) which works but is less efficient than a min-heap of size k when k is small. Mention the tradeoff.
Quickselect worst case: if you always pick the worst pivot (smallest or largest element), it degrades to O(n²). Always use random pivot selection to avoid this in practice.
Not handling duplicates. The problem says kth largest, not kth distinct. Duplicates count toward the ranking. [3,3,3] with k=1 gives 3, k=2 gives 3, k=3 gives 3.
Forgetting that Quickselect modifies the array in-place. If the interviewer asks to preserve the original, you need to copy first or use a different approach.
Solution Code
import heapq
def findKthLargest(nums, k):
min_heap = nums[:k]
heapq.heapify(min_heap)
for num in nums[k:]:
if num > min_heap[0]:
heapq.heapreplace(min_heap, num)
return min_heap[0]Frequently Asked Questions
What is the Kth Largest Element in an Array problem?
Find the kth largest element in an unsorted array. Note that it is the kth largest in sorted order, not the kth distinct element. This problem tests your knowledge of Quickselect and heap-based selection algorithms.
How do you solve Kth Largest Element in an Array?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Kth Largest Element in an Array?
Kth Largest Element in an Array is asked at Meta, Walmart. It is a medium difficulty problem.
What are common mistakes on Kth Largest Element in an Array?
- Confusing kth largest with kth smallest. kth largest = element at index n-k in sorted order, or use min-heap of size k. If the problem meant kth smallest, you would use a max-heap of size k.
- Using a max-heap and popping k times. That is `O(n + k log n)` which works but is less efficient than a min-heap of size k when k is small. Mention the tradeoff.
- Quickselect worst case: if you always pick the worst pivot (smallest or largest element), it degrades to `O(n²)`. Always use random pivot selection to avoid this in practice.
- Not handling duplicates. The problem says kth largest, not kth distinct. Duplicates count toward the ranking. `[3,3,3]` with k=1 gives 3, k=2 gives 3, k=3 gives 3.
- Forgetting that Quickselect modifies the array in-place. If the interviewer asks to preserve the original, you need to copy first or use a different approach.