Smallest Range Covering K Lists

🎯

Smallest Range Covering K Lists

hardMIXEDGoogleAmazonFacebook

Imagine you have multiple news feeds, each sorted by timestamp, and you want to find the smallest time window that includes at least one news item from each feed.

💡 This problem is about finding a range that covers elements from multiple sorted lists simultaneously. Beginners often struggle because it requires managing multiple pointers and understanding how to efficiently track the minimum and maximum elements across lists.

📋

Problem Statement

Given k sorted integer lists, find the smallest range [start, end] such that at least one number from each of the k lists is included in the range. Return the range as a list [start, end]. If multiple ranges satisfy the condition, return the one with the smallest start value.

1 ≤ k ≤ 35000 ≤ number of elements in each list ≤ 50,000-10^5 ≤ element values ≤ 10^5Total number of elements across all lists ≤ 10^5

💡

Example

Input"[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]"

Output[20,24]

The range [20,24] includes 24 from the first list, 20 from the second list, and 22 from the third list, covering all lists with the smallest possible range.

• One or more lists are empty → no valid range, return empty or handle gracefully
• All lists contain the same single element → range is that element
• Lists with negative and positive numbers → range can cross zero
• Lists with very large or very small numbers → ensure no integer overflow

⚠️

Common Mistakes

Not updating the current maximum when pushing new elements into the heap

Incorrect range calculation leading to wrong or suboptimal results

✅ Always update current_max when adding new elements to the heap

Not handling empty lists or null inputs

Runtime errors or incorrect outputs

✅ Add input validation checks before processing

Using brute force for large inputs

Time limit exceeded or program hangs

✅ Explain brute force only, then implement optimized approach

Incorrectly shrinking the sliding window before all lists are covered

Missing valid ranges or incorrect minimal range

✅ Ensure window covers all lists before attempting to shrink

Not breaking loop when one list is exhausted in heap approach

Infinite loop or invalid range

✅ Break when any list runs out of elements

🧠

Brute Force (Enumerate All Combinations)

💡 This approach exists to build intuition by trying all possible combinations of elements, showing why a naive solution is impractical and motivating more efficient methods.

Intuition

Try every possible combination by picking one element from each list and find the range covering those elements. Track the smallest such range.

Algorithm

1. Generate all possible combinations by picking one element from each list.
2. For each combination, find the minimum and maximum values.
3. Calculate the range size (max - min).
4. Keep track of the combination with the smallest range.

💡 The challenge is understanding that checking all combinations is straightforward but computationally expensive, which helps appreciate the need for optimization.

</>

Code

from itertools import product

def smallestRangeBruteForce(nums):
    if not nums or any(len(lst) == 0 for lst in nums):
        return []
    min_range = float('inf')
    result = []
    for combo in product(*nums):
        current_min = min(combo)
        current_max = max(combo)
        if current_max - current_min < min_range or (current_max - current_min == min_range and current_min < result[0] if result else True):
            min_range = current_max - current_min
            result = [current_min, current_max]
    return result

# Driver code
if __name__ == '__main__':
    nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
    print(smallestRangeBruteForce(nums))

Line Notes

from itertools import productImport product to generate all combinations of elements from lists

if not nums or any(len(lst) == 0 for lst in nums)Check for empty input or empty lists to avoid invalid combinations

for combo in product(*nums)Generate every possible tuple picking one element from each list

current_min = min(combo)Find minimum element in current combination to determine range start

current_max = max(combo)Find maximum element in current combination to determine range end

if current_max - current_min < min_range or (current_max - current_min == min_range and current_min < result[0] if result else True)Update result if current range is smaller or equal but starts earlier

import java.util.*;

public class SmallestRangeBruteForce {
    public static int[] smallestRange(List<List<Integer>> nums) {
        if (nums == null || nums.isEmpty()) return new int[0];
        for (List<Integer> list : nums) if (list.isEmpty()) return new int[0];
        int minRange = Integer.MAX_VALUE;
        int[] result = new int[2];
        List<int[]> lists = new ArrayList<>();
        for (List<Integer> list : nums) {
            int[] arr = list.stream().mapToInt(i -> i).toArray();
            lists.add(arr);
        }
        int[] indices = new int[nums.size()];
        int total = 1;
        for (int[] arr : lists) total *= arr.length;
        for (int count = 0; count < total; count++) {
            int temp = count;
            int minVal = Integer.MAX_VALUE, maxVal = Integer.MIN_VALUE;
            for (int i = 0; i < lists.size(); i++) {
                int[] arr = lists.get(i);
                int val = arr[temp % arr.length];
                minVal = Math.min(minVal, val);
                maxVal = Math.max(maxVal, val);
                temp /= arr.length;
            }
            if (maxVal - minVal < minRange || (maxVal - minVal == minRange && minVal < result[0])) {
                minRange = maxVal - minVal;
                result[0] = minVal;
                result[1] = maxVal;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        List<List<Integer>> nums = Arrays.asList(
            Arrays.asList(4,10,15,24,26),
            Arrays.asList(0,9,12,20),
            Arrays.asList(5,18,22,30)
        );
        int[] res = smallestRange(nums);
        System.out.println("[" + res[0] + "," + res[1] + "]");
    }
}

Line Notes

if (nums == null || nums.isEmpty()) return new int[0];Check for null or empty input to avoid errors

for (List<Integer> list : nums) if (list.isEmpty()) return new int[0];Return empty if any list is empty, no valid range

int total = 1; for (int[] arr : lists) total *= arr.length;Calculate total combinations by multiplying lengths

for (int count = 0; count < total; count++)Iterate over all possible combinations using count as index

int val = arr[temp % arr.length];Select element from current list based on modular arithmetic

if (maxVal - minVal < minRange || (maxVal - minVal == minRange && minVal < result[0]))Update result if found smaller or equal range with smaller start

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

void generateAll(const vector<vector<int>>& nums, vector<int>& indices, int depth, int& minRange, pair<int,int>& result) {
    if (depth == nums.size()) {
        int currentMin = INT_MAX, currentMax = INT_MIN;
        for (int i = 0; i < nums.size(); i++) {
            int val = nums[i][indices[i]];
            currentMin = min(currentMin, val);
            currentMax = max(currentMax, val);
        }
        if (currentMax - currentMin < minRange || (currentMax - currentMin == minRange && currentMin < result.first)) {
            minRange = currentMax - currentMin;
            result = {currentMin, currentMax};
        }
        return;
    }
    for (int i = 0; i < nums[depth].size(); i++) {
        indices[depth] = i;
        generateAll(nums, indices, depth + 1, minRange, result);
    }
}

vector<int> smallestRangeBruteForce(const vector<vector<int>>& nums) {
    for (const auto& list : nums) if (list.empty()) return {};
    int minRange = INT_MAX;
    pair<int,int> result = {0, INT_MAX};
    vector<int> indices(nums.size(), 0);
    generateAll(nums, indices, 0, minRange, result);
    return {result.first, result.second};
}

int main() {
    vector<vector<int>> nums = {{4,10,15,24,26},{0,9,12,20},{5,18,22,30}};
    auto res = smallestRangeBruteForce(nums);
    if (res.empty()) {
        cout << "[]" << endl;
    } else {
        cout << "[" << res[0] << "," << res[1] << "]" << endl;
    }
    return 0;
}

Line Notes

for (const auto& list : nums) if (list.empty()) return {};Return empty vector if any list is empty to indicate no valid range

void generateAll(const vector<vector<int>>& nums, vector<int>& indices, int depth, int& minRange, pair<int,int>& result)Recursive function to generate all combinations

if (depth == nums.size())Base case: all lists have selected an element

for (int i = 0; i < nums[depth].size(); i++)Iterate over elements in current list

if (currentMax - currentMin < minRange || (currentMax - currentMin == minRange && currentMin < result.first))Update smallest range found so far

function smallestRangeBruteForce(nums) {
    if (!nums || nums.length === 0 || nums.some(arr => arr.length === 0)) return [];
    let minRange = Infinity;
    let result = [];
    function backtrack(depth, combo) {
        if (depth === nums.length) {
            let currentMin = Math.min(...combo);
            let currentMax = Math.max(...combo);
            if (currentMax - currentMin < minRange || (currentMax - currentMin === minRange && currentMin < (result[0] || Infinity))) {
                minRange = currentMax - currentMin;
                result = [currentMin, currentMax];
            }
            return;
        }
        for (let i = 0; i < nums[depth].length; i++) {
            combo.push(nums[depth][i]);
            backtrack(depth + 1, combo);
            combo.pop();
        }
    }
    backtrack(0, []);
    return result;
}

// Test
const nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]];
console.log(smallestRangeBruteForce(nums));

Line Notes

if (!nums || nums.length === 0 || nums.some(arr => arr.length === 0)) return [];Guard clause for invalid or empty input

function backtrack(depth, combo)Recursive function to build combinations by picking one element per list

if (depth === nums.length)Base case: combination complete, evaluate range

combo.push(nums[depth][i])Add current element to combination before deeper recursion

if (currentMax - currentMin < minRange || (currentMax - currentMin === minRange && currentMin < (result[0] || Infinity)))Update smallest range if better found

⏱

Complexity

TimeO(m^k) where m is average list length and k is number of lists

SpaceO(k) for recursion stack and combination storage

We generate all combinations by picking one element from each list, which is exponential in k, making this approach impractical for large inputs.

💡 For k=3 and m=5, this means 125 combinations; for k=10, it explodes to millions, showing why brute force is not scalable.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and motivate better solutions.

🧠

Better Approach (Merge with Min-Heap)

💡 This approach uses a min-heap to efficiently track the smallest current element among the lists, enabling a sliding window over the merged elements to find the smallest range.

Intuition

Merge the k sorted lists using a min-heap, always knowing the current minimum element. Track the maximum element seen so far to maintain a valid range covering all lists.

Algorithm

1. Initialize a min-heap and insert the first element of each list along with its list index and element index.
2. Track the current maximum element among the inserted elements.
3. Pop the smallest element from the heap and update the range if the current max - min is smaller.
4. If the popped element's list has more elements, insert the next element into the heap and update the max if needed.
5. Repeat until one list is exhausted.

💡 The key is maintaining a window that always contains at least one element from each list, using the heap to efficiently find the minimum.

</>

Code

import heapq

def smallestRange(nums):
    k = len(nums)
    min_heap = []
    current_max = float('-inf')
    # Initialize heap with first element of each list
    for i in range(k):
        if nums[i]:
            val = nums[i][0]
            heapq.heappush(min_heap, (val, i, 0))
            current_max = max(current_max, val)
    range_start, range_end = float('-inf'), float('inf')
    while len(min_heap) == k:
        current_min, row, idx = heapq.heappop(min_heap)
        if current_max - current_min < range_end - range_start or (current_max - current_min == range_end - range_start and current_min < range_start):
            range_start, range_end = current_min, current_max
        if idx + 1 < len(nums[row]):
            next_val = nums[row][idx + 1]
            heapq.heappush(min_heap, (next_val, row, idx + 1))
            current_max = max(current_max, next_val)
        else:
            break
    return [range_start, range_end]

# Driver code
if __name__ == '__main__':
    nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
    print(smallestRange(nums))

Line Notes

import heapqUse heapq for efficient min-heap operations

for i in range(k)Initialize heap with first element from each list

heapq.heappush(min_heap, (val, i, 0))Push tuple with value, list index, and element index

current_max = max(current_max, val)Track the maximum element among current heap elements

while len(min_heap) == kContinue while heap contains one element from each list

current_min, row, idx = heapq.heappop(min_heap)Pop smallest element to update range

if idx + 1 < len(nums[row])If more elements in the same list, push next element

current_max = max(current_max, next_val)Update current max if next element is larger

import java.util.*;

public class SmallestRangeHeap {
    public static int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        int currentMax = Integer.MIN_VALUE;
        int k = nums.size();
        for (int i = 0; i < k; i++) {
            if (!nums.get(i).isEmpty()) {
                int val = nums.get(i).get(0);
                minHeap.offer(new int[]{val, i, 0});
                currentMax = Math.max(currentMax, val);
            }
        }
        int rangeStart = Integer.MIN_VALUE, rangeEnd = Integer.MAX_VALUE;
        while (minHeap.size() == k) {
            int[] minElem = minHeap.poll();
            int currentMin = minElem[0], row = minElem[1], idx = minElem[2];
            if (currentMax - currentMin < rangeEnd - rangeStart || (currentMax - currentMin == rangeEnd - rangeStart && currentMin < rangeStart)) {
                rangeStart = currentMin;
                rangeEnd = currentMax;
            }
            if (idx + 1 < nums.get(row).size()) {
                int nextVal = nums.get(row).get(idx + 1);
                minHeap.offer(new int[]{nextVal, row, idx + 1});
                currentMax = Math.max(currentMax, nextVal);
            } else {
                break;
            }
        }
        return new int[]{rangeStart, rangeEnd};
    }

    public static void main(String[] args) {
        List<List<Integer>> nums = Arrays.asList(
            Arrays.asList(4,10,15,24,26),
            Arrays.asList(0,9,12,20),
            Arrays.asList(5,18,22,30)
        );
        int[] res = smallestRange(nums);
        System.out.println("[" + res[0] + "," + res[1] + "]");
    }
}

Line Notes

PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));Min-heap ordered by element value

for (int i = 0; i < k; i++)Initialize heap with first element from each list

minHeap.offer(new int[]{val, i, 0});Store value, list index, and element index

while (minHeap.size() == k)Process while all lists are represented in heap

int[] minElem = minHeap.poll();Extract smallest element to update range

if (idx + 1 < nums.get(row).size())Add next element from same list if available

currentMax = Math.max(currentMax, nextVal);Update max value seen so far

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

struct Element {
    int val, row, idx;
    bool operator>(const Element& other) const {
        return val > other.val;
    }
};

pair<int,int> smallestRange(const vector<vector<int>>& nums) {
    int k = nums.size();
    priority_queue<Element, vector<Element>, greater<Element>> minHeap;
    int currentMax = INT_MIN;
    for (int i = 0; i < k; i++) {
        if (!nums[i].empty()) {
            minHeap.push({nums[i][0], i, 0});
            currentMax = max(currentMax, nums[i][0]);
        }
    }
    int rangeStart = INT_MIN, rangeEnd = INT_MAX;
    while ((int)minHeap.size() == k) {
        Element minElem = minHeap.top(); minHeap.pop();
        int currentMin = minElem.val, row = minElem.row, idx = minElem.idx;
        if (currentMax - currentMin < rangeEnd - rangeStart || (currentMax - currentMin == rangeEnd - rangeStart && currentMin < rangeStart)) {
            rangeStart = currentMin;
            rangeEnd = currentMax;
        }
        if (idx + 1 < (int)nums[row].size()) {
            int nextVal = nums[row][idx + 1];
            minHeap.push({nextVal, row, idx + 1});
            currentMax = max(currentMax, nextVal);
        } else {
            break;
        }
    }
    return {rangeStart, rangeEnd};
}

int main() {
    vector<vector<int>> nums = {{4,10,15,24,26},{0,9,12,20},{5,18,22,30}};
    auto res = smallestRange(nums);
    cout << "[" << res.first << "," << res.second << "]" << endl;
    return 0;
}

Line Notes

struct ElementCustom struct to hold value and indices for heap

bool operator>(const Element& other) constDefine comparison for min-heap ordering

priority_queue<Element, vector<Element>, greater<Element>> minHeap;Min-heap of Elements

for (int i = 0; i < k; i++)Initialize heap with first element from each list

while ((int)minHeap.size() == k)Continue while all lists are represented

Element minElem = minHeap.top(); minHeap.pop();Pop smallest element to update range

if (idx + 1 < (int)nums[row].size())Push next element from same list if available

currentMax = max(currentMax, nextVal);Update max value seen so far

class MinHeap {
    constructor() {
        this.heap = [];
    }
    swap(i, j) {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    }
    push(val) {
        this.heap.push(val);
        this.bubbleUp(this.heap.length - 1);
    }
    bubbleUp(idx) {
        while (idx > 0) {
            let parent = Math.floor((idx - 1) / 2);
            if (this.heap[parent][0] <= this.heap[idx][0]) break;
            this.swap(parent, idx);
            idx = parent;
        }
    }
    pop() {
        if (this.heap.length === 1) return this.heap.pop();
        const top = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown(0);
        return top;
    }
    bubbleDown(idx) {
        const length = this.heap.length;
        while (true) {
            let left = 2 * idx + 1, right = 2 * idx + 2, smallest = idx;
            if (left < length && this.heap[left][0] < this.heap[smallest][0]) smallest = left;
            if (right < length && this.heap[right][0] < this.heap[smallest][0]) smallest = right;
            if (smallest === idx) break;
            this.swap(idx, smallest);
            idx = smallest;
        }
    }
    size() {
        return this.heap.length;
    }
}

function smallestRange(nums) {
    const k = nums.length;
    const minHeap = new MinHeap();
    let currentMax = -Infinity;
    for (let i = 0; i < k; i++) {
        if (nums[i].length > 0) {
            minHeap.push([nums[i][0], i, 0]);
            currentMax = Math.max(currentMax, nums[i][0]);
        }
    }
    let rangeStart = -Infinity, rangeEnd = Infinity;
    while (minHeap.size() === k) {
        const [currentMin, row, idx] = minHeap.pop();
        if (currentMax - currentMin < rangeEnd - rangeStart || (currentMax - currentMin === rangeEnd - rangeStart && currentMin < rangeStart)) {
            rangeStart = currentMin;
            rangeEnd = currentMax;
        }
        if (idx + 1 < nums[row].length) {
            const nextVal = nums[row][idx + 1];
            minHeap.push([nextVal, row, idx + 1]);
            currentMax = Math.max(currentMax, nextVal);
        } else {
            break;
        }
    }
    return [rangeStart, rangeEnd];
}

// Test
const nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]];
console.log(smallestRange(nums));

Line Notes

class MinHeapCustom min-heap implementation since JS lacks built-in heap

push(val)Add element and maintain heap property by bubbling up

pop()Remove smallest element and restore heap by bubbling down

for (let i = 0; i < k; i++)Initialize heap with first element from each list

while (minHeap.size() === k)Process while all lists are represented in heap

const [currentMin, row, idx] = minHeap.pop();Extract smallest element to update range

if (idx + 1 < nums[row].length)Add next element from same list if available

currentMax = Math.max(currentMax, nextVal);Update max value seen so far

⏱

Complexity

TimeO(n log k) where n is total elements and k is number of lists

SpaceO(k) for the heap and pointers

Each element is pushed and popped once from the heap of size k, so operations cost O(log k) each.

💡 For k=3 and total n=12, this means about 12*log3 ≈ 19 operations, much faster than brute force.

Interview Verdict: Accepted

This approach is efficient and practical for large inputs, making it the standard solution in interviews.

🧠

Optimal Approach (Two Pointers on Merged Array)

💡 This approach merges all elements with their list origin, then uses a sliding window with two pointers to find the smallest range covering all lists.

Intuition

Flatten all lists into one sorted array with list indices, then find the minimum window containing at least one element from each list using two pointers.

Algorithm

1. Create a merged list of all elements with their originating list index.
2. Sort the merged list by element value.
3. Use two pointers to maintain a sliding window over the merged list.
4. Expand the right pointer to include elements until all lists are covered.
5. Shrink the left pointer to minimize the window while still covering all lists.
6. Track the smallest window range during the process.

💡 The challenge is efficiently tracking coverage of all lists and updating the window boundaries.

</>

Code

from collections import Counter

def smallestRangeTwoPointers(nums):
    merged = []
    k = len(nums)
    for i, lst in enumerate(nums):
        for val in lst:
            merged.append((val, i))
    merged.sort(key=lambda x: x[0])
    count = Counter()
    have = 0
    need = k
    left = 0
    min_range = float('inf')
    res = []
    for right in range(len(merged)):
        val, idx = merged[right]
        count[idx] += 1
        if count[idx] == 1:
            have += 1
        while have == need:
            left_val, left_idx = merged[left]
            if val - left_val < min_range or (val - left_val == min_range and left_val < (res[0] if res else float('inf'))):
                min_range = val - left_val
                res = [left_val, val]
            count[left_idx] -= 1
            if count[left_idx] == 0:
                have -= 1
            left += 1
    return res

# Driver code
if __name__ == '__main__':
    nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
    print(smallestRangeTwoPointers(nums))

Line Notes

from collections import CounterUse Counter to track counts of list indices in current window

merged = []Flatten all elements with their list index

merged.sort(key=lambda x: x[0])Sort merged list by element value

count = Counter()Track frequency of list indices in current window

have = 0; need = kTrack how many lists are currently covered

while have == needTry to shrink window while all lists are covered

count[left_idx] -= 1Remove left element from window count

if count[left_idx] == 0: have -= 1If a list is no longer covered, update have

import java.util.*;

public class SmallestRangeTwoPointers {
    public static int[] smallestRange(List<List<Integer>> nums) {
        List<int[]> merged = new ArrayList<>();
        int k = nums.size();
        for (int i = 0; i < k; i++) {
            for (int val : nums.get(i)) {
                merged.add(new int[]{val, i});
            }
        }
        merged.sort(Comparator.comparingInt(a -> a[0]));
        Map<Integer, Integer> count = new HashMap<>();
        int have = 0, need = k, left = 0;
        int minRange = Integer.MAX_VALUE;
        int[] res = new int[2];
        for (int right = 0; right < merged.size(); right++) {
            int val = merged.get(right)[0], idx = merged.get(right)[1];
            count.put(idx, count.getOrDefault(idx, 0) + 1);
            if (count.get(idx) == 1) have++;
            while (have == need) {
                int leftVal = merged.get(left)[0], leftIdx = merged.get(left)[1];
                if (val - leftVal < minRange || (val - leftVal == minRange && leftVal < res[0])) {
                    minRange = val - leftVal;
                    res[0] = leftVal;
                    res[1] = val;
                }
                count.put(leftIdx, count.get(leftIdx) - 1);
                if (count.get(leftIdx) == 0) have--;
                left++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        List<List<Integer>> nums = Arrays.asList(
            Arrays.asList(4,10,15,24,26),
            Arrays.asList(0,9,12,20),
            Arrays.asList(5,18,22,30)
        );
        int[] res = smallestRange(nums);
        System.out.println("[" + res[0] + "," + res[1] + "]");
    }
}

Line Notes

List<int[]> merged = new ArrayList<>();Flatten all elements with their list index

merged.sort(Comparator.comparingInt(a -> a[0]));Sort merged list by element value

Map<Integer, Integer> count = new HashMap<>();Track counts of list indices in current window

if (count.get(idx) == 1) have++;Increment have when a new list is covered

while (have == need)Try to shrink window while all lists are covered

count.put(leftIdx, count.get(leftIdx) - 1);Remove left element from window count

if (count.get(leftIdx) == 0) have--;Update have if a list is no longer covered

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <climits>
using namespace std;

pair<int,int> smallestRangeTwoPointers(const vector<vector<int>>& nums) {
    vector<pair<int,int>> merged;
    int k = nums.size();
    for (int i = 0; i < k; i++) {
        for (int val : nums[i]) {
            merged.emplace_back(val, i);
        }
    }
    sort(merged.begin(), merged.end(), [](auto& a, auto& b) { return a.first < b.first; });
    unordered_map<int,int> count;
    int have = 0, need = k, left = 0;
    int minRange = INT_MAX;
    pair<int,int> res = {0, INT_MAX};
    for (int right = 0; right < (int)merged.size(); right++) {
        int val = merged[right].first, idx = merged[right].second;
        count[idx]++;
        if (count[idx] == 1) have++;
        while (have == need) {
            int leftVal = merged[left].first, leftIdx = merged[left].second;
            if (val - leftVal < minRange || (val - leftVal == minRange && leftVal < res.first)) {
                minRange = val - leftVal;
                res = {leftVal, val};
            }
            count[leftIdx]--;
            if (count[leftIdx] == 0) have--;
            left++;
        }
    }
    return res;
}

int main() {
    vector<vector<int>> nums = {{4,10,15,24,26},{0,9,12,20},{5,18,22,30}};
    auto res = smallestRangeTwoPointers(nums);
    cout << "[" << res.first << "," << res.second << "]" << endl;
    return 0;
}

Line Notes

vector<pair<int,int>> merged;Flatten all elements with their list index

sort(merged.begin(), merged.end(), [](auto& a, auto& b) { return a.first < b.first; });Sort merged list by element value

unordered_map<int,int> count;Track counts of list indices in current window

if (count[idx] == 1) have++;Increment have when a new list is covered

while (have == need)Try to shrink window while all lists are covered

count[leftIdx]--;Remove left element from window count

if (count[leftIdx] == 0) have--;Update have if a list is no longer covered

function smallestRangeTwoPointers(nums) {
    const merged = [];
    const k = nums.length;
    for (let i = 0; i < k; i++) {
        for (const val of nums[i]) {
            merged.push([val, i]);
        }
    }
    merged.sort((a, b) => a[0] - b[0]);
    const count = new Map();
    let have = 0, need = k, left = 0;
    let minRange = Infinity;
    let res = [];
    for (let right = 0; right < merged.length; right++) {
        const [val, idx] = merged[right];
        count.set(idx, (count.get(idx) || 0) + 1);
        if (count.get(idx) === 1) have++;
        while (have === need) {
            const [leftVal, leftIdx] = merged[left];
            if (val - leftVal < minRange || (val - leftVal === minRange && leftVal < (res[0] || Infinity))) {
                minRange = val - leftVal;
                res = [leftVal, val];
            }
            count.set(leftIdx, count.get(leftIdx) - 1);
            if (count.get(leftIdx) === 0) have--;
            left++;
        }
    }
    return res;
}

// Test
const nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]];
console.log(smallestRangeTwoPointers(nums));

Line Notes

const merged = [];Flatten all elements with their list index

merged.sort((a, b) => a[0] - b[0]);Sort merged list by element value

const count = new Map();Track counts of list indices in current window

if (count.get(idx) === 1) have++;Increment have when a new list is covered

while (have === need)Try to shrink window while all lists are covered

count.set(leftIdx, count.get(leftIdx) - 1);Remove left element from window count

if (count.get(leftIdx) === 0) have--;Update have if a list is no longer covered

⏱

Complexity

TimeO(n log n) where n is total number of elements

SpaceO(n) for merged array and O(k) for count map

Sorting all elements dominates time complexity; sliding window is linear.

💡 For n=100,000 elements, sorting takes about 1.5 million operations, which is efficient enough for interviews.

Interview Verdict: Accepted

This approach is optimal when total elements are manageable and is a good alternative to heap-based solutions.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, the min-heap approach is the best balance of clarity and efficiency to implement quickly.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(m^k)	O(k)	Yes (deep recursion)	N/A	Mention only - never code
2. Min-Heap Merge	O(n log k)	O(k)	No	Yes	Code this approach in most interviews
3. Two Pointers on Merged Array	O(n log n)	O(n)	No	Yes	Good alternative if total elements are manageable

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with brute force to grasp the problem, then learn optimized approaches. Practice coding and explaining each step clearly.

How to Present

Clarify the problem and constraints with the interviewer.Describe the brute force approach to show understanding.Explain why brute force is inefficient and introduce the min-heap approach.Discuss the two pointers approach as an alternative.Write clean, tested code for the chosen approach.Test with edge cases and explain your reasoning.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Ability to handle multiple sorted lists, use appropriate data structures (heap, sliding window), and optimize time complexity while maintaining correctness.

Common Follow-ups

• What if lists are not sorted? → Sort first or use different data structures
• How to handle very large k or very large total elements? → Discuss memory and streaming approaches

💡 These follow-ups test your adaptability and understanding of constraints beyond the base problem.

🔍

Pattern Recognition

When to Use

1) Multiple sorted lists, 2) Need to find a range covering all lists, 3) Want smallest or minimal range, 4) Efficient merging or sliding window possible

Signature Phrases

'smallest range that includes at least one number from each list''k sorted lists''cover all lists simultaneously'

NOT This Pattern When

Problems that require only single list sliding window or unrelated range queries without multiple lists

Similar Problems

Merge k Sorted Lists - similar use of min-heap for mergingMinimum Window Substring - sliding window to cover all charactersFind K Closest Elements - binary search with two pointers for range

Practice

1. You are given k sorted linked lists and need to merge them into one sorted list efficiently. Which approach guarantees the optimal time complexity for this problem?

easy

A. Concatenate all lists into one and then sort the combined list using a comparison-based sort.

B. Use a greedy approach by repeatedly picking the smallest head node among all lists without any auxiliary data structure.

C. Apply a divide and conquer strategy by recursively merging pairs of lists until one remains.

D. Use dynamic programming to store intermediate merged results and build the final list.

Solution

1. Step 1: Understand the problem constraints

   We have k sorted lists and want to merge them efficiently.

2. Step 2: Analyze each approach's time complexity

   Greedy without auxiliary structures leads to O(kN) per extraction, concatenation then sorting is O(N log N), dynamic programming is not applicable here. Divide and conquer merges pairs in O(N log k) time, which is optimal.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Divide and conquer merges pairs efficiently [OK]

Hint: Divide and conquer merges pairs in O(N log k) time [OK]

Common Mistakes:

• Assuming greedy without heap is efficient
• Thinking sorting concatenated list is optimal
• Confusing DP applicability here

2. What is the time complexity of the binary search approach that finds the k-th smallest sum in two sorted arrays of lengths n and m, assuming the sums range between minSum and maxSum?

medium

A. O((n + m) * log(maxSum - minSum))

B. O(n * m * log(maxSum - minSum))

C. O(n * log m * log(maxSum - minSum))

D. O(n * m)

Solution

1. Step 1: Analyze countPairs complexity

   countPairs runs in O(n + m) because j only moves backward once across all i.

2. Step 2: Analyze binary search iterations

   Binary search runs O(log(maxSum - minSum)) times.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Combined complexity is O((n + m) * log(maxSum - minSum)) [OK]

Hint: countPairs uses two-pointer linear scan, not nested loops [OK]

Common Mistakes:

• Assuming countPairs is O(n*m)
• Confusing n and m in complexity

3. What is the time complexity of sorting a k-sorted array of size n using a min-heap of size k+1, and why might the common misconception of O(n log n) be incorrect?

medium

A. O(n log n) because each element is inserted and extracted from a heap of size n.

B. O(k log n) because the heap size depends on n but operations depend on k.

C. O(n log k) because each heap operation is on a heap of size k+1, not n.

D. O(n + k log n) because initial heapify takes O(n) and subsequent operations depend on k.

Solution

1. Step 1: Identify heap size and operations

   Heap size is k+1, so each push/pop is O(log k).

2. Step 2: Count total operations

   We perform n insertions and extractions, each O(log k), total O(n log k).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Heap size k+1, not n, reduces complexity from O(n log n) [OK]

Hint: Heap size k+1 reduces log factor from log n to log k [OK]

Common Mistakes:

• Assuming heap size is n, leading to O(n log n)
• Confusing initial heapify cost with total complexity
• Mixing up k and n in complexity terms

4. Suppose you want to find the median of K sorted arrays where elements can be reused infinitely (i.e., arrays represent multisets with unlimited copies). Which modification to the optimal binary search approach is correct?

hard

A. Use the same binary search counting method since counts remain valid with infinite reuse.

B. Modify counting to multiply bisect counts by infinity, which is not feasible; thus binary search fails here.

C. Use binary search on value range but replace counting with a formula based on frequency and reuse constraints.

D. Switch to a heap-based approach that tracks counts and duplicates explicitly to handle infinite reuse.

Solution

1. Step 1: Understand infinite reuse impact

   Infinite reuse means counts are unbounded; naive counting fails.

2. Step 2: Adapt counting method

   Counting must use frequency and reuse constraints to compute how many elements ≤ mid considering infinite copies.

3. Step 3: Modify binary search accordingly

   Binary search on value range remains valid but counting function must be formula-based, not bisect-based.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Counting must reflect reuse; naive bisect counting breaks [OK]

Hint: Infinite reuse breaks bisect counting; formula needed [OK]

Common Mistakes:

• Assuming bisect counting works with infinite reuse
• Switching to heap unnecessarily
• Ignoring reuse constraints in counting

5. Suppose the problem changes so that elements from the arrays can be reused multiple times to form sums (i.e., pairs can include the same element multiple times). Which modification to the binary search approach is necessary to correctly find the k-th smallest sum?

hard

A. No modification needed; reuse does not affect counting pairs.

B. Use a min-heap approach with a visited set to handle duplicates and reuse correctly.

C. Modify countPairs to count pairs with replacement by resetting pointer j for each i.

D. Use binary search but countPairs must be replaced with a formula counting sums with repetition.

Solution

1. Step 1: Understand reuse effect on counting

   With reuse allowed, pairs are not limited to unique indices; counting must consider all j for each i.

2. Step 2: Modify countPairs

   Resetting j for each i allows counting all pairs with sums ≤ mid including repeated elements.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Resetting j ensures correct counting with reuse [OK]

Hint: Reusing elements breaks monotonic pointer j; must reset per i [OK]

Common Mistakes:

• Assuming original countPairs works with reuse
• Using heap without visited set causes duplicates