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.

#632

Hard

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

最小区间

你有 k 个非递减排列的整数列表。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。我们定义如果 b-a 或者在 b-a == d-c 时 a ，则区间 [a,b] 比 [c,d] 小。示例 1：输入： nums = [[4,10,15,24,26], [0,9,1…

数组哈希表贪心滑动窗口排序

题目描述

你有 k 个 非递减排列 的整数列表。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。

我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。

示例 1：

输入：nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
输出：[20,24]
解释： 
列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。

示例 2：

输入：nums = [[1,2,3],[1,2,3],[1,2,3]]
输出：[1,1]

提示：

nums.length == k
1 <= k <= 3500
1 <= nums[i].length <= 50
-10⁵ <= nums[i][j] <= 10⁵
nums[i] 按非递减顺序排列

lightbulb

解题思路

方法一：排序 + 滑动窗口

我们将每个数字 $x$ 及其所在的组 $i$ ，构成数据项 $(x, i)$ ，存放在一个新的数组 $t$ 中，然后对 $t$ 按照数字的大小进行排序（类似于将多个有序数组合并成一个新的有序数组）。

接下来，我们遍历 $t$ 中的每个数据项，只看其中数字所在的组，用哈希表记录滑动窗口内的数字出现的组，如果组数为 $k$ ，说明当前窗口满足题目要求，此时算出窗口的起始和结束位置，更新答案。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为所有数组中数字的个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

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

speed

复杂度分析

指标	值
时间	O(n \log n)
空间	O(n)

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#621 任务调度器 #1054 距离相等的条形码 #1338 数组大小减半