Merge Sorted Feeds
MediumHeap / Priority Queue
Problem
A monitoring service collects event timestamps from several servers. Each server's feeds[i] is already sorted in non-decreasing order. Merge all feeds into one list sorted in non-decreasing order.
Some feeds may be empty, and there may be no feeds at all.
Example 1
- Input:
- feeds = [[1, 4, 9], [2, 3, 10], [5]]
- Output:
- [1, 2, 3, 4, 5, 9, 10]
Example 2
- Input:
- feeds = [[], [7], []]
- Output:
- [7]
Example 3
- Input:
- feeds = []
- Output:
- []
Constraints
- 0 ≤ feeds.length ≤ 10^4
- 0 ≤ feeds[i].length ≤ 500
- Total number of timestamps N ≤ 10^5
- -10^9 ≤ feeds[i][j] ≤ 10^9
- Each feeds[i] is sorted in non-decreasing order.
Hint
Show the first hint
The next value of the output must be the head of one of the k feeds.
Walkthrough
How to approach it
01Clarify before coding
- Are duplicates kept? Yes, every timestamp appears in the output.
- Can feeds be empty, or the list of feeds itself be empty? Yes to both.
- Do we need to keep track of which feed a value came from? Not for the output, but the algorithm needs it internally.
02Brute force
Concatenate every feed and sort the result. Alternatively, merge feeds pairwise one after another.
Cost: Concatenate-and-sort is O(N log N) and ignores the existing order. Merging one by one is O(N·k) because early elements are re-copied in every merge.
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.