Smallest Range Covering Elements from K Lists

118.9k
0

Given k non-empty integer lists sorted in non-decreasing order, find a range [left, right] containing at least one value from every list.

Range [a, b] is smaller than range [c, d] when b - a < d - c. For equal widths, the range with the smaller starting value is smaller. Return both endpoints of the smallest range.

Example 1

Input: nums = [[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]]
Output: [20, 24]
Explanation: Range [20, 24] contains 24 from the first list, 20 from the second list, and 22 from the third list. No valid range has a smaller width.

Example 2

Input: nums = [[1, 2, 3], [1, 2, 3], [1, 2, 3]]
Output: [1, 1]
Explanation: Value 1 appears in every list, so a zero-width range covers all lists.

Brute Force Approach

The goal is to find a small range that contains at least one value from every list. A simple way is to place all values together in sorted order while remembering which list each value came from. Then, any useful range appears as a contiguous window in this sorted sequence.

Expand the right boundary until the window contains all k lists. Once coverage is complete, move the left boundary forward to make the range as small as possible while still keeping all lists represented.

Algorithm

  • Store every value together with its source-list index, because the list identity is needed to check whether all lists are covered.

  • Sort all stored pairs by value so candidate ranges can be represented as contiguous windows.

  • Maintain a frequency count for each source list and a covered count to track how many different lists are currently present.

  • Move the right boundary forward:

    • Increase the frequency of its source list.

    • Increase covered when that list appears in the window for the first time.

  • While covered == k:

    • Compare the current range with the best range found so far.

    • Prefer the smaller range, and if both widths are equal, prefer the smaller left endpoint.

    • Remove the left value from the window and decrease its source frequency.

    • Decrease covered when that source list is no longer represented.

    • Move the left boundary forward.

  • Return the best range after processing the complete sorted sequence.

Dry Run

smallest-range-covering-elements-from-k-lists-brute-force

smallest-range-covering-elements-from-k-lists-brute-force

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Finds the smallest range with a sorted window.
vector<int> smallestRange(vector<vector<int>>& nums) {
int k = nums.size();
vector<pair<int, int>> merged;
// Preserve every value and the matching source list.
for (int listIndex = 0; listIndex < k; listIndex++) {
// Add every value before sorting the merged array.
for (int value : nums[listIndex]) {
merged.push_back({value, listIndex});
}
}
// Value order turns ranges into contiguous windows.
sort(merged.begin(), merged.end());
vector<int> frequency(k, 0);
int covered = 0;
int left = 0;
int bestLeft = merged[0].first;
int bestRight = merged.back().first;
// Expand each possible right boundary once.
for (int right = 0; right < merged.size(); right++) {
int rightList = merged[right].second;
// A first occurrence adds one covered list.
if (frequency[rightList] == 0) {
covered++;
}
frequency[rightList]++;
// Remove redundant left values from valid ranges.
while (covered == k) {
int currentLeft = merged[left].first;
int currentRight = merged[right].first;
int currentWidth = currentRight - currentLeft;
int bestWidth = bestRight - bestLeft;
// Prefer a shorter or earlier equal range.
if (currentWidth < bestWidth ||
(currentWidth == bestWidth &&
currentLeft < bestLeft)) {
bestLeft = currentLeft;
bestRight = currentRight;
}
int leftList = merged[left].second;
frequency[leftList]--;
// Losing a final occurrence breaks coverage.
if (frequency[leftList] == 0) {
covered--;
}
left++;
}
}
return {bestLeft, bestRight};
}
};
// Driver code
int main() {
vector<vector<int>> nums = {
{4, 10, 15, 24, 26},
{0, 9, 12, 20},
{5, 18, 22, 30}
};
Solution obj;
vector<int> answer = obj.smallestRange(nums);
cout << "[" << answer[0] << ", " << answer[1] << "]" << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N log N), where N is the total number of values across all k lists. Collecting all values takes O(N), sorting takes O(N log N), and both sliding-window pointers move at most N times.

Space Complexity: O(N + k), because the merged value-source pairs store N entries and the frequency array stores one count for each of the k lists.

Optimal Approach

The sorted-window approach stores and sorts all N values. Sorted input lists already provide enough order for a smaller structure: one current candidate from each list can represent a valid range.

A min-heap exposes the smallest current candidate, while a separate value tracks the largest current candidate. Advancing only the list owning the minimum value is the sole move capable of raising the left boundary and creating a tighter range.

Algorithm

  • Begin by pushing the first value from every list into a min-heap, because one candidate per list guarantees complete coverage.

  • Track the largest inserted value as currentMaximum, allowing the heap minimum and the tracked maximum to define a valid range.

  • Initialize the best range from the first k candidates so every later comparison starts from a valid answer.

  • Remove the smallest heap entry and compare the resulting range, because only the smallest candidate limits the current left boundary.

  • Apply width and left-endpoint comparisons together so equal-width candidates follow the required tie rule.

  • Stop after the removed entry reaches the end of a list, preventing incomplete candidate sets from entering the search.

  • Push the next value from the removed entry's source list and raise currentMaximum when necessary, preserving one candidate per list.

  • Return the best endpoints after exhaustion so only fully covered candidate ranges influence the answer.

Dry Run

smallest-range-covering-elements-from-k-lists-optimal-approach-v3

smallest-range-covering-elements-from-k-lists-optimal-approach-v3

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Finds the smallest range with k-way merging.
vector<int> smallestRange(vector<vector<int>>& nums) {
int k = nums.size();
priority_queue<vector<int>,
vector<vector<int>>,
greater<vector<int>>> minHeap;
int currentMaximum = INT_MIN;
// Add one starting candidate from every list.
for (int listIndex = 0; listIndex < k; listIndex++) {
int value = nums[listIndex][0];
minHeap.push({value, listIndex, 0});
currentMaximum = max(currentMaximum, value);
}
int bestLeft = minHeap.top()[0];
int bestRight = currentMaximum;
// Complete coverage exists before every extraction.
while (true) {
vector<int> entry = minHeap.top();
minHeap.pop();
int currentMinimum = entry[0];
int listIndex = entry[1];
int elementIndex = entry[2];
int currentWidth = currentMaximum - currentMinimum;
int bestWidth = bestRight - bestLeft;
// Prefer a shorter or earlier equal range.
if (currentWidth < bestWidth ||
(currentWidth == bestWidth &&
currentMinimum < bestLeft)) {
bestLeft = currentMinimum;
bestRight = currentMaximum;
}
// An exhausted list prevents future coverage.
if (elementIndex + 1 == nums[listIndex].size()) {
break;
}
int nextIndex = elementIndex + 1;
int nextValue = nums[listIndex][nextIndex];
// The next value restores the missing source list.
minHeap.push({nextValue, listIndex, nextIndex});
// The largest active value sets the right boundary.
currentMaximum = max(currentMaximum, nextValue);
}
return {bestLeft, bestRight};
}
};
// Driver code
int main() {
vector<vector<int>> nums = {
{4, 10, 15, 24, 26},
{0, 9, 12, 20},
{5, 18, 22, 30}
};
Solution obj;
vector<int> answer = obj.smallestRange(nums);
cout << "[" << answer[0] << ", " << answer[1] << "]" << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N log k), at most N heap removals and insertions operate on a heap containing k entries.

Space Complexity: O(k), the heap stores one active entry from every list and only constant extra variables are retained.

Interview follow-up Questions

The smaller left endpoint wins. For ranges [1, 3] and [5, 7], both widths equal 2, so [1, 3] is selected.

Heap

Read Similar Blogs

Heap

Merge K Sorted Linked Lists

Given an array lists containing the heads of k singly linked lists, merge every node into one linked list sorted in non-decreasing order. Every input list is already sorted in non-decreasing order....

92.2k
Heap

Introduction to Heap

Imagine an emergency room with several waiting patients. The patient needing the most urgent care is treated first, even if another patient arrived earlier. The next choice depends on priority, not...

72.8k
Heap

Meeting Rooms II

Given an array intervals , where every entry [start, end] represents one meeting, find the minimum number of conference rooms needed to hold every meeting without a scheduling conflict. An end time...

57.7k
Comments0