Merge K Sorted Sensor Data Streams
In large-scale IoT deployments, collecting and processing data from numerous sensors is a common task. Often, each sensor generates a stream of readings that are naturally ordered by time or value. For comprehensive analysis, it's frequently necessary to consolidate these individual sensor streams into a single, unified, and globally sorted data stream. This problem challenges you to efficiently merge k such sorted data streams, where the total volume of data can be very large, making in-memory storage of all streams impractical.
Implement the mergeKSortedStreams function. This function takes an array of StreamIterator objects, where each iterator represents a sorted stream of numbers. Your goal is to merge all these streams into a single, sorted array of numbers containing all readings from all input streams.
You must interact with each stream exclusively through its StreamIterator interface. Do not assume the underlying data structure of the stream.
The StreamIterator interface is defined as follows:
interface StreamIterator {
/**
* Advances the iterator and returns the next value in the stream.
* If the stream has more elements, returns `{ value: number, done: false }`.
* If the stream is exhausted, returns `{ value: undefined, done: true }`.
*/
next(): { value: number | undefined, done: boolean };
}
Input:
streams: An array of StreamIterator objects. Each StreamIterator provides numbers in non-decreasing order.Output:
number[] representing a single, sorted array containing all numbers from all input streams.StreamIterator objects might be empty from the start (i.e., their first next() call returns { value: undefined, done: true }). Your solution should handle these gracefully.Examples
Example 1
Input:
streams = [[1,5,9], [2,3,8], [4,6,7]]
Output:
[1,2,3,4,5,6,7,8,9]
Note:
Merges three sorted streams into a single sorted array.
Example 2
Input:
streams = [[10], [], [1,2]]
Output:
[1,2,10]
Note:
Handles empty streams and streams with a single element.
Example 3
Input:
streams = [[1,1,3], [1,2,2], [3]]
Output:
[1,1,1,2,2,3,3]
Note:
Preserves duplicate values and merges streams with varying lengths.
Constraints
1 <= streams.length <= 10^5 (number of input streams, k)N <= 10^6.0 <= reading <= 10^9 for any number returned by StreamIterator.next().StreamIterator.next() method is synchronous.StreamIterator implementations (e.g., next() returning non-numeric values or violating sorted order).N total elements efficiently, typically aiming for O(N log K) where K is the number of streams.O(K) to store elements from active streams.Loading editor...