Log inSign up
hardLeetCodeNot Started

Smallest Range Covering Elements from K Lists

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Heap
Solve on LeetCode
Lesson

Problem Statement

You have k lists of sorted integers in non-decreasing order. Find the smallest range [a, b] such that every list has at least one number inside this range (i.e., a <= x <= b).

A range [a, b] is smaller than [c, d] if b - a < d - c, or a < c if the lengths are equal.

Example 1 · Example 1: Three Sorted Lists:

Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20, 24]
Explanation: List 1: 24 is in [20, 24]\nList 2: 20 is in [20, 24]\nList 3: 22 is in [20, 24]\nRange length is 24 - 20 = 4, which is the minimum possible.

Constraints:

  • nums.length == k
  • 1 <= k <= 3500
  • 1 <= nums[i].length <= 50
  • -105 <= nums[i][j] <= 105
  • nums[i] is sorted in non-decreasing order.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why advancing the minimum element is the only way to shrink the range.
  • Implement multi-pointer tracking using a Min-Heap of size K.
  • Analyze why algorithm terminates as soon as any list is exhausted.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • k sorted lists given.
  • Must pick at least one element from each list.
  • Find minimal enclosing interval [a, b].

Algorithmic Decision Tree:

  • Whenever k sorted streams must be merged or collectively examined, use a Min-Heap of size k.
  • Sliding window over flattened merged list works, but Min-Heap requires only O(k) memory vs O(N).

Connected Patterns:

Merge k Sorted ListsFind K Pairs with Smallest SumsMinimum Window Substring

1. Brute Force — Flatten, Sort and Check All Windows

Intuition

Tag every element with list index, sort array. Check every subarray window [i, j]. If it contains at least one element from every list, track minimum range.

When to apply: When total elements count is very small (N <= 100).

Algorithm

  1. Step 1: Flatten all lists into (val, listId) pairs.
  2. Step 2: Sort combined array ascending.
  3. Step 3: For each i, for each j: track seen listIds.
  4. Step 4: If all k lists are seen, update best range if (val[j] - val[i]) is smaller.
  5. Step 5: Return minimal range.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <unordered_set>
5
6class Solution {
7public:
8 std::vector<int> smallestRange(std::vector<std::vector<int>>& nums) {
9 int k = nums.size();
10 std::vector<std::pair<int, int>> combined;
11 for (int i = 0; i < k; ++i) {
12 for (int val : nums[i]) combined.push_back({val, i});
13 }
14 std::sort(combined.begin(), combined.end());
15
16 int n = combined.size();
17 int bestStart = 0, bestEnd = 1e9;
18
19 for (int i = 0; i < n; ++i) {
20 std::unordered_set<int> seen;
21 for (int j = i; j < n; ++j) {
22 seen.insert(combined[j].second);
23 if (seen.size() == k) {
24 if (combined[j].first - combined[i].first < bestEnd - bestStart) {
25 bestStart = combined[i].first;
26 bestEnd = combined[j].first;
27 }
28 break;
29 }
30 }
31 }
32 return {bestStart, bestEnd};
33 }
34};
35
36int main() {
37 Solution sol;
38 std::vector<std::vector<int>> nums = {{4, 10, 15, 24, 26}, {0, 9, 12, 20}, {5, 18, 22, 30}};
39 std::vector<int> res = sol.smallestRange(nums);
40 std::cout << "[" << res[0] << ", " << res[1] << "]\n";
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(N^2 * k) — O(N2) pairs of indices, each checking up to k elements.
  • Space complexity: O(N) — Stores all combined elements in single array.

Why Brute Force Doesn't Scale:

With N = 1.75 * 105 total elements and k = 3500, an O(N * k) linear scan takes ~6 * 108 operations, which times out. Min-Heap performs O(N log k) ~ 2 * 106 operations.

For k = 3500, log2(k) ~ 12. Heap does 12 operations instead of 3,500 operations per step — a 290x speedup.

2. Better — Sorted Flatten + Sliding Window

Intuition

Merge all elements into one sorted array with list IDs. Expand right pointer until all k lists are present. Then contract left pointer to find minimum range, tracking counts with a map.

When to apply: When O(N) auxiliary space is acceptable.

Algorithm

  1. Step 1: Flatten all elements with list IDs and sort by value.
  2. Step 2: Initialize two pointers left = 0, right = 0 and frequency map.
  3. Step 3: Expand right, incrementing count for that list.
  4. Step 4: While all k lists are covered, update best range and advance left.
  5. Step 5: Return minimal range.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <unordered_map>
5
6class Solution {
7public:
8 std::vector<int> smallestRange(std::vector<std::vector<int>>& nums) {
9 int k = nums.size();
10 std::vector<std::pair<int, int>> combined;
11 for (int i = 0; i < k; ++i) {
12 for (int val : nums[i]) combined.push_back({val, i});
13 }
14 std::sort(combined.begin(), combined.end());
15
16 std::unordered_map<int, int> count;
17 int uniqueCount = 0, left = 0, n = combined.size();
18 int bestStart = 0, bestEnd = 1e9;
19
20 for (int right = 0; right < n; ++right) {
21 int listId = combined[right].second;
22 if (++count[listId] == 1) uniqueCount++;
23
24 while (uniqueCount == k) {
25 if (combined[right].first - combined[left].first < bestEnd - bestStart) {
26 bestStart = combined[left].first;
27 bestEnd = combined[right].first;
28 }
29 int leftListId = combined[left].second;
30 if (--count[leftListId] == 0) uniqueCount--;
31 left++;
32 }
33 }
34 return {bestStart, bestEnd};
35 }
36};
37
38int main() {
39 Solution sol;
40 std::vector<std::vector<int>> nums = {{4, 10, 15, 24, 26}, {0, 9, 12, 20}, {5, 18, 22, 30}};
41 std::vector<int> res = sol.smallestRange(nums);
42 std::cout << "[" << res[0] << ", " << res[1] << "]\n";
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(N log N) — Sorting N elements takes O(N log N). Two-pointer window takes O(N) linear time.
  • Space complexity: O(N) — Stores flattened array of N elements.

3. Optimal — Min-Heap K-Way Pointer Tracking

Intuition

Keep one active element from each list in a Min-Heap of size k. Track currentMax. The current valid range is [minHeap.top(), currentMax]. Update the best range, then push the next element from the popped element's list and update currentMax. Stop immediately when any list runs out.

When to apply: Optimal for merging and range queries over k sorted lists.

Algorithm

  1. Step 1: Push first element of each list into Min-Heap as (val, row, col).
  2. Step 2: Maintain currentMax as max of all initial elements.
  3. Step 3: Pop minimum element (minVal, row, col).
  4. Step 4: Update best range if currentMax - minVal is smaller.
  5. Step 5: If col + 1 < length of list row, push next element and update currentMax.
  6. Step 6: If col + 1 equals length of list, break (list exhausted).
  7. Step 7: Return best range.

Interactive Trace for Smallest Range Covering Elements from K Lists

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Heap holds [0 (L1), 4 (L0), 5 (L2)]
Visual state
Values and pointers at this exact step
tree
Root: 0 (L1)
0
Left: 4 (L0)
4
Right: 5 (L2)
5

Node order shown; add connections to display explicit tree edges.

minVal: h1maxVal: h3
Check / comparison
Range [0, 5] has length 5.
Decision / next transition
Record [0, 5] as current best. Advance pointer in L1.
Why this step matters

Step 1: Heap holds [0 (L1), 4 (L0), 5 (L2)]. Min is 0, Max is 5. Best range is [0, 5].

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <algorithm>
5
6struct Element {
7 int val, row, col;
8 bool operator>(const Element& other) const { return val > other.val; }
9};
10
11class Solution {
12public:
13 std::vector<int> smallestRange(std::vector<std::vector<int>>& nums) {
14 int k = nums.size();
15 std::priority_queue<Element, std::vector<Element>, std::greater<Element>> minHeap;
16 int currentMax = -1e9;
17
18 for (int i = 0; i < k; ++i) {
19 minHeap.push({nums[i][0], i, 0});
20 currentMax = std::max(currentMax, nums[i][0]);
21 }
22
23 int bestStart = 0, bestEnd = 1e9;
24
25 while (minHeap.size() == k) {
26 Element top = minHeap.top();
27 minHeap.pop();
28
29 if (currentMax - top.val < bestEnd - bestStart) {
30 bestStart = top.val;
31 bestEnd = currentMax;
32 }
33
34 if (top.col + 1 < nums[top.row].size()) {
35 int nextVal = nums[top.row][top.col + 1];
36 minHeap.push({nextVal, top.row, top.col + 1});
37 currentMax = std::max(currentMax, nextVal);
38 } else {
39 break;
40 }
41 }
42 return {bestStart, bestEnd};
43 }
44};
45
46int main() {
47 Solution sol;
48 std::vector<std::vector<int>> nums = {{4, 10, 15, 24, 26}, {0, 9, 12, 20}, {5, 18, 22, 30}};
49 std::vector<int> res = sol.smallestRange(nums);
50 std::cout << "[" << res[0] << ", " << res[1] << "]\n";
51 return 0;
52}

Time & Space Complexity

  • Time complexity: O(N log k) — Each of N elements pushed and popped at most once into heap of size k in O(log k) time.
  • Space complexity: O(k) — Heap maintains at most one element per list, using O(k) memory.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Sort Combined Elements and Check SubarraysO(N^2 * k)O(N)Tag each element with its list ID, merge and sort. Check every subarray window [i, j] to see if all k lists are present.Testing all subarray windows.
2.Better — Sorted Flatten + Sliding WindowO(N log N)O(N)Merge all elements into one sorted array with list IDs. Use a two-pointer sliding window with frequency map to find the minimal range containing all k lists.Sorting all elements upfront.
3.Optimal — Min-Heap K-Way Pointer TrackingOptimalO(N log k)O(k)Store current active element from each of the k lists in a Min-Heap of size k. Range is [minHeap.top(), currentMax]. Repeatedly pop min, update answer, and push next element from that list.None. Perfectly optimal.

Common Pitfalls & Crucial Edge Cases

Trying to advance the maximum element

Advancing the maximum only makes the range larger; you must advance the minimum element to shrink the lower bound.

Continuing after any list is exhausted

Once any list runs out, you can no longer pick an element from that list with a higher value, so no smaller valid range can be formed.

Tie-breaking condition

Range [a, b] is preferred over [c, d] if b - a == d - c and a < c.

Crucial Edge Cases to Validate:

  • k = 1 — Smallest range is simply [nums[0][0], nums[0][0]] with length 0.
  • All lists contain identical elements — Range has length 0 (e.g. [5, 5]).
  • Lists of very different lengths — When the shortest list runs out of elements, algorithm terminates immediately.
  • Negative numbers — Comparator handles negative integers correctly without overflow.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the analogy to Merge k Sorted Lists: both use a Min-Heap of size k, but here we track a running global maximum.
  2. Mention the Sliding Window alternative on the flattened array to demonstrate breadth of knowledge.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we terminate the search as soon as the pointer of ANY single list reaches the end?

Back to DSA Sheet