Design an Ordered Stream

Difficulty: Easy | Acceptance: 82.60% | Paid: No Topics: Array, Hash Table, Design, Data Stream

There is a stream of n (idKey, value) pairs arriving in an arbitrary order, where idKey is an integer between 1 and n and value is a string. No two pairs have the same id.

Design a stream that returns the values in increasing order of their IDs by the order in which they were inserted. Implement the OrderedStream class:

OrderedStream(int n) Constructs the stream to take n values and sets a current ptr to 1. String[] insert(int idKey, String value) Inserts the pair (idKey, value) into the stream and then returns the chunk of values that have been inserted starting from the current pointer ptr. The chunk consists of all values in the stream with IDs in the range [ptr, idKey], and then updates ptr to the next ID that is not in the stream. If there are no values in the range, returns an empty list [].

• Examples
• Constraints
• Approach 1: Array with Pointer
• Approach 2: Hash Map with Pointer
• Approach 3: Sorting (Brute Force)

Examples

Example 1

Input
["OrderedStream", "insert", "insert", "insert", "insert", "insert"]
[[5], [3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]]

Output
[null, [], ["aaaaa"], ["bbbbb", "ccccc"], [], ["ddddd", "eeeee"]]

Explanation
OrderedStream os=OrderedStream(5);
os.insert(3, "ccccc"); // Inserts (3, "ccccc"), returns [].
os.insert(1, "aaaaa"); // Inserts (1, "aaaaa"), returns ["aaaaa"].
os.insert(2, "bbbbb"); // Inserts (2, "bbbbb"), returns ["bbbbb", "ccccc"].
os.insert(5, "eeeee"); // Inserts (5, "eeeee"), returns [].
os.insert(4, "ddddd"); // Inserts (4, "ddddd"), returns ["ddddd", "eeeee"].

Constraints

1 <= n <= 1000
1 <= id <= n
value.length == 5
value consists only of lowercase letters.
Each call to insert will use a unique id.

Approach 1: Array with Pointer

Intuition Since the IDs are strictly bounded between 1 and n, we can use a fixed-size array (or list) to store the values directly at their corresponding index. We maintain a pointer ptr that starts at 1. When a value is inserted, we place it in the array. If the inserted ID matches the current ptr, we can iterate forward from ptr to collect all consecutively available values, updating ptr as we go.

Steps

• Initialize an array of size n + 1 (to accommodate 1-based indexing) and a pointer ptr set to 1.
• In the insert method, store the value at the index idKey.
• If idKey is equal to ptr, enter a loop to collect values starting from ptr while the array at that index is not empty.
• Append each found value to the result list and increment ptr.
• Return the result list.

class OrderedStream:
    def __init__(self, n: int):
        self.stream = [""] * (n + 1)
        self.ptr = 1

    def insert(self, idKey: int, value: str) -> list[str]:
        self.stream[idKey] = value
        res = []
        while self.ptr < len(self.stream) and self.stream[self.ptr] != "":
            res.append(self.stream[self.ptr])
            self.ptr += 1
        return res

Complexity

• Time: O(k) where k is the length of the returned chunk. Amortized O(1) per insertion since each element is visited at most once.
• Space: O(n) to store the stream.
• Notes: This is the most optimal approach for this problem due to the bounded ID range.

Approach 2: Hash Map with Pointer

Intuition If the ID range were not bounded or extremely sparse, a Hash Map (Dictionary) would be preferred to store values. The logic remains similar to the array approach: store the value and check if the current pointer exists in the map to form a consecutive chunk.

Steps

• Initialize a Hash Map and a pointer ptr set to 1.
• In insert, add the (idKey, value) pair to the map.
• If idKey equals ptr, iterate while ptr exists as a key in the map.
• Add the value at ptr to the result and increment ptr.
• Return the result.

class OrderedStream:
    def __init__(self, n: int):
        self.stream = {}
        self.ptr = 1

    def insert(self, idKey: int, value: str) -> list[str]:
        self.stream[idKey] = value
        res = []
        if idKey == self.ptr:
            while self.ptr in self.stream:
                res.append(self.stream[self.ptr])
                self.ptr += 1
        return res

Complexity

• Time: O(k) where k is the length of the returned chunk.
• Space: O(n) to store the stream.
• Notes: Slightly higher constant factors for hash lookups compared to array indexing, but more flexible for non-contiguous IDs.

Approach 3: Sorting (Brute Force)

Intuition A naive approach is to store all inserted pairs in a list. On every insertion, we sort the list by ID and then scan to find the longest consecutive sequence starting from the current pointer. This is inefficient but demonstrates the logic without relying on direct index access or hash maps.

Steps

• Initialize an empty list to store pairs and ptr = 1.
• In insert, add the new [idKey, value] to the list.
• Sort the list by the ID (the first element of the pair).
• Iterate through the sorted list to find values matching ptr, ptr+1, etc.
• Return the consecutive chunk found.

class OrderedStream:
    def __init__(self, n: int):
        self.stream = []
        self.ptr = 1

    def insert(self, idKey: int, value: str) -> list[str]:
        self.stream.append((idKey, value))
        self.stream.sort(key=lambda x: x[0])
        res = []
        curr = self.ptr
        # Find consecutive sequence starting from ptr
        # We iterate through sorted list to find matches
        # This is inefficient O(N log N) per insert
        temp_ptr = self.ptr
        for k, v in self.stream:
            if k == temp_ptr:
                res.append(v)
                temp_ptr += 1
        
        if res:
            self.ptr = temp_ptr
        return res

Complexity

• Time: O(m log m) per insertion, where m is the total number of elements inserted so far. This is due to sorting the list on every operation.
• Space: O(n) to store the stream.
• Notes: Highly inefficient compared to the pointer approach. Used here only for comparison.