215. Kth Largest Element in an Array
Asked at Meta, Walmart, LinkedIn, Flipkart
Difficulty
Medium
Time
O(n log k)
Space
O(k)
Pattern
Array
Companies
4
Problem
You are given an integer array nums and an integer k. Return the k-th largest value in the array.
"k-th largest" means the value that sits at position k when you sort the array from big to small. It is not the k-th different value — duplicates count as separate elements. For example, in [5,5,4] the 2nd largest is 5, not 4.
You may solve it any way you like. Sorting the whole array works, but a heap of size k or the quickselect algorithm is faster because you never need the full order.
The k-th largest, not the k-th distinct
Constraints
- ●
1 <= k <= nums.length <= 10^5 - ●
-10^4 <= nums[i] <= 10^4
Examples
nums = [3,2,1,5,6,4], k = 25nums = [3,2,3,1,2,4,5,5,6], k = 44Asked At
4 companies| Company | Difficulty | |
|---|---|---|
| Meta | Medium | View all Meta questions → |
| Walmart | Medium | View all Walmart questions → |
| Medium | View all LinkedIn questions → | |
| Flipkart | Medium | View all Flipkart 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).
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).
Keep a min-heap of the k biggest values
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
O(n log k) timeimport 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 runs in O(n log k) time and O(k) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Kth Largest Element in an Array?
Kth Largest Element in an Array is asked at Meta, Walmart, LinkedIn, Flipkart. 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.