Smallest Covering Range
Problem
Several weather stations each report a sorted list of temperatures: lists[i] is sorted in non-decreasing order and is non-empty. Find the narrowest range [a, b] such that every station has at least one temperature t with a ≤ t ≤ b.
A range [a, b] is narrower than [c, d] if b - a < d - c, or if the widths are equal and a < c. Return the narrowest range as [a, b].
Example 1
- Input:
- lists = [[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]]
- Output:
- [20, 24]
24 from the first list, 20 from the second, 22 from the third. No range of width less than 4 touches all three lists.
Example 2
- Input:
- lists = [[1, 2, 3], [1, 2, 3], [1, 2, 3]]
- Output:
- [1, 1]
Example 3
- Input:
- lists = [[7]]
- Output:
- [7, 7]
Constraints
- 1 ≤ lists.length ≤ 3500
- 1 ≤ lists[i].length ≤ 50
- -10^5 ≤ lists[i][j] ≤ 10^5
- Each lists[i] is sorted in non-decreasing order.
Hint
Show the first hint
Pick one value from each list. The range they define is [min, max] of the picks. How could you improve it?
Walkthrough
How to approach it
01Clarify before coding
- Must the range contain at least one value from every list? Yes, at least one each.
- How are equal widths broken? Smaller start wins.
- Are lists sorted and non-empty? Yes, both.
02Brute force
For each candidate start a (every value in any list), find in each list the first value ≥ a; the end is the max of those. Keep the narrowest.
Cost: O(N · k · log L) with binary search (N total values, k lists, L list length), or O(N · N) with scans: too slow for 3500 lists of 50.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.