Problem 14.3 · Sorting and Divide & ConquerMedium

Kth Largest Element in an Array

PatternDivide and Conquer Top K with a Heap

What it teaches: Quickselect: partition once and recurse into only the side that holds the answer, O(n) on average.

Practise it on judges as “Kth Largest Element in an Array”.

The problem

Return the kth largest element of nums (the kth in sorted descending order, counting duplicates), ideally without fully sorting.

Example 1

Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5

Example 2

Input: nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
Output: 4

Constraints

1 ≤ k ≤ n ≤ 10⁵

Pattern clues in the wording

→ Kth largest/smallest
→ Full sort unnecessary

These clues point to Divide and Conquer: Split the input into halves, solve each half recursively, and combine the results.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	nums = [3,2,1,5,6,4] k = 2	5
2	nums = [3,2,3,1,2,4,5,5,6] k = 4	4

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Min-heap of size k · O(n log k)2. Quickselect · O(n) average, O(n²) worst

Min-heap of size k

Time O(n log k) Space O(k)

Keep the k largest seen so far in a min-heap; its top is the answer.

Approach 1

import java.util.PriorityQueue;

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

Verdict: Simple and good for streams.

Quickselect

Time O(n) average, O(n²) worst Space O(1)

Target index t = n − k. Partition with a random pivot; if the pivot lands at t, return it; else continue on the side containing t.

Approach 2

import java.util.concurrent.ThreadLocalRandom;

class Solution {
    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 + ThreadLocalRandom.current().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; }
}

Verdict: Fastest on average.

Before you submit

Edge cases and common mistakes

Test these inputs

k = 1 (maximum)
k = n (minimum)
Many duplicates

Mistakes people make

Confusing kth largest with index k − 1 in ascending order.

Interview

Follow-up questions

Can quickselect be made O(n) worst case?

Command Palette