Domain 1EasyCORE

Design an Ordered Stream

The problem requires designing an `OrderedStream` class that manages a stream of `(idKey, value)` pairs and returns values in increasing order of their IDs. The class should support the following operations: - **Constructor (`__init__`)**: Initializes the stream with a capacity `n`. - **Insert Method (`insert`)**: Inserts a pair `(idKey, value)` into the stream and returns the largest possible chunk of consecutive values starting from the smallest unprocessed ID.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Design

1656. Design an Ordered Stream

Model: qwen2.5-coder:14b
Topics: Array,Design
FAANG asked: 0
Acceptance rate: 82.1%


Problem Breakdown

The problem requires designing an OrderedStream class that manages a stream of (idKey, value) pairs and returns values in increasing order of their IDs. The class should support the following operations:

  • Constructor (__init__): Initializes the stream with a capacity n.
  • Insert Method (insert): Inserts a pair (idKey, value) into the stream and returns the largest possible chunk of consecutive values starting from the smallest unprocessed ID.

Inputs:

  • n: The number of elements in the stream.
  • idKey: An integer representing the position in the stream.
  • value: A string associated with the idKey.

Outputs:

  • A list of strings that are the largest possible chunk of consecutive values starting from the smallest unprocessed ID.

Implicit Constraints:

  • The idKey is between 1 and n.
  • No two pairs have the same idKey.
  • Each call to insert will be unique.
  • Exactly n calls will be made to insert.

Intuition

A brute-force approach would involve maintaining an array of size n and iterating through it each time to find the largest chunk of consecutive values. This approach is inefficient because it requires scanning the entire array on every insertion, leading to a time complexity of O(n) per insertion.

The key insight is to use a pointer that keeps track of the smallest unprocessed ID. When inserting a new value, we check if it matches the current pointer. If it does, we move the pointer forward and collect all consecutive values starting from this point. This approach ensures that each insertion operation is efficient, with an amortized time complexity of O(1).

Approach

  1. Data Structure: Use an array to store the stream values and a pointer (self.ptr) to keep track of the smallest unprocessed ID.
  2. Initialization: Initialize the array with None values and set the pointer to 0.
  3. Insert Method:
    • Insert the value at the position corresponding to idKey.
    • If the current pointer matches the idKey, collect all consecutive non-None values starting from this point.
    • Move the pointer forward until a None value is encountered.

Complexity Analysis

  • Time Complexity: O(1) for each insertion operation on average. Although we might iterate through consecutive values, the total number of iterations across all insertions will be linear in terms of n.
  • Space Complexity: O(n) for storing the stream values.

Solution

class OrderedStream:

    def __init__(self, n: int):
        self.stream = [None] * n  # Initialize the stream with None values
        self.ptr = 0  # Pointer to track the smallest unprocessed ID

    def insert(self, idKey: int, value: str) -> List[str]:
        self.stream[idKey - 1] = value  # Insert the value at the correct position
        start = self.ptr
        
        # Collect all consecutive non-None values starting from the pointer
        while self.ptr < len(self.stream) and self.stream[self.ptr] is not None:
            self.ptr += 1
        
        return self.stream[start:self.ptr]

Edge Cases Handled

  • Initial Insertion: If the first insertion is at idKey = 1, it will immediately return a chunk containing this value.
  • Non-Consecutive Inserts: If inserts are made out of order, the method will only return consecutive values starting from the smallest unprocessed ID.
  • Full Stream Insertion: When all elements are inserted in order, each insertion will return the next consecutive chunk until the end of the stream.