Combine Sorted Linked Lists

Merge k sorted streams into a single sorted stream. This tests your ability to efficiently manage multiple sorted data sources and is a good indicator of your heap data structure skills.

heappriority queuemergingsorted streamsdata structures

Problem Statement

You are given k infinitely long, sorted integer streams. Each stream provides numbers in ascending order. Design an algorithm to output a single sorted stream that merges all k input streams. You only have access to the 'next' element of each stream at any given time.

Example 1

Input: Streams: [[1, 5, 9, ...], [2, 4, 6, ...], [3, 7, 11, ...]]

Output: Merged Stream: 1, 2, 3, 4, 5, 6, 7, 9, 11, ...

The output stream merges the elements from all three input streams while maintaining ascending order.

Example 2

Input: Streams: [[-5, 0, 5, ...], [-10, -2, 1, ...], [20, 25, 30, ...]]

Output: Merged Stream: -10, -5, -2, 0, 1, 5, 20, 25, 30, ...

This example includes negative numbers to demonstrate the algorithm's ability to handle various integer values.

Constraints

-k >= 1 (There is at least one stream)
-The streams are infinitely long, but you only need to output a finite number of elements for testing purposes.
-Each stream is sorted in ascending order.
-Integer values can be positive, negative, or zero.
-Assume you have a Stream interface with a 'next()' method that returns the next integer or None if the stream is exhausted (though the streams are infinite in theory).

Brute Force Approach

The brute force approach would be like having a line of waiters, each holding a tray of sorted dishes (streams). At each step, you'd have to ask every waiter what the next dish on their tray is, find the smallest one, serve it, and then repeat. This requires checking all k streams at each step, leading to inefficiency.

TimeO(n*k)

SpaceO(1)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem