Find Kth Largest Element in Java
Problem
The kth largest element is the value that would sit in position k if the array were sorted from largest to smallest; duplicates count as separate positions.
Given an unsorted array and a number k, find the kth largest element.
Java Program
import java.util.PriorityQueue;
public class KthLargestHeap {
public static void main(String[] args) {
int[] nums = {12, 5, 27, 8, 19, 3, 27, 14};
int k = 3;
PriorityQueue<Integer> heap = new PriorityQueue<>(); // min-heap holding the k largest seen so far
for (int n : nums) {
heap.offer(n);
if (heap.size() > k) {
heap.poll(); // drop the smallest, keeping only the top k
}
}
System.out.println("Top " + k + " values kept: " + heap.size());
System.out.println(k + "rd largest: " + heap.peek()); // the smallest of the top k
}
}Output
Core Logic
A min-heap capped at k elements always holds the k largest values seen so far, and its smallest member — the root — is the kth largest.
- 1
new PriorityQueue<>()is a min-heap, sopeek()returns its smallest element. - 2Each number is offered to the heap.
- 3Whenever the heap grows past k,
poll()removes the smallest, which can't be among the top k. - 4After the scan, the heap holds the top k values and
peek()is the answer.
Key Point: Using a max-heap of all n elements also works but stores everything; the size-k min-heap keeps memory at O(k), which matters for large inputs or streams.
Why: Each of the n elements causes heap operations on a heap of at most k elements.
Key Concepts
Approach 2: Quickselect
public class KthLargestQuickselect {
public static void main(String[] args) {
int[] nums = {12, 5, 27, 8, 19, 3, 27, 14};
int k = 3;
int target = nums.length - k; // the kth largest sits at this index once sorted ascending
int low = 0, high = nums.length - 1;
while (true) {
int p = partition(nums, low, high);
if (p == target) break;
if (p < target) low = p + 1; // answer is to the right of the pivot
else high = p - 1; // answer is to the left
}
System.out.println(k + "rd largest: " + nums[target]);
}
static int partition(int[] a, int low, int high) {
int pivot = a[high];
int store = low;
for (int i = low; i < high; i++) {
if (a[i] < pivot) {
int t = a[i]; a[i] = a[store]; a[store] = t;
store++;
}
}
int t = a[high]; a[high] = a[store]; a[store] = t;
return store;
}
}
Output
Core Logic
Quickselect uses quick sort's partition step but only continues into the side that contains the wanted position, so on average it does far less work than sorting.
- 1In ascending order, the kth largest sits at index
n - k, calledtarget. - 2
partitionplaces a pivot at its final sorted indexp. - 3If
pequalstarget, the answer is found; otherwise the search continues only to the left or right ofp. - 4The array is rearranged in place, with no extra memory.
Key Point: Average time is O(n), but a consistently bad pivot gives O(n²); choosing a random pivot makes that very unlikely.
Why: Each partition roughly halves the remaining range on average, and everything happens inside the original array.
Key Concepts
Interview Questions
How do you find the kth smallest element instead?
Use a max-heap of size k (new PriorityQueue<>(Collections.reverseOrder())) and drop the largest whenever it grows past k; the top is then the kth smallest.
Do duplicates count as separate positions?
Yes, by the usual definition. In [27, 27, 19], the 2nd largest is 27. Deduplicate first if you want distinct values.