Kth Smallest Number (Find the Kth Smallest with a Max-Heap)

• Kth Smallest – find the element that would be at index K - 1 if the array were fully sorted in ascending order.
• Max-heap of size K – holds the K smallest numbers seen so far; its root is the largest of those K, which is exactly the Kth smallest overall.
• Insertion rule – if a new number is smaller than the root, evict the root and insert the new number; otherwise discard it.
• Complexity – O(n log K) time and O(K) space, better than O(n log n) sorting when K is much smaller than n.
• Alternative – quickselect gives average O(n) for a single query on a static in-memory array.

What is the Kth Smallest Number problem?

Given an unsorted array of numbers and an integer K, find the Kth smallest number. If the array were sorted in ascending order, the Kth smallest would be at index K - 1. The challenge is to find it without fully sorting the array.

For example, in the array [7, 10, 4, 3, 20, 15] with K = 3, the sorted order is [3, 4, 7, 10, 15, 20] and the 3rd smallest is 7.

package com.bank.service;

// Find the Kth smallest fee among all branch fees
// Input: fees = [500, 200, 800, 150, 350, 900], K = 2
// Sorted: [150, 200, 350, 500, 800, 900]
// Answer: 200 (the 2nd smallest fee)

Why use a max-heap for the Kth smallest?

The counter-intuitive choice is key here. To find the Kth smallest, you use a max-heap, not a min-heap. The max-heap holds the K smallest numbers seen so far. Its root is the largest of those K, which is exactly the Kth smallest overall. This root acts as a gatekeeper: any number larger than the root cannot be among the K smallest, so it is discarded.

In Java, PriorityQueue is a min-heap by default, so you pass Collections.reverseOrder() to create a max-heap.

package com.bank.service;

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

public class KthSmallestFinder {

    public int findKthSmallest(int[] nums, int k) {
        PriorityQueue<Integer> maxHeap =
            new PriorityQueue<>(Collections.reverseOrder());

        for (int num : nums) {
            maxHeap.offer(num);
            if (maxHeap.size() > k) {
                maxHeap.poll(); // evict the largest, keeping K smallest
            }
        }
        return maxHeap.peek(); // root = Kth smallest
    }
}

How does the algorithm work step by step?

Walk through the fees array [500, 200, 800, 150, 350, 900] with K = 2.

1. Add 500 to heap. Heap: [500]. Size 1, which is at most K.
2. Add 200 to heap. Heap: [500, 200]. Size 2, which equals K.
3. Add 800. Heap: [800, 200, 500]. Size 3 > K, poll 800. Heap: [500, 200].
4. Add 150. Heap: [500, 200, 150]. Size 3 > K, poll 500. Heap: [200, 150].
5. Add 350. Heap: [350, 150, 200]. Size 3 > K, poll 350. Heap: [200, 150].
6. Add 900. Heap: [900, 150, 200]. Size 3 > K, poll 900. Heap: [200, 150].

The root is 200, which is the 2nd smallest fee.

package com.bank.service;

public class KthSmallestDemo {
    public static void main(String[] args) {
        int[] fees = {500, 200, 800, 150, 350, 900};
        KthSmallestFinder finder = new KthSmallestFinder();
        int result = finder.findKthSmallest(fees, 2);
        System.out.println("2nd smallest fee: " + result);
    }
}

2nd smallest fee: 200

How is Kth Smallest different from Kth Largest?

The heap type flips. For Kth largest, you use a min-heap of size K. For Kth smallest, you use a max-heap of size K. The root always represents the boundary value: the Kth element in the desired direction.

| Feature | Kth Smallest | Kth Largest |
|---|---|---|
| Heap type | Max-heap (size K) | Min-heap (size K) |
| Root meaning | Largest of K smallest = Kth smallest | Smallest of K largest = Kth largest |
| Eviction rule | Evict root when new value is smaller | Evict root when new value is larger |
| Java constructor | new PriorityQueue<>(reverseOrder()) | new PriorityQueue<>() |

package com.bank.service;

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

public class KthComparison {
    // Kth SMALLEST: max-heap keeps K smallest, root = Kth smallest
    public static int kthSmallest(int[] nums, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int n : nums) { maxHeap.offer(n); if (maxHeap.size() > k) maxHeap.poll(); }
        return maxHeap.peek();
    }

    // Kth LARGEST: min-heap keeps K largest, root = Kth largest
    public static int kthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int n : nums) { minHeap.offer(n); if (minHeap.size() > k) minHeap.poll(); }
        return minHeap.peek();
    }

    public static void main(String[] args) {
        int[] fees = {500, 200, 800, 150, 350, 900};
        System.out.println("2nd smallest: " + kthSmallest(fees, 2)); // 200
        System.out.println("2nd largest:  " + kthLargest(fees, 2));  // 800
    }
}

2nd smallest: 200
2nd largest:  800

What about quickselect as an alternative?

For a single query on a static in-memory array, quickselect (also called the partition-select algorithm) gives O(n) average time. It partitions the array around a pivot and recurses into only the side containing the Kth element, halving the problem each time.

package com.bank.service;

import java.util.Random;

public class QuickSelectFinder {
    private final Random random = new Random();

    public int quickSelect(int[] nums, int k) {
        return select(nums, 0, nums.length - 1, k - 1);
    }

    private int select(int[] nums, int lo, int hi, int target) {
        int pivotIdx = partition(nums, lo, hi);
        if (pivotIdx == target) return nums[pivotIdx];
        if (pivotIdx < target) return select(nums, pivotIdx + 1, hi, target);
        return select(nums, lo, pivotIdx - 1, target);
    }

    private int partition(int[] nums, int lo, int hi) {
        int randIdx = lo + random.nextInt(hi - lo + 1);
        swap(nums, randIdx, hi);
        int pivot = nums[hi];
        int i = lo;
        for (int j = lo; j < hi; j++) {
            if (nums[j] <= pivot) swap(nums, i++, j);
        }
        swap(nums, i, hi);
        return i;
    }

    private void swap(int[] a, int i, int j) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
}

What are the edge cases?

• K equals 1: the answer is the minimum. The heap reduces to holding just one element.
• K equals n: the answer is the maximum.
• K out of range: throw an exception. Guard with if (k < 1 || k > nums.length).
• Duplicate values: the algorithm handles duplicates correctly because the heap does not enforce uniqueness.
• All same values: every element is both the Kth smallest and Kth largest.

package com.bank.service;

public class KthSmallestEdgeCases {
    public static void main(String[] args) {
        KthSmallestFinder finder = new KthSmallestFinder();
        int[] fees = {500, 200, 800, 150, 350, 900};
        System.out.println("K=1 (min): " + finder.findKthSmallest(fees, 1));
        System.out.println("K=6 (max): " + finder.findKthSmallest(fees, 6));

        int[] same = {100, 100, 100};
        System.out.println("All same, K=2: " + finder.findKthSmallest(same, 2));
    }
}

K=1 (min): 150
K=6 (max): 900
All same, K=2: 100

When should you use the heap vs quickselect?

• Heap: streaming data where elements arrive over time, or when K is much smaller than n and you want O(n log K) guaranteed.
• Quickselect: single query on a static in-memory array where O(n) average is acceptable. Worst case is O(n squared) but randomized pivots make this extremely unlikely.
• Full sort: when you need multiple Kth queries on the same array, sorting once at O(n log n) and then indexing is simpler.

What are common interview follow-up questions?

• What heap type do you use for Kth smallest vs Kth largest? (Max-heap for smallest, min-heap for largest.)
• What if the data is streaming and you cannot sort? (Heap approach works directly.)
• Can you do better than O(n log K)? (Quickselect gives O(n) average for a single query.)
• How do you handle negative numbers? (No change needed; comparisons work the same.)
• What if K changes over time? (Maintain the full sorted structure or use an order-statistics tree.)