Kth Largest Element in an Array
You get an array of integers nums and an integer k. Return the k-th largest value in nums: the value at position k, counting from 1, once the array is sorted from largest to smallest.
Equal values count separately. In [5, 5, 1] the largest value is 5 and the second largest is also 5.
Function
- numsinteger-array
- the values to rank
- kinteger
- which largest value to return, 1 for the largest
- Returnsinteger
- the k-th largest value, counting duplicates
Constraints
1 ≤ k ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 104- Equal values count as separate values.
Examples
- Input
- nums = [7, 2, 9, 4, 9, 1]k = 2
- Output
- 9
- Explanation
- From largest to smallest the values are
9, 9, 7, 4, 2, 1. The two 9s count separately, so the second largest is9, not7.
- Input
- nums = [5, -3, 8, 0, 2]k = 4
- Output
- 0
- Explanation
- From largest to smallest the values are
8, 5, 2, 0, -3, and the fourth of them is0.
- Input
- nums = [6]k = 1
- Output
- 6
- Explanation
- With one value and
k = 1, that value is the largest.
Follow-up
Values now arrive one at a time. Can you report the median of all values seen so far after each arrival, in O(log n) time per value?
Hints
Open them one at a time. Each one gives away a little more.
Sorted from largest to smallest, the answer sits at a known position. Which one? And do you need every other value in order to know it?
The k-th largest value is the smallest of the
klargest values. If you keep only theklargest values seen so far, which of them do you compare a new value against?Keep a min-heap of at most
kvalues. A new value replaces the top when it is larger, and the top at the end is the answer. ForO(n)average time, partition around a random pivot as quicksort does and keep only the side that holds indexn-k.
Solution
You need one position of the sorted order, not all n. A min-heap of size k keeps only the values that can still be the answer, and quickselect partitions like quicksort but follows only the side that holds the answer, which brings the average time down to O(n).
Sort and read one position
Intuition
The k-th largest value is defined by the sorted order, so sort and read one position: index k-1 of a largest-first order, or index n-k of a smallest-first order. Sorted largest first, the first example is [9, 9, 7, 4, 2, 1], and index 1 holds the second 9. Every copy of a value keeps its own position.
With n = 10^4 a sort makes about 1.3 × 10^5 comparisons, ordering all n values when one position matters.
Algorithm
- Copy
numsso the caller's array stays as it was. - Sort the copy. Use a numeric comparison; some languages compare numbers as text by default.
- Return index
k-1of a largest-first order, or indexn-kof a smallest-first order.
def findKthLargest(nums, k):
# Largest first: the k-th largest sits at index k-1.
ordered = sorted(nums, reverse=True)
return ordered[k - 1]Keep the k largest in a min-heap
Intuition
The k-th largest value is the smallest of the k largest. So walk through nums once and keep the k largest values seen so far in a min-heap, whose top is that smallest value.
Once the heap holds k values, compare each new x with the top. If x is not larger, k kept values are at least as large, so x can never be the answer. If it is larger, the top drops out of the k largest and x replaces it. In example 2 with k = 4, the top after the first four values is -3; 2 replaces it, and the new top, 0, is the answer.
Each value costs at most one O(log k) heap step: O(n log k) time and O(k) memory.
Algorithm
- Start with an empty min-heap.
- For each value
x, add it while the heap holds fewer thankvalues. - Once it holds
k, replace the top withxonly whenxis larger than the top. - After the last value, return the top of the heap.
import heapq
def findKthLargest(nums, k):
# A min-heap of the k largest values so far; its top is the smallest of them.
heap = []
for x in nums:
if len(heap) < k:
heapq.heappush(heap, x)
elif x > heap[0]:
heapq.heapreplace(heap, x) # drop the top, add x
return heap[0]Quickselect with a three-way partition
Intuition
After one quicksort partition the pivot sits at its final sorted index, though neither side is sorted. In smallest-first order the answer lives at target = n-k, so after each partition you continue only on the side that holds target.
In the first example target is 4. Partitioning around 4 puts 7, 9, 9 at indexes 3 to 5, so you keep that side. Partitioning it around 9 puts both 9s at indexes 4 and 5, and index 4 holds the answer.
A three-way partition groups the values equal to the pivot in [lt, gt], already in sorted place, so target inside it ends the search. A random pivot lands in the middle half half the time, cutting the range to at most three quarters, so the expected work is O(n); the worst case stays O(n²). Partitioning a copy costs O(n) memory.
Algorithm
- Copy
numsintoa, settarget = n-k,lo = 0andhi = n-1. - Pick a random pivot from
a[lo..hi]. - Partition
a[lo..hi]into values below, equal to and above the pivot, leaving the equal values ina[lt..gt]. - If
target < lt, sethi = lt-1; iftarget > gt, setlo = gt+1; otherwise return the pivot. - Repeat from step 2.
import random
def findKthLargest(nums, k):
a = list(nums)
target = len(a) - k # the answer's index once a is sorted smallest first
lo, hi = 0, len(a) - 1
while True:
pivot = a[random.randint(lo, hi)]
# Three-way partition of a[lo..hi]: < pivot, then == pivot, then > pivot.
lt, i, gt = lo, lo, hi
while i <= gt:
if a[i] < pivot:
a[lt], a[i] = a[i], a[lt]
lt += 1
i += 1
elif a[i] > pivot:
a[i], a[gt] = a[gt], a[i]
gt -= 1
else:
i += 1
# Now a[lt..gt] all equal pivot, and they are in their sorted places.
if target < lt:
hi = lt - 1
elif target > gt:
lo = gt + 1
else:
return pivot
Pitfalls and edge cases
- Removing duplicates first. In the first example the answer is
9, but after turning the array into a set it becomes7. - Reading index
n-k-1.kcounts from 1, so the answer is atn-kof a smallest-first order. - Sorting numbers as text. In JavaScript and TypeScript,
[10, 9, 2].sort()gives[10, 2, 9]; pass(a, b) => a - b. - Using a max-heap of size
k. Evicting the largest keeps theksmallest values and returns the k-th smallest. - Quickselect with a two-way partition or a fixed pivot.
10^4copies of7, or a sorted array, shrink the range by one value per round: about5 × 10^7steps.
Frequently asked questions4
What is the time complexity of Kth Largest Element in an Array?
Sorting takes O(n log n) time. A min-heap of size k takes O(n log k) time and O(k) memory. Quickselect with a random pivot takes O(n) time on average and O(n²) in the worst case, which a random pivot makes very unlikely.
Why use a min-heap, not a max-heap, to find the kth largest element?
The value you compare against and evict is the smallest of the k largest, so it must be on top. A max-heap works only if you put all n values in it and pop k-1 times, which needs O(n) memory.
Should I use a heap or quickselect for the kth largest element?
Quickselect is faster on average, O(n), but it needs all values in memory and reorders them. The heap is O(n log k) with no bad worst case, and it works when values arrive one at a time.
Can the kth largest element be found in linear time in the worst case?
Yes. The median-of-medians rule picks a pivot guaranteed to cut off a fixed share of the values, making selection O(n) in the worst case, though slower in practice. With values from -10^4 to 10^4, counting each value also works in linear time.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def findKthLargest(nums, k):
# Write code hereTest #1
Test #2
Test #3
Arguments
nums = [7, 2, 9, 4, 9, 1] k = 2
Expected Output
9