Smallest Number Range Covering K Lists (Find the Tightest Range Including One Element from Each List)

• Smallest Number Range is a K-way Merge problem that finds the tightest range covering all K sorted lists.
• A min-heap holds one current element per list, and a separate variable tracks the running maximum.
• The span from heap minimum to running maximum is always a valid covering range.
• We repeatedly advance the minimum to try to shrink the window, updating the best range.
• When any list is exhausted, no further valid window exists, so we stop.
• Time is O(N log K) and space is O(K).

What is the Smallest Number Range problem?

Given K sorted lists of integers, find the smallest range [a, b] such that at least one number from each list falls within the range. The range size is b - a. If multiple ranges have the same size, return the one with the smaller start value.

For example, given lists [4, 10, 15], [0, 9, 12], [5, 18, 22], the smallest range is [9, 15] because it includes 10 from list 1, 9 from list 2, and 15 from list 3.

What is the key invariant?

The crucial invariant is that if the heap holds exactly one element from each list, then the span from the smallest to the largest of those elements necessarily contains at least one element from every list. This means the span is a valid covering range at all times.

How does the algorithm work?

We seed the min-heap with the first element of each list and compute the maximum of those seeds. Each iteration: read the heap minimum, compare the span max - min against the best so far, pop the minimum, and push its successor from the same list while updating the running maximum.

package com.bank.service;

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

public class SmallestRangeService {

    /**
     * Finds the smallest range covering at least one rate from each lender.
     * Used by the National Bank of India marketing team.
     */
    public static int[] smallestRange(List<List<Integer>> lenderRates) {
        // Heap entry: {value, listIndex, elementIndex}
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(
            (a, b) -> Integer.compare(a[0], b[0]));

        int currentMax = Integer.MIN_VALUE;

        // Seed with first element of each list
        for (int i = 0; i < lenderRates.size(); i++) {
            int val = lenderRates.get(i).get(0);
            minHeap.offer(new int[]{val, i, 0});
            currentMax = Math.max(currentMax, val);
        }

        int bestStart = minHeap.peek()[0];
        int bestEnd = currentMax;

        while (true) {
            int[] entry = minHeap.poll();
            int val = entry[0], listIdx = entry[1], elemIdx = entry[2];

            // Check if this window is tighter
            if (currentMax - val < bestEnd - bestStart) {
                bestStart = val;
                bestEnd = currentMax;
            }

            // Push successor from the same list
            if (elemIdx + 1 >= lenderRates.get(listIdx).size()) {
                break; // List exhausted, no further valid window
            }
            int nextVal = lenderRates.get(listIdx).get(elemIdx + 1);
            minHeap.offer(new int[]{nextVal, listIdx, elemIdx + 1});
            currentMax = Math.max(currentMax, nextVal);
        }

        return new int[]{bestStart, bestEnd};
    }

    public static void main(String[] args) {
        List<List<Integer>> rates = List.of(
            List.of(400, 1000, 1500),
            List.of(0, 900, 1200),
            List.of(500, 1800, 2200)
        );
        int[] range = smallestRange(rates);
        System.out.println("Smallest range: [" + range[0] + ", " + range[1] + "]");
    }
}

Smallest range: [400, 500]

Why does advancing the minimum shrink the window?

The window spans from the heap minimum to the running maximum. The maximum can only stay the same or increase when we push a new element. The minimum can only stay the same or increase when we pop and replace it. Therefore, advancing the minimum is the only lever that can reduce the window width. The maximum is passive; it only grows.

When does the algorithm stop?

The algorithm stops the moment any list is exhausted, meaning the popped element has no successor. After that point, we cannot maintain one element per list in the heap, so no further valid covering window exists.

What are the edge cases?

Several edge cases require attention.

• Single list: the range is [min, min] for a single element, or [first, first] since only one list exists.
• Lists with one element each: the range spans from the smallest to the largest of those elements.
• Duplicate values across lists: the range may be zero width if all lists share a common value.
• Large K with small lists: the algorithm terminates quickly since the shortest list bounds iterations.

package com.bank.core;

import java.util.List;

public class SmallestRangeEdgeCases {
    public static void main(String[] args) {
        // All lists share a common value
        List<List<Integer>> rates = List.of(
            List.of(100, 500),
            List.of(100, 600),
            List.of(100, 700)
        );
        int[] range = SmallestRangeService.smallestRange(rates);
        System.out.println("Range: [" + range[0] + ", " + range[1] + "]");
        // [100, 100] -> zero width
    }
}

What is the time and space complexity?

With N total elements across all K lists, each element is pushed and popped from the heap at most once. Each heap operation costs O(log K). Total time is O(N log K). Space is O(K) for the heap holding one element per list.

How does tie-breaking work?

Ties on window width are resolved by keeping the first (smaller-start) window. We only replace the best when a new window is strictly tighter (currentMax - val < bestEnd - bestStart), not when equal. This ensures the first window with the smallest start is preserved.

What should a senior engineer know?

A senior engineer should understand these deeper aspects.

• This is a sliding window over a virtual merged stream: the heap simulates merging K sorted lists, and the window advances by moving the minimum forward.
• The running maximum cannot decrease: it is monotonically non-decreasing, which is why only the minimum matters for shrinking.
• Alternative approach: merge all lists, then use a sliding window with a frequency map to ensure coverage. This is O(N log N) and uses more space but is conceptually simpler.