Smallest Range Covering Elements from K Lists

Smallest Range Covering Elements from K Lists - Problem

Array Hash Table Greedy Sliding Window Sorting Heap (Priority Queue) Hard

You have k lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k lists.

We define the range [a, b] is smaller than range [c, d] if b - a < d - c or a < c if b - a == d - c.

Return the smallest range as an array [start, end].

Input & Output

Example 1 — Basic Case

$ Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]

› Output: [20,24]

💡 Note: The range [20,24] covers list 1 (24), list 2 (20), and list 3 (22). This gives the minimum range of 4.

Example 2 — Minimum Size

$ Input: nums = [[1,2,3],[1,2,3],[1,2,3]]

› Output: [1,1]

💡 Note: All lists contain 1, so the optimal range is [1,1] with range 0.

Example 3 — Different Ranges

$ Input: nums = [[10,20],[15,25],[5,30]]

› Output: [15,20]

💡 Note: Range [15,20] covers 20 from list 1, 15 from list 2, and no direct element from list 3, but we need at least one from each. Actually [15,20] covers list 2 (15) and list 1 (20), but we need list 3. The correct answer would be [15,25] covering 20 from list 1, 15 from list 2, and 25 from list 3.

Constraints

nums.length == k
1 ≤ k ≤ 3500
1 ≤ nums[i].length ≤ 50
-10⁵ ≤ nums[i][j] ≤ 10⁵
nums[i] is sorted in non-decreasing order

Visualization

Tap to expand

Understanding the Visualization

Input

K sorted lists with different ranges of values

Process

Find range [a,b] that covers all lists with minimum span

Output

Return the smallest range as [start, end]

Key Takeaway

🎯 Key Insight: Use a priority queue to efficiently track the minimum element from each list while maintaining the maximum, creating a sliding window approach that finds the optimal range in O(n log k) time.

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to maintain a sliding window that contains exactly one element from each list. The priority queue approach is optimal, using a min heap to track the smallest elements while maintaining the maximum. This achieves O(n log k) time complexity and O(k) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - All Combinations	O(n^k)	O(k)	Try all possible pairs from different lists to find minimum range
Merge and Sliding Window	O(n log n)	O(n)	Merge all elements with source tracking, then use sliding window
Priority Queue (Min Heap) Approach	O(n log k)	O(k)	Use min heap to track smallest elements and sliding window technique

Brute Force - All Combinations — Algorithm Steps

Generate all combinations of k elements (one from each list)
For each combination, find min and max values
Track the combination with smallest range (max - min)

Visualization

Tap to expand

Step-by-Step Walkthrough

Input Lists

Three sorted lists with elements

Generate Combinations

Create all possible combinations (one from each list)

Find Minimum Range

Calculate range for each combination and find minimum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int* solution(int** nums, int* numsSizes, int numsSize, int* returnSize) {
    *returnSize = 2;
    int* result = (int*)malloc(2 * sizeof(int));
    
    // Simplified implementation for demo
    result[0] = 0;
    result[1] = 0;
    
    return result;
}

int main() {
    // Simplified input parsing
    int returnSize;
    int** nums = NULL;
    int* numsSizes = NULL;
    int numsSize = 0;
    
    int* result = solution(nums, numsSizes, numsSize, &returnSize);
    printf("[%d,%d]\n", result[0], result[1]);
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n^k)

Generate all combinations where n is average list length and k is number of lists

✓ Linear Growth

Space Complexity

O(k)

Store current combination of k elements

✓ Linear Space

89.2K Views

Medium Frequency

~35 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler