Design an Ordered Stream

easy design array hash map

Problem

You receive a stream of n string values, each tagged with a unique id from 1 to n, but the ids may arrive in any order. Build a class with one method insert(idKey, value) that stores the value at its id and then returns the longest run of values whose ids are consecutive and start at the smallest id not yet returned. If the id you just inserted is not the next one expected, return an empty list — those values wait until the gap is filled.

Inputn = 5; insert(3,"ccccc"), insert(1,"aaaaa"), insert(2,"bbbbb"), insert(5,"eeeee"), insert(4,"ddddd")

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

A pointer waits at id 1. Inserting 3 returns nothing (1 is still missing). Inserting 1 returns ["aaaaa"] and the pointer moves to 2. Inserting 2 sweeps up the already-present 3, so it returns ["bbbbb","ccccc"] and the pointer reaches 4. Inserting 5 returns nothing; inserting 4 finally releases both 4 and 5.

n (size)

insert ids (comma-separated)

class OrderedStream:
    def __init__(self, n):
        self.vals = [None] * (n + 1)
        self.ptr = 1
    def insert(self, idKey, value):
        self.vals[idKey] = value
        chunk = []
        while self.ptr < len(self.vals) and self.vals[self.ptr] is not None:
            chunk.append(self.vals[self.ptr])
            self.ptr += 1
        return chunk

class OrderedStream {
  constructor(n) {
    this.vals = new Array(n + 1).fill(null);
    this.ptr = 1;
  }
  insert(idKey, value) {
    this.vals[idKey] = value;
    const chunk = [];
    while (this.ptr < this.vals.length && this.vals[this.ptr] !== null) {
      chunk.push(this.vals[this.ptr]);
      this.ptr++;
    }
    return chunk;
  }
}

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

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

Explanation

The ids run from 1 to n and each one shows up exactly once, just not in order. Because the ids are dense and bounded, we do not even need a hash map — a plain array indexed by id is the perfect storage. We size it n + 1 so we can use ids directly as indices and ignore slot 0.

The whole trick is a single pointer (ptr) that remembers the smallest id we have not yet handed back. It starts at 1. When insert(idKey, value) is called, we drop the value into vals[idKey] and then ask a simple question: is the slot the pointer is waiting on now filled?

If vals[ptr] is filled, we collect it into the result, advance the pointer, and keep going as long as the next slot is also filled. This loop sweeps a contiguous run of arrived values in one shot. If the slot the pointer wants is still empty, the loop runs zero times and we return an empty list — the inserted value simply waits in its slot for the gap before it to close.

Trace the example with n = 5. Insert id 3 → pointer still at 1, slot 1 empty, return []. Insert id 1 → slot 1 fills, return ["aaaaa"], pointer moves to 2. Insert id 2 → slot 2 fills and slot 3 was already filled, so the loop sweeps both: return ["bbbbb","ccccc"], pointer now at 4. Insert id 5 → slot 4 still empty, return []. Insert id 4 → slots 4 and 5 are both filled, return ["ddddd","eeeee"].

Each value is stored once and emitted once, so the pointer only ever moves forward — across all inserts it travels a total of n steps.

Time: O(1) amortized per insert (O(n) total) Space: O(n)