Kth Largest Element in an Array
Description
Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element. Duplicate values count separately — for example, in the array [3, 3, 2], the 1st largest is 3, and the 2nd largest is also 3.
The challenge: can you solve it without fully sorting the array?
Examples
Example 1
Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5
Explanation: Sorting the array in descending order gives [6, 5, 4, 3, 2, 1]. The 2nd element is 5, so we return 5.
Example 2
Input: nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
Output: 4
Explanation: Sorting in descending order gives [6, 5, 5, 4, 3, 3, 2, 2, 1]. The 4th element is 4. Notice that duplicates are counted separately — both 5s occupy positions 2 and 3.
Example 3
Input: nums = [1], k = 1
Output: 1
Explanation: There is only one element, so the 1st largest is 1 itself.
Constraints
- 1 ≤ k ≤ nums.length ≤ 10^5
- -10^4 ≤ nums[i] ≤ 10^4
Editorial
Brute Force
Intuition
The most direct way to find the kth largest element is to sort the entire array and then simply pick the element at the appropriate position.
Imagine you have a shelf of books with different heights, and you want to find the 3rd tallest. The simplest approach: arrange all books from tallest to shortest, then count to the 3rd one. That is exactly what sorting does — it puts every element in its correct position so we can directly index into the answer.
If we sort in descending order, the answer is at index k - 1. Equivalently, if we sort in ascending order, the answer is at index n - k (where n is the array length).
Step-by-Step Explanation
Let's trace through with nums = [3, 2, 1, 5, 6, 4], k = 2:
Step 1: Start with the unsorted array: [3, 2, 1, 5, 6, 4]. We need the 2nd largest element.
Step 2: Sort the array in ascending order: [1, 2, 3, 4, 5, 6].
Step 3: We want the kth largest. In ascending order, the kth largest is at index n - k = 6 - 2 = 4.
Step 4: Look up index 4: nums[4] = 5.
Step 5: Return 5. To verify: in descending order [6, 5, 4, 3, 2, 1], the 2nd element is indeed 5.
Sorting Approach — Sort Then Index — Watch how the entire array is sorted, after which we simply look up the element at position n - k to find the kth largest.
Algorithm
- Sort the array in ascending order
- Return the element at index n - k (0-indexed)
Alternatively:
- Sort the array in descending order
- Return the element at index k - 1
Code
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
return nums[nums.size() - k];
}
};class Solution:
def findKthLargest(self, nums: list[int], k: int) -> int:
nums.sort()
return nums[len(nums) - k]class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
}Complexity Analysis
Time Complexity: O(n log n)
Sorting the array of n elements takes O(n log n) using comparison-based sorts like merge sort, quicksort, or Timsort (Python's default). The index lookup is O(1), so sorting dominates.
Space Complexity: O(1) to O(n)
Depends on the sort algorithm used. In-place sorts like heapsort use O(1) extra space. Merge sort uses O(n). Python's Timsort uses O(n) in the worst case. The index lookup itself uses O(1).
Why This Approach Is Not Efficient
Sorting determines the position of every element, when we only need the position of one. With n up to 10^5, sorting costs about 10^5 × 17 ≈ 1.7 × 10^6 operations — fast enough to pass, but conceptually wasteful.
The problem itself asks: "Can you solve it without sorting?" This is a strong hint that better approaches exist. The key insight: we do not need the entire array sorted. We only need to identify which element would sit at the kth position from the end. If we could partially organize the array — just enough to know what belongs at that one position — we could save significant work.
A heap can help us maintain only the top k elements, and a partitioning strategy (Quickselect) can narrow down to the target position even faster.
Better Approach - Min-Heap of Size k
Intuition
Instead of sorting everything, imagine you are a talent scout who needs to find the kth best player in a league of n players. You do not need to rank all n players. Instead, you maintain a "top-k shortlist" — a small group of exactly k candidates.
As you evaluate each player:
- If your shortlist has fewer than k people, add them immediately
- If your shortlist is full, compare the new player against the weakest person on the shortlist. If the new player is better, they replace the weakest candidate
At the end, the weakest person remaining on your shortlist is the kth best overall.
A min-heap of size k implements exactly this strategy. The heap's minimum element is always the weakest candidate in our top-k set. When a new element arrives that is larger than the heap minimum, we remove the minimum and insert the new element. After processing all n elements, the heap's minimum is the kth largest.
Step-by-Step Explanation
Let's trace through with nums = [3, 2, 1, 5, 6, 4], k = 2:
Step 1: Initialize an empty min-heap. We will maintain at most k = 2 elements.
Step 2: Process nums[0] = 3. Heap size (0) < k (2), so insert 3. Heap: [3].
Step 3: Process nums[1] = 2. Heap size (1) < k (2), so insert 2. Heap: [2, 3]. Min = 2.
Step 4: Process nums[2] = 1. Heap size = k. Compare 1 with heap min (2). Is 1 > 2? No. Skip — 1 is not among the top-2 largest elements.
Step 5: Process nums[3] = 5. Compare 5 with heap min (2). Is 5 > 2? Yes. Remove 2, insert 5. Heap: [3, 5]. Min = 3.
Step 6: Process nums[4] = 6. Compare 6 with heap min (3). Is 6 > 3? Yes. Remove 3, insert 6. Heap: [5, 6]. Min = 5.
Step 7: Process nums[5] = 4. Compare 4 with heap min (5). Is 4 > 5? No. Skip.
Step 8: All elements processed. The heap holds [5, 6] — the top 2 largest elements. The heap minimum is 5, which is the 2nd largest. Return 5.
Min-Heap of Size k — Maintaining Top-k Elements — Watch how a min-heap of size k filters the array, keeping only the k largest elements. The heap minimum at the end is the kth largest.
Algorithm
- Create an empty min-heap
- For each element in the array:
- If the heap has fewer than k elements, insert the element
- Else if the element is greater than the heap's minimum:
- Remove the minimum (the weakest top-k candidate)
- Insert the current element
- Else skip the element (it is too small to be in the top-k)
- The heap's minimum is the kth largest element — return it
Code
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
// Min-heap of size k
priority_queue<int, vector<int>, greater<int>> minHeap;
for (int num : nums) {
if (minHeap.size() < k) {
minHeap.push(num);
} else if (num > minHeap.top()) {
minHeap.pop();
minHeap.push(num);
}
}
return minHeap.top();
}
};import heapq
class Solution:
def findKthLargest(self, nums: list[int], k: int) -> int:
# Python's heapq is a min-heap by default
min_heap = []
for num in nums:
if len(min_heap) < k:
heapq.heappush(min_heap, num)
elif num > min_heap[0]:
heapq.heapreplace(min_heap, num)
return min_heap[0]class Solution {
public int findKthLargest(int[] nums, int k) {
// PriorityQueue is a min-heap by default in Java
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
if (minHeap.size() < k) {
minHeap.offer(num);
} else if (num > minHeap.peek()) {
minHeap.poll();
minHeap.offer(num);
}
}
return minHeap.peek();
}
}Complexity Analysis
Time Complexity: O(n log k)
We process each of the n elements once. Each heap operation (insert or remove-min) costs O(log k) because the heap never exceeds size k. Total: n elements × O(log k) per operation = O(n log k). When k is much smaller than n, this is significantly faster than O(n log n).
Space Complexity: O(k)
The heap stores at most k elements at any time. No other data structures grow with input size.
Why This Approach Is Not Efficient
The min-heap approach at O(n log k) is a significant improvement over O(n log n) sorting, especially when k is small. However, it is not optimal.
With n up to 10^5 and k potentially equal to n/2, the cost becomes O(n log(n/2)) ≈ O(n log n) in the worst case — not much better than sorting. The heap processes every single element and performs a logarithmic operation for most of them.
The fundamental limitation: the heap approach examines every element but does not exploit the structure of the problem. It does not use the fact that we are searching for a specific rank position in the array. A partitioning strategy can narrow down to the target position by eliminating half the remaining elements per step, achieving O(n) average time.
Optimal Approach - Quickselect (Partition-Based Selection)
Intuition
Quickselect borrows the core idea from QuickSort — partitioning — but exploits a crucial observation: after one partition, we know exactly which side of the pivot our target element must be on, so we only need to recurse into one half.
Imagine you are looking for a specific book on a library shelf by its ranking (say the 3rd most popular). You pick a random book as a divider, then move all more-popular books to the left and less-popular books to the right. After this single operation:
- If the divider ends up at exactly position 3 → that is your answer
- If the divider is at position 5 → the 3rd most popular must be among the left group (positions 1-4)
- If the divider is at position 1 → the 3rd most popular must be among the right group (positions 2 onwards)
You only rearrange the relevant side, cutting the search space roughly in half each time. On average, you look at n + n/2 + n/4 + ... ≈ 2n elements total, giving O(n) expected time.
We convert "kth largest" to "(n-k)th smallest" (0-indexed) so that we work with standard ascending-order partitioning.
Step-by-Step Explanation
Let's trace with nums = [3, 2, 1, 5, 6, 4], k = 2. We want the (n - k) = 4th index (0-based) in sorted order.
Step 1: Call quickselect on the full range [0, 5]. Choose pivot as the middle element: nums[(0+5)/2] = nums[2] = 1.
Step 2: Partition around pivot 1. Scan from left for elements ≥ 1 (pointer i) and from right for elements ≤ 1 (pointer j).
- i finds nums[0] = 3 (≥ 1), j finds nums[2] = 1 (≤ 1). Since i < j, swap → [1, 2, 3, 5, 6, 4].
- Continue: i finds nums[1] = 2 (≥ 1), j finds nums[0] = 1 (≤ 1). Now i ≥ j, stop. Partition boundary j = 0.
Step 3: Is j (0) < target (4)? Yes → the target is in the right partition. Recurse on [1, 5].
Step 4: Call quickselect on range [1, 5]. Array: [1, 2, 3, 5, 6, 4]. Pivot = nums[(1+5)/2] = nums[3] = 5.
Step 5: Partition around pivot 5 within [1, 5].
- i finds nums[3] = 5 (≥ 5), j finds nums[5] = 4 (≤ 5). i < j → swap → [1, 2, 3, 4, 6, 5].
- Continue: i finds nums[4] = 6 (≥ 5), j finds nums[3] = 4 (≤ 5). i ≥ j, stop. Partition boundary j = 3.
Step 6: Is j (3) < target (4)? Yes → recurse on [4, 5].
Step 7: Call quickselect on range [4, 5]. Array: [1, 2, 3, 4, 6, 5]. Pivot = nums[(4+5)/2] = nums[4] = 6.
Step 8: Partition around pivot 6 within [4, 5].
- i finds nums[4] = 6 (≥ 6), j finds nums[5] = 5 (≤ 6). i < j → swap → [1, 2, 3, 4, 5, 6].
- Continue: i finds nums[5] = 6 (≥ 6), j finds nums[4] = 5 (≤ 6). i ≥ j, stop. Partition boundary j = 4.
Step 9: Is j (4) < target (4)? No → recurse on [4, 4]. Base case: l == r, return nums[4] = 5.
Quickselect — Partition and Recurse on One Side — Watch how Quickselect narrows down to the target position by partitioning the array and recursing into only the half that contains the answer.
Algorithm
- Convert the problem: target_index = n - k (0-indexed position in ascending order)
- Define quickselect(left, right):
- Base case: if left == right, return nums[left]
- Choose a pivot (e.g., the middle element)
- Partition the subarray [left, right] around the pivot using two-pointer scanning:
- Move pointer i right until nums[i] ≥ pivot
- Move pointer j left until nums[j] ≤ pivot
- If i < j, swap nums[i] and nums[j]
- After partition, j marks the boundary
- If j < target_index, recurse on [j + 1, right]
- Else, recurse on [left, j]
- Return quickselect(0, n - 1)
Code
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int n = nums.size();
int target = n - k;
return quickselect(nums, 0, n - 1, target);
}
private:
int quickselect(vector<int>& nums, int left, int right, int target) {
if (left == right) return nums[left];
int pivot = nums[(left + right) / 2];
int i = left - 1, j = right + 1;
while (i < j) {
do { i++; } while (nums[i] < pivot);
do { j--; } while (nums[j] > pivot);
if (i < j) swap(nums[i], nums[j]);
}
if (j < target) {
return quickselect(nums, j + 1, right, target);
}
return quickselect(nums, left, j, target);
}
};class Solution:
def findKthLargest(self, nums: list[int], k: int) -> int:
n = len(nums)
target = n - k
def quickselect(left: int, right: int) -> int:
if left == right:
return nums[left]
pivot = nums[(left + right) // 2]
i, j = left - 1, right + 1
while i < j:
i += 1
while nums[i] < pivot:
i += 1
j -= 1
while nums[j] > pivot:
j -= 1
if i < j:
nums[i], nums[j] = nums[j], nums[i]
if j < target:
return quickselect(j + 1, right)
return quickselect(left, j)
return quickselect(0, n - 1)class Solution {
private int target;
public int findKthLargest(int[] nums, int k) {
target = nums.length - k;
return quickselect(nums, 0, nums.length - 1);
}
private int quickselect(int[] nums, int left, int right) {
if (left == right) return nums[left];
int pivot = nums[(left + right) / 2];
int i = left - 1, j = right + 1;
while (i < j) {
do { i++; } while (nums[i] < pivot);
do { j--; } while (nums[j] > pivot);
if (i < j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
if (j < target) {
return quickselect(nums, j + 1, right);
}
return quickselect(nums, left, j);
}
}Complexity Analysis
Time Complexity: O(n) average, O(n²) worst case
On average, each partition halves the search space. The total work follows the recurrence T(n) = T(n/2) + O(n), which sums to T(n) = n + n/2 + n/4 + ... = 2n = O(n). In the worst case (when the pivot is always the minimum or maximum), the partition only eliminates one element, leading to T(n) = T(n-1) + O(n) = O(n²). Choosing the middle element as pivot (instead of the first or last) mitigates this for many practical inputs.
Space Complexity: O(log n) average, O(n) worst case
The recursion depth is O(log n) on average (each call halves the range) and O(n) in the worst case. This can be reduced to O(1) by using an iterative implementation that replaces recursion with a loop updating left/right bounds.