Loading
Loading
A news aggregator pulls timestamped stories from several publishers. Each publisher's feed already arrives sorted by timestamp, oldest first, but the aggregator needs one combined timeline.
Given feeds, a list of sorted integer lists (some may be empty), return a single sorted list containing every timestamp from every feed, duplicates included.
feeds = [[1, 4, 9], [2, 3, 10], [5]]heap = {1, 2, 5}the front of each feedout = [1]pop 1 from feed 0, push its next value 4out = [1, 2]pop 2 from feed 1, push 3out = [1, 2, 3]pop 3, push 10out = [1, 2, 3, 4]pop 4, push 9out = [1, 2, 3, 4, 5, 9, 10]feed 2 is exhausted; drain the rest[1, 2, 3, 4, 5, 9, 10]Sign in to keep a note here. It is free, and nobody else can see it.
Sign inExample 1
| 0 | 1 | 4 | 9 |
|---|---|---|---|
| 1 | 2 | 3 | 10 |
| 2 | 5 |
Repeatedly take the smallest front value among the feeds.
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 | 4 | 9 |
|---|---|---|---|
| 1 | 2 | 3 | 10 |
| 2 | 5 |
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 | 3 | 3 |
|---|---|---|
| 1 | ||
| 2 | 1 | 3 |
The empty feed contributes nothing; every duplicate is kept.