Find the Kth Smallest Element in an Array

Title: Find the Kth Smallest Element in an Array

In this guide, you’ll learn how to find the K-th smallest element in an array using a max-heap of size K. We’ll frame the problem, build a clean solution in Java with PriorityQueue and Collections.reverseOrder(), trace it by hand on a fresh input, and then stress test it against the edge cases that trip candidates up when the heap direction has to flip.

This is the mirror of the “K-th largest” interview question, and the whole lesson lives in a single word: max. Java’s PriorityQueue defaults to a min-heap, which is the wrong direction for this problem. By the end of this article you’ll have a program that runs in O(n log K) time, a mental model for picking the heap direction, and a feel for the Quickselect alternative interviewers love to ask about.

Understanding the Problem

Given an integer array and an integer k, we want to return the K-th smallest element in the array in sorted order. Duplicates count: for {3, 2, 3, 1, 2, 4, 5, 5, 6} with k = 4 the ascending sort is 1, 2, 2, 3, 3, 4, 5, 5, 6 and the fourth entry is 3. This is the convention most interviewers expect unless they say otherwise.

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

Approach Using a Max-Heap of Size K

We walk through the array once, maintaining a max-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 max-heap using PriorityQueue with Collections.reverseOrder() as the comparator, since the default is a min-heap.
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 less than the heap’s top (the current K-th smallest candidate), poll the top and offer the current element.
6. Otherwise, the current element cannot be in the bottom K; skip it.
7. After the loop, return the heap’s top, which is now the K-th smallest element.

Java Program

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

import java.util.Collections;
import java.util.PriorityQueue;

public class KthSmallestElement {
    public static int findKthSmallest(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> maxHeap = new PriorityQueue<>(k, Collections.reverseOrder());
        for (int i = 0; i < numbers.length; i++) {
            if (maxHeap.size() < k) {
                maxHeap.offer(numbers[i]);
            } else if (numbers[i] < maxHeap.peek()) {
                maxHeap.poll();
                maxHeap.offer(numbers[i]);
            }
        }
        return maxHeap.peek();
    }

    public static void main(String[] args) {
        int[] numbers = {7, 10, 4, 3, 20, 15};
        int k = 3;
        int result = findKthSmallest(numbers, k);
        System.out.println("The " + k + "th smallest element is: " + result);
    }
}

Explanation of the Program

The guard clause at the top of findKthSmallest 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 largest element for k = 0 or throwing a confusing NoSuchElementException at the final peek.

The key configuration is Collections.reverseOrder() passed to the PriorityQueue constructor. Without this comparator, Java gives you a min-heap by default, which is the wrong direction for this problem. With the reverse-order comparator, peek() and poll() both operate on the largest element currently in the heap.

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 largest of the current bottom-K candidates), we evict the top and offer the current element. The implicit third case, where the current element is not smaller than the top, is handled by doing nothing because the element cannot possibly be in the final bottom K.

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

Step-by-Step Trace

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

Invariant: at the end of each iteration, the heap contains the K smallest elements seen so far (or all elements seen so far if fewer than K have arrived), with the largest of them at the top. Iteration 6 is the one worth studying: a duplicate of a value already in the heap can still legitimately displace the top because duplicates count toward the K-smallest set.

Examples

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

Example 1: Mixed Positive Integers

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

The sorted ascending view is 1, 2, 3, 4, 5, 6, so the second smallest is 2. This is the mirror of the canonical K-th largest example.

Example 2: Duplicates in the Input

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

Duplicates count: the sorted ascending view is 1, 2, 2, 3, 3, 4, 5, 5, 6, so the fourth entry is 3. If you expected 4 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 = findKthSmallest(numbers, 2);
System.out.println(result);
// Output: -4

The sorted ascending view is -5, -4, -3, -2, -1, so the second smallest is -4. Note that “second smallest” means “second from the bottom,” not “second closest to zero.” The reverse-order comparator honors the sign naturally.

Common Mistakes to Avoid

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

• Forgetting Collections.reverseOrder() – new PriorityQueue<>() gives you a min-heap by default. Without the reverse-order comparator, the “max-heap” is actually a min-heap and your code returns the K-th largest instead of the K-th smallest. Pass the comparator explicitly.
• Using a min-heap of size K – feels right for “smallest” but ends up requiring k - 1 extra polls at the end to reach the K-th element, and does not let you reject large inputs in O(1). Use a max-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.
• 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.
• Confusing K-th smallest with K-th distinct smallest – the usual convention keeps duplicates, so {5, 5, 5} with k = 2 returns 5. Always clarify the interpretation with the interviewer before coding.

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 minimum)
• K equals the array length (just the maximum)
• 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 random pivot runs in expected O(n) time with O(1) extra space (operating in place) but has a pathological O(n squared) worst case; most interviewers accept Quickselect with random-pivot as the next-level answer.

When K approaches n, the max-heap approach degrades to O(n log n) and loses its edge. A good rule of thumb: if K <= n / 2, use a max-heap of size K for the K-th smallest; otherwise, pivot and use a min-heap of size n - k + 1 to find the K-th smallest as the largest of the “top” 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 max-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 bottom-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 smallest? – 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 smallest element is the mirror of the K-th largest, and the whole lesson lives in picking the right heap direction. A single pass, a bounded max-heap built with Collections.reverseOrder(), and a strict less-than 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 bottom 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.