Kth Smallest Number in M Sorted Lists (Find the Kth Smallest Across Sorted Lists)

• K-way Merge – a pattern for merging M sorted sequences using a min-heap of size M that always holds the current smallest unprocessed element from each list.
• Kth Smallest across M lists – stop the merge after K pops instead of running it to completion.
• Heap entry – stores the value, the list index, and the element index within that list so the next element can be fetched after a pop.
• Time complexity – O(K log M) because each of K pops involves a log-M heap operation.
• Space complexity – O(M) for the heap, since each list contributes at most one live candidate.

What is the Kth Smallest in M Sorted Lists problem?

You are given M individually sorted lists and an integer K. Find the Kth smallest number among all elements across all lists. You do not need to fully merge the lists; you just need the Kth element in the merged order.

For example, given lists [2, 6, 8], [3, 7, 10], [5, 8, 12] and K = 5, the merged order is [2, 3, 5, 6, 7, 8, 8, 10, 12] and the 5th smallest is 7.

package com.bank.service;

// M sorted fee lists from branches:
// Branch A: [150, 300, 450]
// Branch B: [200, 350, 500]
// Branch C: [100, 250, 400]
// Merged:   [100, 150, 200, 250, 300, 350, 400, 450, 500]
// K=4 -> 4th smallest = 250

How does the K-way Merge with a heap work?

The algorithm seeds a min-heap with the first element of each sorted list. Each entry in the heap carries three pieces of information: the value, the list index (which list it came from), and the element index (its position within that list).

You then pop K times. On each pop, you get the current global minimum. If the popped entry's list has more elements, you push the next element from the same list. The Kth popped value is the answer.

package com.bank.service;

import java.util.List;
import java.util.PriorityQueue;

public class KthSmallestMSorted {

    public int findKthSmallest(List<List<Integer>> lists, int k) {
        // Entry: [value, listIndex, elementIndex]
        PriorityQueue<int[]> heap = new PriorityQueue<>(
            (a, b) -> Integer.compare(a[0], b[0])
        );

        // Seed with first element of each list
        for (int i = 0; i < lists.size(); i++) {
            if (!lists.get(i).isEmpty()) {
                heap.offer(new int[]{lists.get(i).get(0), i, 0});
            }
        }

        int count = 0;
        while (!heap.isEmpty()) {
            int[] entry = heap.poll();
            count++;

            if (count == k) {
                return entry[0]; // Kth smallest found
            }

            int listIdx = entry[1];
            int elemIdx = entry[2];
            if (elemIdx + 1 < lists.get(listIdx).size()) {
                heap.offer(new int[]{
                    lists.get(listIdx).get(elemIdx + 1),
                    listIdx,
                    elemIdx + 1
                });
            }
        }

        throw new IllegalArgumentException("K exceeds total elements");
    }
}

Why is the heap bounded to size M, not K?

The heap holds at most one live candidate per list. After you pop the smallest from list i, you push the next element from list i. The list's slot in the heap is always occupied by at most one entry. Since there are M lists, the heap never exceeds M entries.

This is an important complexity detail. The heap size is M (number of lists), not K (target rank) or N (total elements). Each pop costs O(log M), and you do K pops, so total time is O(K log M).

package com.bank.service;

public class HeapSizeExplanation {
    // M=3 lists, heap always has at most 3 entries:
    // Step 1: heap = [(100, C, 0), (150, A, 0), (200, B, 0)]  size=3
    // Pop 100 from C, push 250 from C:
    // Step 2: heap = [(150, A, 0), (200, B, 0), (250, C, 1)]  size=3
    // Pop 150 from A, push 300 from A:
    // Step 3: heap = [(200, B, 0), (250, C, 1), (300, A, 1)]  size=3
    // Heap never grows beyond M=3
}

How do you handle edge cases?

• K exceeds total elements: throw an exception or return -1. Guard with a total count check.
• Empty lists: skip them when seeding the heap.
• All lists have one element: the heap starts with M entries and each pop exhausts one list.
• K equals 1: pop once and return the global minimum.
• Duplicate values across lists: handled naturally because the heap compares values, not list indices.

package com.bank.service;

import java.util.Arrays;
import java.util.List;

public class KthSmallestDemo {
    public static void main(String[] args) {
        List<List<Integer>> branchFees = Arrays.asList(
            Arrays.asList(150, 300, 450),
            Arrays.asList(200, 350, 500),
            Arrays.asList(100, 250, 400)
        );

        KthSmallestMSorted finder = new KthSmallestMSorted();
        System.out.println("K=1: " + finder.findKthSmallest(branchFees, 1)); // 100
        System.out.println("K=4: " + finder.findKthSmallest(branchFees, 4)); // 250
        System.out.println("K=9: " + finder.findKthSmallest(branchFees, 9)); // 500
    }
}

K=1: 100
K=4: 250
K=9: 500

How is this different from merging all M lists first?

Fully merging M sorted lists produces a single sorted list of all N elements in O(N log M) time. Finding the Kth smallest by stopping early costs only O(K log M). When K is much smaller than N, the early-stop version is dramatically faster.

| Approach | Time | Space | When to use |
|---|---|---|---|
| Full merge then index | O(N log M) | O(N) | Need the entire merged list |
| K-way merge, stop at K | O(K log M) | O(M) | Only need the Kth smallest |
| Sort all into one array | O(N log N) | O(N) | Lists are not pre-sorted |

What about the banking use case?

At the National Bank of India, each regional branch stores its customer fees already sorted. The analytics team needs the Kth smallest fee across all branches for percentile benchmarking. Rather than merging millions of fees from dozens of branches, the K-way merge heap advances only K steps, making the query fast and memory-efficient.

package com.bank.service;

import java.util.Arrays;
import java.util.List;

public class FeeBenchmark {
    public static void main(String[] args) {
        // Each branch has pre-sorted fees
        List<List<Integer>> branchFees = Arrays.asList(
            Arrays.asList(100, 200, 300, 400, 500),
            Arrays.asList(150, 250, 350, 450, 550),
            Arrays.asList(120, 220, 320, 420, 520)
        );

        KthSmallestMSorted finder = new KthSmallestMSorted();
        int percentile10 = finder.findKthSmallest(branchFees, 2);
        System.out.println("10th percentile fee: " + percentile10);
    }
}

10th percentile fee: 120

What should a senior engineer know?

• This is the same engine as Merge K Sorted Lists (LeetCode 23), simply stopped early.
• If you need the Kth largest instead, you could reverse the comparison, but it is simpler to compute (total - K + 1)th smallest.
• For extremely large M, consider a tournament tree or external merge sort.
• In distributed systems, each node's sorted data is a "list" and the coordinator runs the K-way merge.

What are common interview follow-up questions?

• What if the lists are not sorted? (Sort them first, or use a different approach like quickselect on the concatenated array.)
• What is the heap size? (M, not K.)
• Can you do it without a heap? (Binary search on the answer is possible with O(M log N log range) time, which is sometimes better.)
• How do you handle lists stored on disk? (External merge with buffered I/O.)