67.Kth Largest Element in an Array

MediumHeap / Priority Queue · 4/7

Problem

Given an integer array nums and an integer k, return the k-th largest element in the array.

This is the k-th largest in sorted order, not the k-th distinct value — duplicates count. Try to solve it without fully sorting the array.

Examples

Input:  nums = [3,2,1,5,6,4], k = 2
Output: 5
Explanation: Sorted descending: [6,5,4,3,2,1] -> 2nd is 5.

Input:  nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
Explanation: Sorted descending: [6,5,5,4,3,3,2,2,1] -> 4th is 4.

Constraints

1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

💡 Key Insight

The k-th largest is the element that would sit at index n - k in ascending order. We do not need the rest of the order: a size-k min-heap keeps just the top k (O(n log k)), and Quickselect partitions around a pivot and discards the side that cannot contain index n - k, giving O(n) on average.

Brute Force (Sorting)

TimeO(n log n)SpaceO(log n)

Intuition

Sort ascending and read index n - k.

Algorithm

Arrays.sort(nums).
Return nums[nums.length - k].

Visualization

nums = [3,2,1,5,6,4], k = 2
sorted = [1,2,3,4,5,6]
index n-k = 4 -> 5

Code

java

import java.util.Arrays;

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

Complexity

Time: O(n log n) — sorting.
Space: O(log n) — sort recursion stack.

Min-Heap of Size k

TimeO(n log k)SpaceO(k)

Intuition

Maintain the k largest values seen so far in a min-heap. Its root is the smallest of the top k — the current k-th largest. Any value smaller than the root is irrelevant and gets evicted.

Algorithm

For each num: offer(num); if size() > k, poll().
Return peek().

Visualization

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

flowchart LR
    A["3: heap {3}"] --> B["2: heap {2,3}"]
    B --> C["1: push, pop 1<br/>heap {2,3}"]
    C --> D["5: push, pop 2<br/>heap {3,5}"]
    D --> E["6: push, pop 3<br/>heap {5,6}"]
    E --> F["4: push, pop 4<br/>heap {5,6}"]
    F --> G["peek = 5"]

Code

java

import java.util.PriorityQueue;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll(); // remove the smallest of k + 1
            }
        }
        return minHeap.peek();
    }
}

Complexity

Time: O(n log k) — each element costs O(log k).
Space: O(k) — heap size.

Quickselect with 3-Way PartitionOptimal

TimeO(n) averageSpaceO(1)

Intuition

Pick a random pivot and split the current range into three zones: < pivot, == pivot, > pivot (Dutch national flag). After one pass we know the sorted position range [lt, gt] of the pivot value. If target = n - k falls inside it, the pivot is the answer; otherwise continue in only the left or right zone. The 3-way split matters: arrays with many duplicates would make a 2-way partition degrade to O(n²).

Algorithm

target = n - k, lo = 0, hi = n - 1.
Loop:
- pivot = nums[random index in [lo, hi]].
- Partition with pointers lt = lo, i = lo, gt = hi: smaller → swap to lt, larger → swap to gt, equal → i++.
- If target < lt, set hi = lt - 1; if target > gt, set lo = gt + 1; otherwise return pivot.

Dry Run

nums = [3,2,1,5,6,4], k = 2, target = 4

round 1: pivot = 3
  after partition: [2,1 | 3 | 6,4,5]   lt = 2, gt = 2
  target 4 > gt -> lo = 3

round 2: range [3..5] = [6,4,5], pivot = 5
  after partition: [4 | 5 | 6]  -> lt = 4, gt = 4
  target 4 in [lt, gt] -> return 5

Code

java

import java.util.Random;

class Solution {
    private final Random rand = new Random();

    public int findKthLargest(int[] nums, int k) {
        int target = nums.length - k; // index in ascending order
        int lo = 0, hi = nums.length - 1;
        while (true) {
            int pivot = nums[lo + rand.nextInt(hi - lo + 1)];
            int lt = lo, i = lo, gt = hi;
            // invariant: [lo,lt) < pivot, [lt,i) == pivot, (gt,hi] > pivot
            while (i <= gt) {
                if (nums[i] < pivot) {
                    swap(nums, lt++, i++);
                } else if (nums[i] > pivot) {
                    swap(nums, i, gt--); // do not advance i: new nums[i] is unchecked
                } else {
                    i++;
                }
            }
            if (target < lt) {
                hi = lt - 1;
            } else if (target > gt) {
                lo = gt + 1;
            } else {
                return pivot; // target lies in the block of pivot values
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

Complexity

Time: O(n) average — each round keeps an expected constant fraction of the range; O(n²) only with astronomically unlucky pivots.
Space: O(1) — in-place and iterative.

Complexity Comparison

Approach	Time	Space
Sorting	O(n log n)	O(log n)
Min-Heap of Size k	O(n log k)	O(k)
Quickselect (3-way)	O(n) average	O(1)

Common Pitfalls

Off-by-one on the target: the k-th largest is index n - k in ascending order, not k - 1 or n - k - 1.
Using a fixed pivot or a 2-way Lomuto partition — LeetCode includes large inputs of identical values that push that version to O(n²) and time out.
Advancing i after swapping with gt — the element swapped in from the right has not been classified yet.
Deduplicating values: [5,5,4] with k = 2 has answer 5, not 4.