Kth Largest Element in an Array
Problem statement
You are given an array of integers nums and a number k. Return the k-th largest value, as it would appear if you sorted the array from biggest to smallest.
Duplicates count separately. In [5, 5, 3] the largest is 5, the second largest is also 5, and the third largest is 3. You are not asked for the k-th distinct value.
Think of a list of response times in milliseconds. "The 2nd slowest request" is the 2nd largest value in that list.
Examples
Example 1
Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5
Explanation: Sorted from biggest to smallest the array is [6, 5, 4, 3, 2, 1]. The 1st largest is 6 and the 2nd largest is 5.
Example 2
Input: nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
Output: 4
Explanation: Sorted from biggest to smallest the array is [6, 5, 5, 4, 3, 3, 2, 2, 1]. Duplicates count, so the 1st to 4th largest are 6, 5, 5 and 4. The answer is 4.
Hints
Approach
Optimal: Quickselect
Intuition
Quickselect is quicksort with a shortcut. Pick a pivot value, and split the values into three groups: bigger than the pivot, equal to the pivot, and smaller than the pivot.
Now count. Say there are 3 bigger values and the pivot has no duplicates.
- If
kis 3 or less, the k-th largest is inside the bigger group. We throw the rest away and search only the bigger group. - If
kfalls inside the "equal" group, the pivot itself is the answer. - Otherwise the answer is in the smaller group. We reduce
kby the number of values we just skipped and search the smaller group.
Each round throws away a good part of the list, so we never sort anything. That is why the average cost is O(n).
We pick the pivot at random so that no fixed input can always make us unlucky. We use a separate "equal" group so that an array full of the same number finishes in one round instead of looping.
Steps
- Start with
currentas the whole array. - Pick a random value from
currentas the pivot. - Split
currentintobigger(above the pivot),equal(same as the pivot) andsmaller(below the pivot). - If
kis at most the size ofbigger, setcurrent = biggerand go back to step 2. - Else if
kis at most the size ofbiggerplus the size ofequal, return the pivot. - Otherwise subtract the size of
biggerandequalfromk, setcurrent = smallerand go back to step 2.
Dry run
nums = [3, 2, 1, 5, 6, 4], k = 2
The pivot is random. Here we assume the first pivot is 3 and the second is 5. Any other choice gives the same final answer.
| round | current | pivot | bigger | equal | decision |
|---|---|---|---|---|---|
| 1 | [3, 2, 1, 5, 6, 4] | 3 | [5, 6, 4] (3 items) | 1 item | k = 2 is at most 3, so keep bigger |
| 2 | [5, 6, 4] | 5 | [6] (1 item) | 1 item | k = 2 is at most 1 + 1, so return 5 |
The answer is 5.
Edge cases: an array with one value returns that value in the first round. An array where every value is equal, like [7, 7, 7], ends in one round because all values fall in the equal group. A negative value works the same as any other number.
Complexity
Time O(n) - on average - Each round picks a random pivot and scans the current list once. On average the pivot splits the list so the next round has about half as many items. The work is n + n/2 + n/4 + ..., which adds up to about 2n. The worst case is O(n²) if the pivots are always unlucky, but a random pivot makes that extremely unlikely.
Space O(n) - Each round builds new lists for the bigger and smaller values. The first round copies up to n values, and later rounds are smaller. An in-place version can use O(1) extra space, but it is harder to read.
import random
class Solution:
def findKthLargest(self, nums: list[int], k: int) -> int:
current = nums
while True:
pivot = random.choice(current)
bigger = [x for x in current if x > pivot]
equal = [x for x in current if x == pivot]
if k <= len(bigger):
current = bigger
elif k <= len(bigger) + len(equal):
return pivot
else:
k -= len(bigger) + len(equal)
current = [x for x in current if x < pivot]
if __name__ == "__main__":
print(Solution().findKthLargest([3, 2, 1, 5, 6, 4], 2)) # 5
print(Solution().findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)) # 4RecapThe whole problem in a few lines, for the night before
- Spot it: the k-th biggest (or top k) value, and you do not need the whole list sorted
- Idea: keep a min-heap of the k biggest values seen so far; its top is the answer (quickselect gives O(n) on average)
- Cost: O(n log k) time, O(k) space for the heap
- Trap: use a min-heap, not a max-heap; duplicates count separately; k = 1 is just the maximum
Interview follow-ups
The numbers arrive one at a time as a stream. How do you report the k-th largest after each new number?
Keep the min-heap of size
kbetween calls. For each new number, push it, and if the heap has more thankitems, pop the smallest. Then the top of the heap is the current k-th largest. Each update costs O(log k), and memory stays at O(k) no matter how long the stream runs. This is the problem Kth Largest Element in a Stream.How would you find the k-th smallest instead?
Flip the idea. With sorting, read index
k - 1from the small end. With a heap, use a max-heap of sizek, and drop the biggest item whenever it grows pastk. With quickselect, compare with<instead of>. The cost stays the same.Can you guarantee O(n) time in the worst case, not just on average?
Yes, with the "median of medians" method, which picks a pivot that is always good enough to shrink the list by a fixed fraction. It is rarely used in practice because the constant factors are large and the code is long. In most real work the min-heap, with its guaranteed O(n log k), or random quickselect is the better choice.
Frequently asked questions
The heap's job is to throw away the value we no longer need. We keep the k biggest values, so the one we want to drop is the smallest of them. A min-heap hands us that smallest value instantly. A max-heap would give us the biggest value, which is the wrong one to remove.
Many times. The array [5, 5, 3] has a 1st largest of 5, a 2nd largest of 5 and a 3rd largest of 3. Sorting, the heap and quickselect all treat each copy as its own value, so you do not need any special handling.
Start with sorting, because it is correct and takes one line. Then say you can do better and show the min-heap, which is simple and has a guaranteed O(n log k) cost. Mention quickselect as the average O(n) option and explain its worst case. This shows you know the trade-offs, which is what the interviewer wants to hear.
A fixed pivot, such as always the first value, can be forced into O(n²) by a sorted input. A random pivot makes a bad run very unlikely. The "equal" group makes sure that many repeated values do not cause long loops, because all copies of the pivot are handled in one go.
Finding the k-th largest is how you compute a percentile or a "top k" over metrics. Examples are the 2nd slowest request, the 5 busiest hosts or the 10 biggest log files. The heap idea also drives live dashboards, where new numbers arrive all the time and you cannot sort everything again.
