Kth Largest Element in an Array
Kth Largest Element in an Array is a medium heaps problem solved with the top k / kth largest / smallest pattern.
The best approach, quickselect (average o(n)), runs in O(n) average, O(n²) worst time and O(1) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from sort up.
Problem
Return the k-th largest element of an unsorted array. Duplicates count: it is the element at position k in descending sorted order.
Examples
Example 1
- Input
nums = [3, 2, 1, 5, 6, 4], k = 2- Output
5
Example 2
- Input
nums = [7, 7, 3], k = 2- Output
7- Why
- Duplicates count separately: k-th largest in sorted order, not k-th distinct.
Constraints
1 <= k <= nums.length <= 10^5- Try to beat full sorting.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Sort | O(n log n) | O(log n) |
| Min-heap of size k | O(n log k) | O(k) |
| Quickselect (average O(n)) | O(n) average, O(n²) worst | O(1) |
1Sort
O(n log n)O(log n)Sort ascending and return nums[n - k].
- Arrays.sort; return nums[n - k].
class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
}class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
nums.sort()
return nums[len(nums) - k]class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
return nums[nums.size() - k];
}
};function findKthLargest(nums, k) {
nums.sort((a, b) => a - b);
return nums[nums.length - k];
}2Min-heap of size k
O(n log k)O(k)Push every value into a min-heap and pop whenever it grows past k. The heap always holds the k largest values seen, and its top, the smallest of them, is the k-th largest.
- For each x: offer(x); if size > k, poll().
- Return peek().
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int x : nums) {
heap.offer(x);
if (heap.size() > k) heap.poll();
}
return heap.peek();
}
}class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
heap = []
for x in nums:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap)
return heap[0]class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> heap;
for (int x : nums) {
heap.push(x);
if ((int)heap.size() > k) heap.pop();
}
return heap.top();
}
};class MinHeap {
constructor(cmp = (a, b) => a - b) { this.a = []; this.cmp = cmp; }
size() { return this.a.length; }
isEmpty() { return this.a.length === 0; }
peek() { return this.a[0]; }
push(x) {
const a = this.a;
a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (this.cmp(a[i], a[p]) >= 0) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop() {
const a = this.a, top = a[0], last = a.pop();
if (a.length > 0) {
a[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && this.cmp(a[l], a[m]) < 0) m = l;
if (r < a.length && this.cmp(a[r], a[m]) < 0) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
function findKthLargest(nums, k) {
const heap = new MinHeap();
for (const x of nums) {
heap.push(x);
if (heap.size() > k) heap.pop();
}
return heap.peek();
}3Quickselect (average O(n))
O(n) average, O(n²) worstO(1)Partition around a random pivot like quicksort, but recurse only into the side that contains index n - k. On average the work halves each round.
- target = n - k; partition [lo, hi] around a random pivot.
- If the pivot lands at target, return it; otherwise continue on one side.
class Solution {
private final Random rnd = new Random();
public int findKthLargest(int[] nums, int k) {
int target = nums.length - k, lo = 0, hi = nums.length - 1;
while (true) {
int p = partition(nums, lo, hi);
if (p == target) return nums[p];
if (p < target) lo = p + 1; else hi = p - 1;
}
}
private int partition(int[] a, int lo, int hi) {
swap(a, lo + rnd.nextInt(hi - lo + 1), hi);
int pivot = a[hi], store = lo;
for (int i = lo; i < hi; i++) if (a[i] < pivot) swap(a, i, store++);
swap(a, store, hi);
return store;
}
private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
}import random
class Solution:
def __init__(self):
self.rnd = random.Random()
def findKthLargest(self, nums: List[int], k: int) -> int:
target, lo, hi = len(nums) - k, 0, len(nums) - 1
while True:
p = self.partition(nums, lo, hi)
if p == target:
return nums[p]
if p < target:
lo = p + 1
else:
hi = p - 1
def partition(self, a: List[int], lo: int, hi: int) -> int:
self.swap(a, lo + self.rnd.randrange(hi - lo + 1), hi)
pivot, store = a[hi], lo
for i in range(lo, hi):
if a[i] < pivot:
self.swap(a, i, store)
store += 1
self.swap(a, store, hi)
return store
def swap(self, a: List[int], i: int, j: int) -> None:
a[i], a[j] = a[j], a[i]class Solution {
mt19937 rnd{random_device{}()};
public:
int findKthLargest(vector<int>& nums, int k) {
int target = nums.size() - k, lo = 0, hi = nums.size() - 1;
while (true) {
int p = partition(nums, lo, hi);
if (p == target) return nums[p];
if (p < target) lo = p + 1; else hi = p - 1;
}
}
private:
int partition(vector<int>& a, int lo, int hi) {
swap(a[lo + (int)(rnd() % (hi - lo + 1))], a[hi]);
int pivot = a[hi], store = lo;
for (int i = lo; i < hi; i++) if (a[i] < pivot) swap(a[i], a[store++]);
swap(a[store], a[hi]);
return store;
}
};function findKthLargest(nums, k) {
const target = nums.length - k;
let lo = 0, hi = nums.length - 1;
while (true) {
const p = partition(nums, lo, hi);
if (p === target) return nums[p];
if (p < target) lo = p + 1; else hi = p - 1;
}
}
function partition(a, lo, hi) {
swap(a, lo + Math.floor(Math.random() * (hi - lo + 1)), hi);
const pivot = a[hi];
let store = lo;
for (let i = lo; i < hi; i++) if (a[i] < pivot) swap(a, i, store++);
swap(a, store, hi);
return store;
}
function swap(a, i, j) { const t = a[i]; a[i] = a[j]; a[j] = t; }Edge cases to test
- Duplicates
- k = 1 or k = n
Hints
Hint 1
Keep only the k largest values seen so far. Which of them is the answer?
FAQ
What is the best time complexity for Kth Largest Element in an Array?
Quickselect (average O(n)) runs in O(n) average, O(n²) worst time and O(1) extra space.
Which pattern does Kth Largest Element in an Array use?
It is a heaps problem that uses the top k / kth largest / smallest pattern. Other problems with the same pattern: Kth Largest Element in a Stream, Top K Frequent Words, K Closest Points to Origin.
Is there a brute force solution for Kth Largest Element in an Array?
Yes. Sort takes O(n log n) time and O(log n) space. Sort ascending and return nums[n - k].
Which edge cases should I test for Kth Largest Element in an Array?
Duplicates; k = 1 or k = n.