Kth Largest Element in an Array

Medium Problem 81 of 151 Java and Python

Problem

Given an integer array nums and an integer k, return the k-th largest element in the array: the k-th largest in sorted order, not the k-th distinct value.

Can you do it without 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 ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums[i] ≤ 10⁴

Explanation

Keep only the k largest values seen so far in a min-heap. Its smallest element (the top) is the k-th largest so far. A new number bigger than the top replaces it; smaller numbers can never be in the top k.

Approach 1 · Naive

Sort

Time O(n log n)
Space O(1) extra (sort may use O(log n))

Sort ascending and read index n - k.

Sort nums.
Return nums[n - k].

Java

import java.util.*;

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

Python

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return sorted(nums)[len(nums) - k]

Approach 2 · Optimal

Min-heap of size k

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

Push every number into a min-heap; whenever it grows beyond k, pop the smallest. The top is the answer.

For each number: push it; if the heap size exceeds k, pop.
Return the heap's top.

Java

import java.util.*;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int num : nums) {
            heap.offer(num);
            if (heap.size() > k) {
                heap.poll();
            }
        }
        return heap.peek();
    }
}

Python

import heapq

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        for num in nums:
            heapq.heappush(heap, num)
            if len(heap) > k:
                heapq.heappop(heap)
        return heap[0]

Complexity compared

Approach	Time	Space
Naive Sort	O(n log n)	O(1) extra (sort may use O(log n))
Optimal Min-heap of size k	O(n log k)	O(k)

Key takeaways

k-th largest → min-heap of size k; k-th smallest → max-heap of size k.
Quickselect averages O(n) and is worth mentioning, though its worst case is O(n²).

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem