Show problems as
Classic problem #23HardArrayDivide and ConquerHeap (Priority Queue)Merge Sort

Merge k Sorted Lists

Real-world version: Merge Shard Streams
Tracked in this browser only
Read Merge k Sorted Lists on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstMerge K Lists · Priority Queues, animated step by step

A monitoring fleet writes its signed temperature readings into shards. You receive streams, a list of those shards. Each shard is already laid out from lowest reading to highest, and a shard may carry nothing at all.

Fold the shards into a single array that runs from lowest reading to highest. Every reading is kept, so a value stored in three shards shows up three times in the result.

The shard count can be far larger than the readings inside any one shard, so pull from all shard fronts together rather than flattening first.

Examples

Example 1

Input
streams = [[-8, -1, 4], [-3, 0], [2, 2, 9]]
Output
[-8, -3, -1, 0, 2, 2, 4, 9]

Eight readings from three shards line up as one run, and the value 2 stays twice because two shards recorded it.

Example 2

Input
streams = [[3, 4, 5], [1, 2]]
Output
[1, 2, 3, 4, 5]

The second shard supplies both of the two lowest readings before the first shard contributes anything.

Example 3

Input
streams = [[7, 7], [7]]
Output
[7, 7, 7]

Repeats spread across shards are all retained, so the result holds three copies.

Constraints

  • k == streams.length
  • 0 <= k <= 10^4
  • 0 <= streams[i].length <= 500
  • -10^4 <= streams[i][j] <= 10^4
  • Each streams[i] is already in non-decreasing order
  • The total number of readings across all shards is at most 10^4

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def merge_streams(streams: list[list[int]]) -> list[int]:
Java
public int[] mergeStreams(int[][] streams)

More on the same topics