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. What is the time complexity of the optimal Alien Dictionary solution using Kahn's algorithm with early cycle detection and edge deduplication, given C as the total number of characters in all words and U as the number of unique characters?

medium

A. O(C log U) due to sorting characters during graph construction

B. O(U^2) due to checking all pairs of characters

C. O(C * U) because each character is compared with all unique characters

D. O(C + U + E) where E is number of edges, since graph construction and BFS visit all characters and edges once

Solution

1. Step 1: Analyze graph construction cost

   Each adjacent word pair is compared up to min length, total comparisons proportional to total characters C.

2. Step 2: Analyze topological sort cost

   BFS visits each node (U) and each edge (E) once; E ≤ C since edges come from character comparisons.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Overall complexity O(C + U + E) matches linear graph traversal [OK]

Hint: Graph traversal cost dominates, not pairwise character comparisons [OK]

Common Mistakes:

• Assuming quadratic due to character pairs
• Confusing edges with nodes
• Forgetting BFS linearity

2. What is the worst-case time complexity of the optimal backtracking solution for the Expression Add Operators problem, given a numeric string of length n?

medium

A. O(n^3) due to nested loops and substring parsing

B. O(2^n) because each digit can either be concatenated or separated by an operator

C. O(4^n) because each digit can be followed by 4 choices: +, -, *, or no operator (concatenate)

D. O(3^n) since only three operators are inserted between digits

Solution

1. Step 1: Identify branching factor per digit

   At each digit (except the first), there are 4 choices: add '+', '-', '*', or concatenate (no operator).

2. Step 2: Calculate total combinations

   With n digits, the number of expressions is roughly 4^(n-1), which is O(4^n) in worst case.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   4 choices per digit lead to exponential 4^n growth [OK]

Hint: Count operator choices plus concatenation per digit [OK]

Common Mistakes:

• Confusing 3 operators only, ignoring concatenation
• Assuming polynomial complexity

3. The following code attempts to solve the Russian Doll Envelopes problem optimally. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line 4: Sorting envelopes with key (x[0], x[1]) ascending both

B. Line 6: Extracting heights from envelopes

C. Line 8: Using bisect_left to find insertion index

D. Line 11: Replacing tails element at found index

Solution

1. Step 1: Examine sorting key

   Sorting by (width asc, height asc) allows envelopes with same width and increasing height, which breaks strict nesting rules.

2. Step 2: Correct sorting key

   Sorting by (width asc, height desc) prevents envelopes with equal width but increasing height from being counted incorrectly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing sorting to (x[0], -x[1]) fixes the bug [OK]

Hint: Sort height descending for equal widths to avoid counting duplicates [OK]

Common Mistakes:

• Sorting both width and height ascending
• Using <= instead of < in comparisons
• Not handling equal widths properly

4. Examine the following snippet from an implementation of the optimal Word Search II solution. Which line contains a subtle bug that can cause incorrect results or infinite recursion?

medium

A. Line where curr_node.word is not set to null after found

B. Line where board[r][c] is set to '#'

C. Line where curr_node.word is appended to res

D. Line where backtrack is recursively called on neighbors

Solution

1. Step 1: Identify purpose of setting curr_node.word to None

   This prevents adding the same word multiple times by marking it as found.

2. Step 2: Analyze effect of missing this line

   Without setting curr_node.word to None, duplicates can be appended and redundant searches occur, possibly causing inefficiency or infinite recursion.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing word removal after found causes duplicates [OK]

Hint: Mark found words None to avoid duplicates [OK]

Common Mistakes:

• Forgetting to mark visited cells
• Not pruning found words
• Incorrect recursion boundaries

5. Suppose the problem is modified so that characters in t can be reused unlimited times (i.e., the window must contain at least one occurrence of each character in t, but counts do not matter). Which modification to the sliding window algorithm correctly solves this variant?

hard

A. Keep frequency counts but ignore decrementing counts when shrinking window

B. Sort s and t and use two pointers to find minimal substring containing all chars

C. Use the original frequency counting approach but reset counts after each valid window

D. Use a set to track which characters from t are present in the window, and shrink when all are present

Solution

1. Step 1: Understand the variant

   Since counts do not matter and characters can be reused unlimited times, we only need to check presence of each unique character from t in the window.

2. Step 2: Modify tracking data structure

   Using a set to track which characters from t are currently in the window is sufficient. When the set contains all unique chars, the window is valid.

3. Step 3: Shrink window accordingly

   Shrink the window while maintaining presence of all required characters in the set.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Tracking presence with a set fits the reuse variant [OK]

Hint: Presence tracking with set suffices when counts don't matter [OK]

Common Mistakes:

• Continuing to track exact counts unnecessarily
• Resetting counts incorrectly
• Sorting strings which breaks substring property