Kth Largest Element in an Array
Last Updated: April 3, 2026
Understanding the Problem
We have an array of integers and need to find the kth largest element. Not the kth distinct largest, just the kth from the top if you were to sort the array in descending order. So if the array has duplicates, they each count as separate positions.
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. This is one of the most classic interview problems, and interviewers expect you to know multiple approaches with different trade-offs.
Key Constraints:
1 <= k <= nums.length <= 10^5→ n can be up to 100,000, so O(n^2) worst case is risky. We should aim for O(n log n) or better. An O(n) average-case solution would be ideal.-10^4 <= nums[i] <= 10^4→ Values range from -10,000 to 10,000. This limited range opens up counting-based approaches. The total range is only 20,001 distinct values.k <= nums.length→ k is always valid, so we don't need to handle the case where k is larger than the array.
Approach 1: Sorting
Intuition
The most straightforward way to find the kth largest element: sort the entire array, then just read off the answer. If the array is sorted in ascending order, the kth largest element sits at index n - k. If sorted in descending order, it is at index k - 1.
This is the approach most people think of first, and it is perfectly valid. It is easy to code, easy to verify, and with n up to 10^5, an O(n log n) sort finishes in milliseconds.
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.
We are sorting the entire array just to find one element. What if we only tracked the k largest elements we have seen so far?
Approach 2: Min-Heap
Intuition
Instead of sorting everything, maintain a collection of just the k largest elements seen so far. The smallest element in that collection is the answer: the kth largest overall.
A min-heap of size k is perfect for this. As you scan through the array, you add elements to the heap. Once the heap grows beyond size k, you remove the smallest element. After processing all elements, the heap contains exactly the k largest elements, and the root (the minimum) is the kth largest.
Think of it like a VIP list with k spots. Everyone tries to get in, but only the top k stay. The person at the bottom of the VIP list is the kth most important.
The min-heap acts as a sliding filter. At any point, it holds the k largest elements seen so far. When a new element arrives, it competes for a spot. If it is larger than the current kth largest (the heap root), it pushes that element out and takes its place. If it is smaller, it gets added and immediately removed. By the time we have processed all n elements, the heap contains exactly the k largest from the entire array.
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 great when k is small. But what if we could find the kth largest in O(n) average time by narrowing the search space with each step?
Approach 3: Quickselect
Intuition
Quickselect is based on the same partition idea as quicksort, but with a key twist: instead of recursing into both halves, we only recurse into the half that contains the element we are looking for. This is the same idea behind binary search, applied to an unsorted array using partitioning.
Pick a pivot element and partition the array so everything less than the pivot is on the left, everything greater is on the right. After partitioning, the pivot is in its correct sorted position. If that position matches n - k, we are done. If the pivot ended up too far right, our answer is in the left partition. If too far left, it is in the right partition.
On average, each partition step eliminates about half the remaining elements. So instead of O(n log n) to sort everything, we do O(n) + O(n/2) + O(n/4) + ... = O(2n) = O(n) average work.
The partition step places the pivot in its final sorted position. Every element to the left is smaller, every element to the right is larger. So after one partition, we know exactly where the pivot would be in the fully sorted array, without actually sorting anything else. If the pivot lands at our target index, we are done. Otherwise, we know which half to search, and we can discard the other half entirely. The three-way partition (Dutch National Flag) handles duplicate values efficiently by settling the entire "equal" region in one pass.
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 this extremely unlikely.
- Space Complexity: O(1). The iterative implementation uses constant extra space. We partition in-place and use a loop instead of recursion.