Given an integer array nums and an integer k, return the kth largest element in the array.
Rank by sorted order, not distinct value — if nums sorted in descending order is [6, 5, 5, 4, ...], the 1st largest is 6, the 2nd largest is 5, and the 3rd largest is also 5 (the second copy), not 4. Equivalently, it's the element that lands at index k - 1 after sorting nums in descending order.
You must solve it without sorting the whole array whenever possible — a full O(n log n) sort works, but the intended solution runs faster on average.
Example
Sorted descending: [6, 5, 4, 3, 2, 1]. The 2nd largest is 5.
Constraints
- 1 <= k <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
Intuition
A first pass just fully sorts the array, then reads off the value that ends up k slots from the end.
function findKthLargest(nums, k) {
// Sort ascending on a copy, so the input array isn't mutated.
const sorted = [...nums].sort((a, b) => a - b);
// The kth largest lands at this index once everything is fully ordered.
return sorted[sorted.length - k];
}This is O(n log n) — and it computes a strict order for every element, even though the question only ever asks for the one value sitting at a single rank. Can we do better?
The key move: reuse the same partition step Sort an Array's quicksort uses — pick a pivot and, in one pass, split everything ≤ it from everything > it, which drops the pivot into its final sorted position. Quicksort then recurses into both halves to finish ordering the whole array; quickselect recurses into only one — whichever half contains the target rank — and throws the other half's internal order away entirely, since it was never asked for.
Every partition reveals the pivot's exact final rank for free: the position it lands at (pivotIndex, the count of everything ≤ it) is that rank. Compare it to targetIndex — nums.length - k, the index the kth largest would sit at if the array were fully sorted ascending. If they match, the pivot itself is the answer; otherwise targetIndex lies entirely on one side, so recurse into only that side.
Discarding half the remaining work at every round, instead of recursing into both halves, is the same win Binary Search gets from halving a search range each step — except here each discarded half is an unsorted partition rather than a single midpoint check. Expected: each partition costs O(size of its range), and that range is expected to shrink by a constant factor every round — n + n/2 + n/4 + … — a geometric series that sums to O(n) total, instead of the O(n) per level × O(log n) levels a full sort pays for touching both halves every time.
In the stored solution, low/high bound the current search range, pivotIndex is what partition returns (called boundary inside partition itself), and targetIndex is fixed once at the top as nums.length - k. The walkthrough below marks only the pivot directly (as pivot) and narrates low/high/pivotIndex/targetIndex in the captions, so the names line up when you get to the code. Walking it through:
findKthLargest([9, 3, 7, 1, 8, 2], k = 2) — targetIndex = nums.length - k = 4
We want the value that lands at index 4 once nums is sorted ascending — the 2nd largest. Partition around a random pivot; quickselect will only ever look at the side that could contain index 4, never both.
after partitioning around 7 — pivotIndex = 3
One pass swapped everything ≤ 7 ahead of the boundary; 7 itself lands at index 3. That position is 7's exact sorted rank, revealed for free — neither side has been sorted, only separated.
Index 4 sits to the right of the pivot, so the answer lives in the right partition. The left partition [3, 2, 1] is discarded completely — its internal order is never computed, which is exactly the work a full sort would have wasted.
partition low=4..high=5 around 9 — pivotIndex = 5
Only two elements remain in range. The pass confirms 9 is already in its final position at index 5 — pivotIndex = 5.
Index 4 sits to the left of this pivot, so narrow again — this time down to the single index 4.
low === high === 4 — done
The range has shrunk to one element: nums[4] = 8. That's the 2nd largest of the original array, reached in two partition rounds — the left partition's order was never needed.
Optimization
Quickselect (randomized partition)
Sorting the whole array to answer "what's the kth largest" is O(n log n) but wasteful — we don't actually need the other elements in order, just the one at the target rank. Quickselect adapts quicksort's partition step to find a single rank in expected O(n) time: partition around a pivot, then — unlike quicksort — recurse into only the side that contains the target index, discarding the other side entirely.
The kth largest is the element at index nums.length - k once the array is sorted ascending, so the algorithm is really "find the element at that index" (a selection problem), phrased with a target rank rather than a target value.
Partitioning: pick a random pivot index (swapped to the end), then do a Lomuto-style single pass, moving every element <= pivot into a growing prefix. The pivot lands at boundary, its final sorted position. If boundary equals the target index, that's the answer; otherwise recurse into the half — left or right — that contains the target index, and only that half.
Randomizing the pivot matters for the same reason it does in sort-an-array: a fixed pivot choice (e.g. always the last element) has an input that defeats it — an already-sorted or reverse-sorted array makes every partition peel off just one element, degrading to O(n^2). A random pivot makes that adversarial case vanishingly unlikely regardless of the input's initial order.
Expected O(n) time (the classic argument: each partition pass is O(range size) and the range shrinks by a constant factor on average, geometric series sums to O(n)), O(1) extra space (in-place, iterative — no recursion stack growth since only one side is ever explored).
function findKthLargest(nums, k) {
// The kth largest is the element that ends up at this index once nums is sorted ascending.
const targetIndex = nums.length - k;
return quickselect(nums, 0, nums.length - 1, targetIndex);
}
// Finds the value that belongs at nums[targetIndex] if nums[low..high] were fully sorted,
// without sorting the whole range — only ever recurses into the side containing targetIndex.
function quickselect(nums, low, high, targetIndex) {
while (true) {
if (low === high) return nums[low];
const pivotIndex = partition(nums, low, high);
if (pivotIndex === targetIndex) return nums[pivotIndex];
if (targetIndex < pivotIndex) {
high = pivotIndex - 1;
} else {
low = pivotIndex + 1;
}
}
}
// Lomuto partition around a randomly chosen pivot. Returns the pivot's final (sorted) index.
function partition(nums, low, high) {
const randomIndex = low + Math.floor(Math.random() * (high - low + 1));
swap(nums, randomIndex, high);
const pivotValue = nums[high];
let boundary = low;
for (let i = low; i < high; i++) {
if (nums[i] <= pivotValue) {
swap(nums, i, boundary);
boundary++;
}
}
swap(nums, boundary, high);
return boundary;
}
function swap(nums, i, j) {
const temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}Min-heap of size k
Walk the array maintaining a min-heap capped at size k: push each value, and whenever the heap exceeds k elements, pop the smallest. After processing every element, the heap holds exactly the k largest values seen, and its root (the smallest of that set) is the kth largest overall.
This avoids mutating the input (unlike quickselect's in-place partitioning) and is a natural fit when nums arrives as a stream rather than a fixed array. O(n log k) time, O(k) extra space — better than quickselect's O(n) average when k is small relative to n, worse when k is close to n.
function findKthLargest(nums, k) {
const heap = []; // binary min-heap, stored as an array; heap[0] is always the smallest element in it
// Restore the heap property upward from index: swap a too-small value up past its larger parents.
const siftUp = (index) => {
while (index > 0) {
const parent = (index - 1) >> 1;
if (heap[parent] <= heap[index]) break; // parent already smaller — heap property holds
[heap[parent], heap[index]] = [heap[index], heap[parent]];
index = parent;
}
};
// Restore the heap property downward from index: swap a too-large value down past its smaller children.
const siftDown = (index) => {
const size = heap.length;
while (true) {
const left = index * 2 + 1;
const right = index * 2 + 2;
let smallest = index;
if (left < size && heap[left] < heap[smallest]) smallest = left;
if (right < size && heap[right] < heap[smallest]) smallest = right;
if (smallest === index) break; // already smaller than both children — done
[heap[smallest], heap[index]] = [heap[index], heap[smallest]];
index = smallest;
}
};
for (const value of nums) {
// Add the value, then evict the current minimum the instant the heap grows past k —
// this keeps only the k largest values seen so far, never more.
heap.push(value);
siftUp(heap.length - 1);
if (heap.length > k) {
heap[0] = heap[heap.length - 1]; // move the last leaf to the root...
heap.pop();
siftDown(0); // ...then sift it down to restore the heap property
}
}
// The heap holds exactly the k largest values; its root is the smallest of that set — the kth largest overall.
return heap[0];
}Complexity analysis
Time complexity: O(n) expected. Here's why:
- Each call to
partitionmakes a single O(range size) pass over thelow..highwindow it's given. - With a randomized pivot, each partition is expected to roughly halve the size of the remaining search range.
- Only one side is ever recursed into, so the work across rounds is n + n/2 + n/4 + … — a geometric series that sums to O(n) total, not the O(n) per level × O(log n) levels a full sort pays for.
So the expected running time is O(n). An unlucky sequence of random pivots can still degrade toward O(n²) — for example if every partition happened to peel off only one element — but with a random pivot on every call no fixed input can force that; it only happens by chance, with vanishing probability as n grows.
Space complexity: O(1) expected extra space. Here's why:
partitionrearrangesnumsin place — no auxiliary array is built.quickselectis written as a loop that reassignslow/high, not a recursive call, so narrowing the range doesn't grow any call stack — unlike quicksort, which keeps a stack frame per recursion level since it recurses into both sides.
So beyond a handful of loop variables, the optimal solution uses O(1) space — better than the brute force's O(n) for the sorted copy (plus the sort's own O(log n) call-stack space).
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| nums = [42], k = 1 | 42 | Single element — k must be 1, and it's trivially the answer. |
| nums = [5,9], k = 2 | 5 | Two elements, k = length — the smallest value is the worst rank, found in one partition pass. |
| nums = [6,6,6,3,3,9,9,1], k = 4 | 6 | Duplicates clustered right at the target rank — three 6s straddle position 4, but the sorted position (not the value) decides which copy is returned. |
| nums = [3,3,3,3], k = 2 | 3 | All-equal — every partition round is a wash, since everything is simultaneously ≤ and ≥ the pivot. |
| nums = [-5,-2,-9,-1,-7], k = 1 | -1 | All negative, k = 1 — asks for the maximum, which is the least-negative value. |
| nums = [8,-3,0,5,-3,2], k = 6 | -3 | k = length asks for the minimum — the search range collapses all the way down to a single index. |
Try it yourself
Write your solution against the real judge before checking the reference.