Code Implementation

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

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

class OrderedStream {
public:
    vector<string> stream;
    int ptr;
    OrderedStream(int n) {
        stream = vector<string>(n);
        ptr = 0;
    }
    
    vector<string> insert(int idKey, string value) {
        stream[idKey - 1] = value;
        vector<string> res;
        while (ptr < stream.size() && !stream[ptr].empty()) {
            res.push_back(stream[ptr]);
            ptr++;
        }
        return res;
    }
};
      

class OrderedStream {
    private String[] stream;
    private int ptr;

    public OrderedStream(int n) {
        stream = new String[n];
        ptr = 0;
    }
    
    public List<String> insert(int idKey, String value) {
        stream[idKey - 1] = value;
        List<String> res = new ArrayList<>();
        while (ptr < stream.length && stream[ptr] != null) {
            res.add(stream[ptr]);
            ptr++;
        }
        return res;
    }
}
      

var OrderedStream = function(n) {
    this.stream = new Array(n);
    this.ptr = 0;
};

OrderedStream.prototype.insert = function(idKey, value) {
    this.stream[idKey - 1] = value;
    const res = [];
    while (this.ptr < this.stream.length && this.stream[this.ptr] !== undefined) {
        res.push(this.stream[this.ptr]);
        this.ptr += 1;
    }
    return res;
};
      

Problem Description

You are asked to design an Ordered Stream that stores n values, each associated with a unique idKey from 1 to n. The stream allows you to insert values in any order, but you must output values in order (starting from the smallest available idKey) when possible.

When you insert a value with idKey, you return a list of all consecutive values starting from the current pointer position (ptr) if they are present. The pointer advances as you output values, and you skip over missing entries.

Constraints:

• Each idKey is unique and used only once.
• Values are inserted in any order, but output must always be in ascending order of idKey.
• No value is reused or overwritten.

Thought Process

The challenge is to support out-of-order insertions while always outputting the next available sequence in order. A brute-force approach might scan the entire list on every insert, but that's inefficient.

Instead, we can think of the stream as a conveyor belt. Each slot is filled only once, and we have a pointer (ptr) that marks the next expected value. When we insert a value, if it fills the slot at the pointer, we can now "release" all consecutive filled slots starting from the pointer. If not, we wait for more insertions.

This approach avoids unnecessary checks and only outputs values when possible, keeping everything efficient and in order.

Solution Approach

Let's break down the solution step by step:

1. Data Structure:
   • Use an array (or list) of size n to store the values at their respective indices (idKey - 1).
   • Maintain a pointer (ptr) that always points to the next value to output.
2. Insert Operation:
   • When insert(idKey, value) is called, place value at stream[idKey - 1].
   • If idKey - 1 equals ptr, start collecting values from ptr forward as long as slots are filled.
   • Return the collected list, and update ptr to the next empty slot.
   • If idKey - 1 is not equal to ptr, return an empty list.
3. Efficiency:
   • Each insert operation only checks consecutive slots starting from ptr, so no unnecessary scanning occurs.
   • Each value is output exactly once.

This design ensures all operations are efficient and maintain the required order.

Example Walkthrough

Let's consider n = 5 and the following sequence of operations:

• insert(3, "ccccc") → [] (since ptr is at 0, but idKey is 3)
• insert(1, "aaaaa") → ["aaaaa"] (now slot 0 is filled, so output it and move ptr to 1)
• insert(2, "bbbbb") → ["bbbbb", "ccccc"] (slots 1 and 2 are now filled, output both and move ptr to 3)
• insert(5, "eeeee") → [] (slot 4 is filled, but ptr is at 3, which is still empty)
• insert(4, "ddddd") → ["ddddd", "eeeee"] (slots 3 and 4 are now filled, output both and ptr moves to 5)

At each step, we only output values when all previous values have been inserted, preserving the order.

Time and Space Complexity

Brute-force Approach: If we scanned the entire array on every insert, time complexity would be O(n^2) for n inserts.

Optimized Approach:

• Time Complexity: Each value is checked and output exactly once, so total time for all operations is O(n).
• Space Complexity: We use an array of size n, so space is O(n).

Summary

The Ordered Stream problem is elegantly solved by using a simple array and a moving pointer. This approach ensures that insertions are handled efficiently, and outputs are always in the correct order, regardless of the order of insertions. The key insight is to only output values when all previous slots have been filled, and to never revisit already-processed slots, achieving optimal time and space complexity.