Loading
Loading
Several weather stations each log the minutes at which they detected a gust, in sorted order. A meteorologist wants the shortest stretch of time during which every station detected at least one gust.
Given lists, where each row is a non-empty sorted list of minutes, return [lo, hi], the narrowest window such that every row contains at least one value v with lo ≤ v ≤ hi. If several windows are equally narrow, return the one with the smallest lo.
lists = [[1, 8, 20], [4, 12], [6, 9, 30]]fronts 1, 4, 6window [1, 6], width 5 — best so farfronts 8, 4, 6row 0 advanced past 1: window [4, 8], width 4 — bestfronts 8, 12, 6row 1 advanced: window [6, 12], width 6fronts 8, 12, 9row 2 advanced: window [8, 12], width 4 — a tie, keep [4, 8]fronts 20, 12, 9window [9, 20], width 11fronts 20, 12, 30window [12, 30]; row 1 has nothing left, stop[4, 8]Sign in to keep a note here. It is free, and nobody else can see it.
Sign inExample 1
| 0 | 1 | 8 | 20 |
|---|---|---|---|
| 1 | 4 | 12 | |
| 2 | 6 | 9 | 30 |
[4, 8] contains 8, 4 and 6, width 4. [8, 12] is also width 4 but starts later.
Example 2
Sign in to open hints.
Struggling is where the learning happens. Open this once you have genuinely tried, or once the hints have run out.
O(N log k) time · O(k) space
Input. Run your code to watch it work on this input, one line at a time.
| 0 | 1 | 8 | 20 |
|---|---|---|---|
| 1 | 4 | 12 | |
| 2 | 6 | 9 | 30 |
Running code is turned off on this deployment. You can still read the problem, write code, use hints and the visualizer.
Tab moves focus out of the editor. Press Ctrl+M to let Tab indent instead.
No results yet
Run your code against the sample tests, or submit to run the full suite.
| 0 | 5 | |
|---|---|---|
| 1 | 5 | 7 |
Both stations logged minute 5, so the window is a single point.