#632

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Smallest Range Covering Elements from K Lists

Find the minimal range covering at least one number from each of k sorted lists using array scanning and hash lookup efficiently.

array hash table greedy sliding window sorting

Problem Statement

You are given k lists of integers, each sorted in non-decreasing order. Your task is to identify the smallest continuous range [a, b] such that at least one number from each list falls within this range. The range is considered smaller if its length is shorter, or if lengths are equal, the range starting earlier is preferred.

Implement a function that accepts an array of k sorted lists and returns the smallest range covering all lists. Example: given nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]], the output should be [20,24] because each list contributes at least one number within this interval.

Examples

Example 1

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

Output: [20,24]

List 1: [4, 10, 15, 24,26], 24 is in range [20,24]. List 2: [0, 9, 12, 20], 20 is in range [20,24]. List 3: [5, 18, 22, 30], 22 is in range [20,24].

Example 2

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

Output: [1,1]

Example details omitted.

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.

Solution Approach

Flatten and sort all numbers

Convert each list element into a tuple of (value, list_index) and combine all lists into a single array. Sort this array by value to allow sequential scanning while maintaining knowledge of which list each number belongs to.

Use sliding window with hash map

Maintain a window over the sorted array and track the count of elements from each list using a hash map. Expand the window to include at least one number from every list, then attempt to shrink from the left to minimize the range while preserving coverage.

Update minimal range efficiently

Whenever the window contains all k lists, compare the current window's range with the recorded minimal range. Replace the minimal range if the current window is smaller or starts earlier with the same length. Continue until the end of the array is reached.

Complexity Analysis

Metric	Value
Time	O(n \log n)
Space	O(n)

Flattening and sorting takes O(n log n) where n is the total number of elements. Sliding window passes over each element once, and hash map operations are O(1) average, leading to O(n) additional time. Space is O(n) for storing the flattened array and hash counts.

What Interviewers Usually Probe

Pay attention to maintaining a valid window covering all lists as early as possible.
Hash map usage shows understanding of list indexing and coverage tracking.
Efficiency concerns arise if you attempt nested loops over lists rather than flattening and scanning.

Common Pitfalls or Variants

Common pitfalls

Assuming numbers are uniformly distributed and skipping window shrink checks, causing suboptimal range selection.
Ignoring duplicate numbers across lists, which may miscount coverage in the hash map.
Overcomplicating with separate priority queues per list instead of one global sorted structure.

Follow-up variants

Return all ranges that tie for minimal length instead of just the first found.
Allow unsorted input lists, requiring initial sorting of each list before flattening.
Compute smallest range with exactly one number from each list, enforcing single selection per list.

FAQ

What is the best approach for Smallest Range Covering Elements from K Lists?

Flatten all numbers with their source list indices, sort them, then use a sliding window with a hash map to track coverage and find the minimal range.

Can this problem be solved without sorting?

Sorting is essential for efficient scanning; without it, you risk O(n^2) checks and missing minimal range opportunities.

How do you handle duplicate numbers across different lists?

Include duplicates in the flattened array but ensure the hash map counts the number of lists covered, not individual duplicates, to maintain correct coverage.

What are common mistakes in the array scanning plus hash lookup approach?

Failing to shrink the window correctly, miscounting covered lists, or forgetting to update the minimal range whenever a valid window is found.

Does the problem pattern favor greedy or heap strategies?

The primary pattern is array scanning plus hash lookup. A heap can help in alternative implementations, but the most direct method uses sorted array and sliding window for minimal range.

terminal

Solution

Solution 1: Sorting + Sliding Window

We construct a data item $(x, i)$ for each number $x$ and its group $i$, and store these items in a new array $t$. Then, we sort $t$ by the value of the numbers (similar to merging multiple sorted arrays into a new sorted array).

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        t = [(x, i) for i, v in enumerate(nums) for x in v]
        t.sort()
        cnt = Counter()
        ans = [-inf, inf]
        j = 0
        for i, (b, v) in enumerate(t):
            cnt[v] += 1
            while len(cnt) == len(nums):
                a = t[j][0]
                x = b - a - (ans[1] - ans[0])
                if x < 0 or (x == 0 and a < ans[0]):
                    ans = [a, b]
                w = t[j][1]
                cnt[w] -= 1
                if cnt[w] == 0:
                    cnt.pop(w)
                j += 1
        return ans

Solution 2: Priority Queue (Heap)

#### TypeScript

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        t = [(x, i) for i, v in enumerate(nums) for x in v]
        t.sort()
        cnt = Counter()
        ans = [-inf, inf]
        j = 0
        for i, (b, v) in enumerate(t):
            cnt[v] += 1
            while len(cnt) == len(nums):
                a = t[j][0]
                x = b - a - (ans[1] - ans[0])
                if x < 0 or (x == 0 and a < ans[0]):
                    ans = [a, b]
                w = t[j][1]
                cnt[w] -= 1
                if cnt[w] == 0:
                    cnt.pop(w)
                j += 1
        return ans

Continue Practicing

#621 task scheduler #1054 distant barcodes #1338 reduce array size to the half