Kth Largest Element in an Array

Medium Heaps Top K / Kth Largest / Smallest Original on LeetCode

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, 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.

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.

Code

Code appears here once we start writing it.

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 Java code.

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

TimeO(n log n)

SpaceO(log n)

Sort ascending and return nums[n - k].

Arrays.sort; return nums[n - k].

Java

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

2Min-heap of size k

TimeO(n log k)

SpaceO(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().

Java

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();
    }
}

3Quickselect (average O(n))

TimeO(n) average, O(n²) worst

SpaceO(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.

Java

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; }
}

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.

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.