Kth Largest Element in an Array
Problem
nums and an integer k, return the value
that would sit at position k if the array were sorted in descending order
(duplicates count separately). Can you avoid fully sorting?[3,2,1,5,6,4], k=2Output5[3,2,3,1,2,4,5,5,6], k=4Output41 ≤ k ≤ n ≤ 105 · -104 ≤ nums[i] ≤ 104
Try it yourself
class Solution {
public int findKthLargest(int[] nums, int k) {
}
}
n-k of the sorted array.
A partition step puts one pivot in its final sorted slot — so only recurse into the
one side that contains index n-k (n + n/2 + n/4 … = O(n) on average).Instinct Need the k-th smallest/largest, an unordered top-k, or values grouped into buckets in place - partition around a pivot and chase only one side.
Memory hack Pivot, partition, pick a side - quickselect is quicksort's lazy cousin that only chases the half holding k.
Open the Partitioning & Quickselect guide →Approaches
Brute ForceSort, then Index
O(n log n)Space O(log n)Sort ascending; the k-th largest is then simply nums[n - k]. Sorting
orders everything, which is far more work than finding one rank.
public int findKthLargest(int[] nums, int k) { Arrays.sort(nums); return nums[nums.length - k]; }
One line and safe, but does a full sort for a single answer.
BetterMin-Heap of Size k
O(n log k)Space O(k)Keep the k largest values seen so far in a min-heap. When it
grows past k, evict the smallest. At the end the heap's minimum is exactly
the k-th largest.
public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> heap = new PriorityQueue<>(); // min-heap for (int x : nums) { heap.offer(x); if (heap.size() > k) heap.poll(); // drop the smallest } return heap.peek(); }
Great when k « n or data is streaming; still log k per element.
OptimalQuickSelect (Random Pivot, 3-Way Partition)
O(n) avg, O(n²) worstSpace O(1)Pick a random pivot and split [lo, hi] into
< pivot | = pivot | > pivot (Dutch-flag style). If target index
n-k lands in the middle block, the pivot is the answer; otherwise shrink
to one side. The 3-way split keeps all-equal arrays linear.
public int findKthLargest(int[] nums, int k) { Random rnd = new Random(); int lo = 0, hi = nums.length - 1, target = nums.length - k; while (true) { int pivot = nums[lo + rnd.nextInt(hi - lo + 1)]; int lt = lo, i = lo, gt = hi; // [lo,lt) < p, [lt,gt] == p, (gt,hi] > p while (i <= gt) { if (nums[i] < pivot) swap(nums, lt++, i++); else if (nums[i] > pivot) swap(nums, i, gt--); else i++; } if (target < lt) hi = lt - 1; else if (target > gt) lo = gt + 1; else return pivot; } } private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
Dry run[3,2,1,5,6,4], k=2 → target=4 (pivots 3, 5)
- start3l21564hpivot = 3
- part.2l13645hlt=gt=2; 4 > 2
- shrink2136l45hlo=3, pivot = 5
- part.2134l56hlt=gt=4 = target ✔ 5
Expected linear time, in-place and iterative — the interview favourite.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Sort, then Index | O(n log n) | O(log n) |
| Better | Min-Heap of Size k | O(n log k) | O(k) |
| Optimal | QuickSelect (Random Pivot, 3-Way Partition) | O(n) avg, O(n²) worst | O(1) |
- Mixing up k-th largest (index
n-k) with k-th smallest (k-1). - Fixed first/last pivot — sorted input makes QuickSelect O(n²).
- 2-way partition with many duplicates — degrades to O(n²) (LeetCode has such tests).
- Give the heap solution first; it also works on streams.
- Explain the average O(n): each round keeps about half, n + n/2 + … ≤ 2n.
- Mention that QuickSelect mutates the input — copy it if the caller needs the order.