1656. Design an Ordered Stream

Problem¶

Implement OrderedStream(n) for unique IDs from 1 to n, arriving in any order. Each insert(idKey, value) returns the longest consecutive chunk starting at the next ID not yet returned; stop at the first missing ID.

OrderedStream(3)
insert(3, "ccccc") → []                  next ID: 1
insert(1, "aaaaa") → ["aaaaa"]           next ID: 2
insert(2, "bbbbb") → ["bbbbb", "ccccc"]  next ID: 4

class OrderedStream:
    def __init__(self, n: int):


    def insert(self, idKey: int, value: str) -> list[str]:

Key trick¶

Store values by ID and maintain a pointer to the next unreturned ID; the pointer only moves forward.

Trap¶

Do not skip missing IDs or return values twice; also account for IDs being one-based while Python lists are zero-based.

Why is it interesting?¶

One insertion can release many buffered values, yet every value is visited only once across all insertions.

Python solution¶

class OrderedStream:
    def __init__(self, n: int):
        self.values = [None] * n
        self.idx = 0  # Index of the next value to return.

    def insert(self, idKey: int, value: str) -> list[str]:
        self.values[idKey - 1] = value
        res = []

        # Emit everything available before the first gap.
        while (
            self.idx < len(self.values)
            and self.values[self.idx] is not None
        ):
            res.append(self.values[self.idx])
            self.idx += 1

        return res

Time: Initialization takes \(O(n)\). An insertion returning \(k\) values takes \(O(k + 1)\); all \(n\) insertions together take \(O(n)\).

Space: \(O(n)\) persistent storage and \(O(k)\) for a returned chunk.

Comment on my solution¶

Your solution is correct and optimal. The local i and final update of self.start are perfectly valid; checking is not None instead of truthiness makes the missing-value sentinel explicit, although your check is safe under the nonempty-string constraint.

# WORKS
class OrderedStream:
    def __init__(self, n: int):
        self.values = [None] * n
        self.start = 0

    def insert(self, idKey: int, value: str) -> list[str]:
        self.values[idKey - 1] = value
        res = []
        i = self.start
        while i < len(self.values) and self.values[i]:
            res.append(self.values[i])
            i += 1
        self.start = i
        return res