Kth Largest Element in an Array
Understanding the Problem
We have an array of integers and need to find the kth largest element in sorted order, counting by position rather than by distinct value. If the array were sorted in descending order, the answer is the element at position k from the top. Duplicates each count as a separate position.
For example, in [3,2,3,1,2,4,5,5,6], the sorted descending order is [6,5,5,4,3,3,2,2,1]. The 4th largest is 4, even though there are only 6 distinct values.
The problem also hints at solving it without sorting, which suggests there is a more efficient approach than the obvious O(n log n) sort. There are three standard approaches with different trade-offs: full sort, a size-k heap, and quickselect.
Key Constraints:
1 <= k <= nums.length <= 10^5→ n reaches 100,000, so a guaranteed O(n^2) approach is too slow. O(n log n) is safe, and O(n) average is achievable. Since k is always within bounds, there is no invalid-k case to handle.-10^4 <= nums[i] <= 10^4→ Values span only 20,001 distinct integers, which makes counting-based approaches viable as an alternative.
Approach 1: Sorting
Intuition
Sort the entire array, then read off the answer by index. In an ascending sort, the kth largest element sits at index n - k: there are exactly k - 1 elements larger than it, all to its right. In a descending sort, it sits at index k - 1.
This is easy to code and easy to verify, and with n up to 10^5 an O(n log n) sort runs in a few milliseconds. It does more work than needed, since it orders every element when we only want one, but it establishes a correct baseline.
Algorithm
- Sort the array in ascending order.
- Return the element at index
nums.length - k.
Example Walkthrough
Code
- Time Complexity: O(n log n). Sorting dominates. The sort takes O(n log n), and the index lookup is O(1).
- Space Complexity: O(log n). Most built-in sorts use O(log n) stack space for introsort/quicksort.
The next approach avoids ordering the whole array by tracking only the k largest elements seen so far.
Approach 2: Min-Heap
Intuition
Maintain a collection of only the k largest elements seen so far. The smallest element in that collection is the kth largest overall, so once the whole array is processed, that minimum is the answer.
A min-heap of size k fits this exactly, because it gives O(1) access to its minimum and O(log k) insertion. Scan through the array adding each element to the heap. Whenever the heap grows beyond size k, remove the minimum. After all elements are processed, the heap holds the k largest values, and its root is the kth largest.
The invariant is: after processing the first i elements, the heap holds the largest min(i, k) of them. Adding the next element keeps the heap a superset of the true top set by at most one extra value, and removing the minimum discards a value that cannot be among the k largest (k larger or equal values already remain in the heap). The invariant is preserved, so after all n elements the heap holds the k largest of the array and its root is the kth largest.
Algorithm
- Create a min-heap (priority queue).
- Iterate through each number in the array.
- Add the number to the heap.
- If the heap size exceeds k, remove the smallest element (the root).
- After processing all elements, the root of the heap is the kth largest element.
Example Walkthrough
Code
- Time Complexity: O(n log k). We process each of the n elements once. Each heap operation costs O(log k) since the heap never exceeds size k.
- Space Complexity: O(k). The heap stores at most k elements.
The heap approach is O(n log k), which is efficient when k is small. The next approach reaches O(n) average time by partitioning the array and discarding the half that cannot contain the answer at each step.
Approach 3: Quickselect
Intuition
Quickselect uses the same partition step as quicksort but recurses into only one side. After partitioning around a pivot, every element to the left is smaller and every element to the right is larger, so the pivot sits at its final sorted position. If that position is the target index n - k, the pivot is the answer. If the target is to the left, search the left partition; if to the right, search the right partition. The other side is discarded.
Using a three-way partition (Dutch National Flag) splits the range into < pivot, == pivot, and > pivot. This settles every copy of the pivot value in one pass, so arrays with many duplicates do not degrade into repeated partitions over equal elements.
On average each partition discards about half the remaining elements, giving O(n) + O(n/2) + O(n/4) + ... = O(2n) = O(n) average work, compared with O(n log n) to sort everything.
After a three-way partition, the indices [lo, hi] all hold the pivot value and are in their final sorted positions. If targetIndex falls in [lo, hi], every element at those indices equals the pivot, so the pivot value is the answer regardless of which exact index the target is. If targetIndex < lo, the answer lies among the smaller elements in [left, lo-1]; if targetIndex > hi, it lies among the larger elements in [hi+1, right]. Each step strictly shrinks the search range, so the loop terminates.
Algorithm
- Set the target index to
nums.length - k(the position of the kth largest in a sorted array). - Choose a random pivot from the current search range.
- Partition the array: elements less than pivot go left, equal elements go middle, greater go right.
- If the target index falls in the "equal" section, return the pivot.
- If the target index is in the left section, narrow the search to the left portion.
- If the target index is in the right section, narrow the search to the right portion.
- Repeat until found.
Example Walkthrough
Code
- Time Complexity: O(n) average, O(n^2) worst case. On average, each partition reduces the problem size by half: O(n + n/2 + n/4 + ...) = O(2n) = O(n). The worst case occurs when the pivot is always the smallest or largest element. Random pivot selection makes a consistently bad split improbable, so the expected running time stays O(n).
- Space Complexity: O(1). The iterative implementation uses constant extra space. We partition in-place and use a loop instead of recursion.