#215 Kth Largest Element in an Array
frequently reported atMetaAppleWalmartByteDance / TikTokAmazonMicrosoft
the problem
In plain words
Return the kth largest element in the array (in sorted order, not the kth distinct). Try to do it without sorting.
in nums = [3,2,1,5,6,4], k = 2
out 5
in nums = [3,2,3,1,2,4,5,5,6], k = 4
out 4
- 1 ≤ k ≤ nums.length ≤ 10⁵
- -10⁴ ≤ nums[i] ≤ 10⁴
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternTop-k with a size-k heapQuickselect
You don't need the array sorted — only the k largest (heap) or only the position n − k in sorted order (quickselect).
solutions
From brute force to optimal
Sort ascending and read index n − k.
- Copy and sort.
- Return copy[n − k].
Sorting dominates.
The copy (O(log n) if sorting in place).
class Solution { public int findKthLargest(int[] nums, int k) { int[] copy = nums.clone(); Arrays.sort(copy); return copy[copy.length - k]; }}Keep the k largest seen so far; the root is the answer.
- Offer each value.
- If size > k, poll.
- Return peek.
n offers/polls on a heap of ≤ k + 1.
The heap.
class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> heap = new PriorityQueue<>(); // min-heap of the k largest so far for (int x : nums) { heap.offer(x); if (heap.size() > k) heap.poll(); // drop the smallest of k+1 } return heap.peek(); // smallest of the top k }}Dry run
Partition around a random pivot into < | = | >, then continue only in the part containing index n − k.
- target = n − k.
- Pick a random pivot; Dutch-flag partition [lo, hi].
- target in the middle block → pivot is the answer; else shrink to one side.
Expected work n + n/2 + n/4 + … ≈ 2n; a random pivot makes the worst case astronomically unlikely, and three-way partitioning handles many duplicates.
We copy nums to avoid mutating the input; in place it's O(1).
class Solution { private final Random rnd = new Random(42); public int findKthLargest(int[] nums, int k) { int[] a = nums.clone(); int target = a.length - k; // final index of the answer in ascending order int lo = 0, hi = a.length - 1; while (true) { int pivot = a[lo + rnd.nextInt(hi - lo + 1)]; // three-way partition: [lo, lt) < pivot, [lt, gt] == pivot, (gt, hi] > pivot int lt = lo, i = lo, gt = hi; while (i <= gt) { if (a[i] < pivot) swap(a, lt++, i++); else if (a[i] > pivot) swap(a, i, gt--); else i++; } if (target < lt) hi = lt - 1; // answer is in the "less" part else if (target > gt) lo = gt + 1; // answer is in the "greater" part else return a[target]; // target sits in the pivot block } } private static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }}Quickselect dry run
Values lie in [−10⁴, 10⁴]: count them, then walk from the top until k is used up.
- count[x + 10000]++.
- From the largest value down, subtract counts from k.
R = 20001 possible values.
The count array.
class Solution { public int findKthLargest(int[] nums, int k) { final int OFFSET = 10_000; // values are in [-10^4, 10^4] int[] count = new int[2 * OFFSET + 1]; for (int x : nums) count[x + OFFSET]++; for (int v = count.length - 1; v >= 0; v--) { // walk from the largest value down k -= count[v]; if (k <= 0) return v - OFFSET; } throw new IllegalArgumentException("k > n"); }}in the room
How to say it in the interview
talk track
- Offer all three: sort, heap, quickselect — with complexities.
- Code the heap unless they push for O(n); then quickselect, mentioning the random pivot and the O(n²) worst case.
- If data streams in, the heap wins: it doesn't need all values at once.
traps
- Quickselect with a fixed pivot on sorted or all-equal input degrades to O(n²).
- Two-way (Lomuto) partitioning also degrades on arrays full of duplicates — the three-way partition fixes it.
- Off-by-one: the k-th largest sits at index n − k in ascending order, not k or n − k − 1.
- Looking for the kth distinct value — duplicates count separately here.
what they ask next
Follow-ups
Guaranteed O(n) worst case?
Median-of-medians pivot selection gives O(n) worst case, but its constant is large — rarely used in practice.
Kth largest in a stream (LC 703)?
Keep the size-k min-heap between calls; each add is O(log k).
before you submit
Edge cases to test
- k = 1 is the maximum; k = n is the minimum.
- Many duplicates or all values equal: a two-way partition degrades to O(n²) — use three-way.
- Already sorted input with a fixed first/last pivot: O(n²) — pick the pivot at random.
practise next
Similar problems
- #703Kth Largest Element in a StreamEasyin Heaps
- #973K Closest Points to OriginMediumin Heaps
- #912Sort an ArrayMediumin Sorting