Find the Kth Largest Element in an Array

Title: Find the Kth Largest Element in an Array

In this guide, you’ll learn how to find the K-th largest element in an array using a min-heap of size K. We’ll frame the problem, build a clean solution in Java with PriorityQueue, trace it by hand on a fresh input, and then stress test it against the edge cases that make this a staple interview question at Google, Amazon, and almost every top-tier company.

This problem is the general form of “find the second largest” and “find the third largest” and is explicitly tracked by LeetCode as problem 215. By the end of this article you’ll have a program that runs in O(n log K) time, a mental model for the heap approach, and a working feel for the Quickselect alternative that interviewers love to ask about as a follow-up.

Understanding the Problem

Given an integer array and an integer k, we want to return the K-th largest element in the array in sorted order. By convention here, duplicates count: for {3, 2, 3, 1, 2, 4, 5, 5, 6} with k = 4 the descending sort is 6, 5, 5, 4, 3, 3, 2, 2, 1 and the fourth entry is 4. This is the LeetCode 215 interpretation, which is the one most interviewers expect unless they say otherwise.

The naive approach is to sort the array and index into position n - k, which costs O(n log n) time. We can do better. If we maintain a min-heap of exactly K elements as we scan, the heap always holds the K largest values seen so far, with the smallest of them at the top. After one pass, the top of the heap is the K-th largest overall.

Approach Using a Min-Heap of Size K

We walk through the array once, maintaining a min-heap bounded at size K. The algorithm steps are:

1. Validate that the array is non-null and that 1 <= k <= numbers.length; otherwise throw an exception.
2. Create a min-heap using PriorityQueue, with initial capacity k.
3. Iterate over every element in the array.
4. If the heap holds fewer than K elements, offer the current element to the heap.
5. Otherwise, if the current element is strictly greater than the heap’s top (the current K-th largest candidate), poll the top and offer the current element.
6. Otherwise, the current element cannot be in the top K; skip it.
7. After the loop, return the heap’s top, which is now the K-th largest element.

Java Program

Here is the complete, compilable program that implements the approach above.

import java.util.PriorityQueue;

public class KthLargestElement {
    public static int findKthLargest(int[] numbers, int k) {
        if (numbers == null || k < 1 || k > numbers.length) {
            throw new IllegalArgumentException("Invalid input: k must satisfy 1 <= k <= numbers.length");
        }
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
        for (int i = 0; i < numbers.length; i++) {
            if (minHeap.size() < k) {
                minHeap.offer(numbers[i]);
            } else if (numbers[i] > minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(numbers[i]);
            }
        }
        return minHeap.peek();
    }

    public static void main(String[] args) {
        int[] numbers = {3, 2, 1, 5, 6, 4};
        int k = 2;
        int result = findKthLargest(numbers, k);
        System.out.println("The " + k + "th largest element is: " + result);
    }
}

Explanation of the Program

The guard clause at the top of findKthLargest rejects a null array and any k outside the valid range 1 through numbers.length. Failing fast with IllegalArgumentException is better than silently returning the smallest element for k = 0 or throwing a confusing NoSuchElementException at the final peek.

Java’s PriorityQueue is a min-heap by default, so peek() and poll() both operate on the smallest element currently in the heap. We size the heap with initial capacity k so the internal array does not need to resize during the first K insertions.

Inside the loop, the first branch fills the heap during the warm-up phase while it still holds fewer than K elements. The second branch is the hot path once the heap is full: if the current element beats the heap’s top (which is the smallest of the current top-K candidates), we evict the top and offer the current element. The implicit third case, where the current element is not larger than the top, is handled by doing nothing because the element cannot possibly be in the final top K.

After the loop, the K elements inside the heap are exactly the K largest from the input, and the smallest of them, at the heap’s top, is the K-th largest overall. We return it with a single peek() call in constant time.

Step-by-Step Trace

Let’s run the algorithm on the input {7, 10, 4, 3, 20, 15} with k = 3, which should finish with the heap holding {10, 15, 20} and a top value of 10. Each row below shows the state after that iteration completes.

Invariant: at the end of each iteration, the heap contains the K largest elements seen so far (or all elements seen so far if fewer than K have arrived), with the smallest of them at the top. Iteration 4 is the one worth studying: a small value gets rejected in O(1) via the peek() comparison, which is the whole reason the algorithm beats O(n log n) sorting.

Examples

The following examples show the program behaving on three different shapes of input.

Example 1: The Classic LeetCode Case

int[] numbers = {3, 2, 1, 5, 6, 4};
int result = findKthLargest(numbers, 2);
System.out.println(result);
// Output: 5

The sorted descending view is 6, 5, 4, 3, 2, 1, so the second largest is 5. This is the canonical LeetCode 215 input and output.

Example 2: Duplicates in the Input

int[] numbers = {3, 2, 3, 1, 2, 4, 5, 5, 6};
int result = findKthLargest(numbers, 4);
System.out.println(result);
// Output: 4

Duplicates count: the sorted descending view is 6, 5, 5, 4, 3, 3, 2, 2, 1, so the fourth entry is 4. If you expected 3 here, you were thinking of the “K-th distinct” variant, which is a different problem.

Example 3: All Negative Numbers

int[] numbers = {-1, -5, -3, -2, -4};
int result = findKthLargest(numbers, 2);
System.out.println(result);
// Output: -2

The heap-based algorithm handles negatives naturally because PriorityQueue<Integer> uses the natural ordering of Integer, which honors sign. The sorted descending view is -1, -2, -3, -4, -5, so the second largest is -2.

Common Mistakes to Avoid

These are the specific pitfalls candidates run into while coding this problem under pressure.

• Using a max-heap of size K – feels right for “largest” but ends up requiring k - 1 extra polls at the end to reach the K-th element, and does not let you reject small inputs in O(1). Use a min-heap of size K and return the heap’s top directly.
• Sorting the whole array – works but costs O(n log n); the heap approach is O(n log K), which is a real improvement when K is small relative to n. Interviewers always want the better complexity.
• Confusing K-th largest with K-th distinct largest – the LeetCode convention keeps duplicates, so {5, 5, 5} with k = 2 returns 5. Always clarify the interpretation with the interviewer before coding.
• Using >= instead of > when comparing to peek() – with >=, a duplicate of the current heap top triggers an unnecessary poll and offer, doubling the work on arrays with many duplicates. Keep the comparison strict.
• Reading the heap root before the heap is full – calling peek() inside the first branch where size < k throws NoSuchElementException on the very first iteration. The branch structure prevents this; do not merge the branches during a rewrite.

Edge Cases to Test

Walk through these boundary inputs before claiming the solution is complete. The order below mirrors how often each case shows up in interview grading rubrics.

• K equals 1 (just the maximum)
• K equals the array length (just the minimum)
• K greater than the array length (invalid input)
• K equal to zero or negative (invalid input)
• Empty array
• Single-element array
• All identical elements
• Strictly ascending or strictly descending input
• Multiple duplicates straddling the K-th position
• Integer.MIN_VALUE and Integer.MAX_VALUE present
• Null array reference

Additional Considerations

The heap-based algorithm runs in O(n log K) time: one pass over the array with at most one offer/poll pair per element, each operation costing O(log K). Space usage is O(K) for the heap plus a constant for the loop index and the local variables.

A full sort gives O(n log n) time, which is worse than the heap when K is small, and it mutates the input unless you copy it first. Quickselect using a Dutch National Flag partition runs in expected O(n) time with O(1) extra space (operating in place) but has a pathological O(n squared) worst case without a careful pivot strategy; most interviewers accept Quickselect with random-pivot as the next-level answer.

When K approaches n, the heap approach degrades to O(n log n) and loses its edge. A good rule of thumb: if K <= n / 2, use a min-heap for the K-th largest; otherwise, pivot and use a max-heap of size n - k + 1 to find the K-th largest as the smallest of the “bottom” n - k + 1 values. Interviewers appreciate candidates who notice this asymmetry.

Interview Follow-up Questions

Interviewers almost always probe deeper after the base solution works. Expect variants along these lines.

• Can you do better than O(n log K)? – use the Quickselect algorithm with a random pivot for expected O(n) time; the trade-off is a worst-case O(n squared) and more involved partition logic.
• What if the array arrives as an unbounded stream? – the same min-heap of size K works unchanged; after warm-up, every incoming value is either rejected in O(log K) or replaces the top. Memory stays O(K).
• What if the array has billions of elements spread across many machines? – compute the local top-K on each shard, send the K per-shard values to a coordinator, and run the same algorithm on the merged list of size K * shards; the shard step is embarrassingly parallel.
• What if the interviewer actually wants the K-th distinct largest? – deduplicate on the fly with a HashSet, or treat the heap elements as unique by rejecting any value already present; the complexity becomes O(n (log K + 1)).
• What if the input is small but you need to answer repeatedly with changing K? – sort the array once in O(n log n) and answer each query in O(1); the amortized cost beats the heap when the query count is large.

Conclusion

Finding the K-th largest element is the generalization of the two-tracker and three-tracker patterns from earlier posts, and it rewards knowing exactly why a min-heap beats a max-heap for this specific question. A single pass, a bounded heap, and a strict comparison against the heap top produce a clean O(n log K) solution that handles duplicates, negatives, and streaming inputs without surprises.

Try adapting the program to return the top K values rather than just the K-th, or implementing Quickselect for the expected O(n) alternative. You can learn more about array problems like this one on our Arrays category page.