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

00:00
Testcase

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.

ApproachTimeSpace
SortO(n log n)O(log n)
Min-heap of size kO(n log k)O(k)
Quickselect (average O(n))O(n) average, O(n²) worstO(1)

1Sort

TimeO(n log n)
SpaceO(log n)

Sort ascending and return nums[n - k].

  1. Arrays.sort; return nums[n - k].
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.

  1. For each x: offer(x); if size > k, poll().
  2. 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();
    }
}

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.

  1. target = n - k; partition [lo, hi] around a random pivot.
  2. 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; }
}

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.