Kth Largest Element in an Array

Share

Given an integer array nums and an integer k, return the kth largest element in the array. Note: it is the kth largest in sorted order, not the kth distinct element.

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:

Contents

Approach 1: Sort
Java
public int findKthLargest(int[] nums, int k) {
    Arrays.sort(nums);
    return nums[nums.length - k]; // kth from the end
}

Simple but O(n log n). We can do better.

Approach 2: Min-Heap of size k

Maintain a min-heap of size exactly k. When the heap exceeds k, remove the minimum. At the end, the root of the heap is the k-th largest.

Why? After processing all elements, the heap holds the k largest values. The minimum of those k values (the heap root) is the k-th largest overall.

Java
public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // min at top

    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll(); // remove the smallest, keep top-k
        }
    }
    return minHeap.peek(); // kth largest
}

Complexity Analysis
ApproachTimeSpace
SortO(n log n)O(1)
Min-Heap size kO(n log k)O(k)

Note: Min-heap approach is preferred when k is much smaller than n (streaming data, memory constraints).