Problem statement

n pairs (idKey, value) arrive in some arbitrary order, where the idKeys are exactly 1 to n, each once. The stream must hand the values back in idKey order, as soon as it can.

Write the class OrderedStream:

• OrderedStream(int n) prepares a stream for n values.
• String[] insert(int idKey, String value) stores the pair and returns the largest possible chunk of values that can now be released: starting from the smallest idKey not yet released, every consecutive stored value, in idKey order. If the next idKey to release has not arrived, it returns an empty list.

Concatenating all the returned chunks gives the values sorted by idKey.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.

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: Id 3 arrives first but 1 is still missing, so nothing is released. Id 1 releases just itself (2 is missing); id 2 releases 2 and the waiting 3. Id 5 waits for 4, and 4 releases both.

Example 2

Input: ["OrderedStream","insert","insert","insert"]
[[3],[2,"lemon"],[3,"mango"],[1,"apple"]]
Output: [null,[],[],["apple","lemon","mango"]]
Explanation: Everything waits for id 1, which then releases all three values at once.

Constraints

• 1 <= n <= 1000
• 1 <= idKey <= n
• value.length == 5
• value consists only of lowercase letters
• Each call to insert has a different idKey
• Exactly n calls are made to insert

Hints for Design an Ordered Stream

1. Hint 1

   Store each value at index idKey of an array of size n + 1 as it arrives.

2. Hint 2

   Keep a pointer to the smallest idKey that has not been released yet.

3. Hint 3

   After storing, walk the pointer forward while the slot under it is filled, collecting those values — that walk is the chunk.

How to solve Design an Ordered Stream

An array of slots plus a release pointer. Each insert fills one slot, then the pointer advances over every consecutive filled slot, and the values it passes are exactly what can be released now.

Approach

1. Create slots of size n + 2 (all empty) and ptr = 1.
2. insert(idKey, value): set slots[idKey] = value.
3. While slots[ptr] is filled, append it to the chunk and increment ptr.
4. Return the chunk (possibly empty).

Why it works

Everything below ptr has been released and slots[ptr] is the first id not yet released. A value can only be released once every smaller id has been, so the chunk is precisely the run of filled slots starting at ptr — no more (the run ends at a missing id), no less (every filled slot in the run qualifies).

Complexity

• Time — O(n) over all n inserts — the pointer only moves forward
• Space — O(n)

Pitfalls

• Releasing only the value just inserted misses values that were waiting behind it.
• Size the array so slots[n + 1] exists (or check ptr <= n) — the pointer walks one past the last id.

Reference solution

Python

from typing import List

class OrderedStream:

    def __init__(self, n: int):
        self.slots = [None] * (n + 2)
        self.ptr = 1

    def insert(self, idKey: int, value: str) -> List[str]:
        self.slots[idKey] = value
        out = []
        while self.slots[self.ptr] is not None:
            out.append(self.slots[self.ptr])
            self.ptr += 1
        return out

Java

class OrderedStream {
    private String[] slots;
    private int ptr = 1;

    public OrderedStream(int n) {
        slots = new String[n + 2];
    }

    public String[] insert(int idKey, String value) {
        slots[idKey] = value;
        int from = ptr;
        while (slots[ptr] != null) ptr++;
        return Arrays.copyOfRange(slots, from, ptr);
    }
}

C++

class OrderedStream {
    vector<string> slots;
    vector<bool> filled;
    int ptr = 1;
public:
    OrderedStream(int n) : slots(n + 2), filled(n + 2, false) {}

    vector<string> insert(int idKey, string value) {
        slots[idKey] = value;
        filled[idKey] = true;
        vector<string> out;
        while (filled[ptr]) out.push_back(slots[ptr++]);
        return out;
    }
};

JavaScript

var OrderedStream = function(n) {
    this.slots = new Array(n + 2).fill(null);
    this.ptr = 1;
};

OrderedStream.prototype.insert = function(idKey, value) {
    this.slots[idKey] = value;
    var out = [];
    while (this.slots[this.ptr] !== null) out.push(this.slots[this.ptr++]);
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy
• Convert Sorted Array to Binary Search Tree Easy