# Design an Ordered Stream
**Difficulty:** EASY
[External](https://leetcode.com/problems/design-an-ordered-stream)
Canonical: https://scaleengineer.com/dsa/problems/design-an-ordered-stream
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design), [Data Stream](https://scaleengineer.com/dsa/patterns/data-stream)
**Data structures:** Array, Hash Table
---
## Problem
There is a stream of `n` `(idKey, value)` pairs arriving in an **arbitrary** order, where `idKey` is an integer between `1` and `n` and `value` is a string. No two pairs have the same `id`.

Design a stream that returns the values in **increasing order of their IDs** by returning a **chunk** (list) of values after each insertion. The concatenation of all the **chunks** should result in a list of the sorted values.

Implement the `OrderedStream` class:

* `OrderedStream(int n)` Constructs the stream to take `n` values.
* `String[] insert(int idKey, String value)` Inserts the pair `(idKey, value)` into the stream, then returns the **largest possible chunk** of currently inserted values that appear next in the order.

**Example:**

**![](https://assets.glich.co/dsa/design-an-ordered-stream/image0.gif)**

**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**
// Note that the values ordered by ID is ["aaaaa", "bbbbb", "ccccc", "ddddd", "eeeee"].
OrderedStream os = new OrderedStream(5);
os.insert(3, "ccccc"); // Inserts (3, "ccccc"), returns [].
os.insert(1, "aaaaa"); // Inserts (1, "aaaaa"), returns ["aaaaa"].
os.insert(2, "bbbbb"); // Inserts (2, "bbbbb"), returns ["bbbbb", "ccccc"].
os.insert(5, "eeeee"); // Inserts (5, "eeeee"), returns [].
os.insert(4, "ddddd"); // Inserts (4, "ddddd"), returns ["ddddd", "eeeee"].
// Concatentating all the chunks returned:
// [] + ["aaaaa"] + ["bbbbb", "ccccc"] + [] + ["ddddd", "eeeee"] = ["aaaaa", "bbbbb", "ccccc", "ddddd", "eeeee"]
// The resulting order is the same as the order above.

**Constraints:**

* `1 <= n <= 1000`
* `1 <= id <= n`
* `value.length == 5`
* `value` consists only of lowercase letters.
* Each call to `insert` will have a unique `id.`
* Exactly `n` calls will be made to `insert`.

# Approaches
## Using a HashMap and a Pointer
This approach uses a HashMap to store the incoming `(idKey, value)` pairs in an unordered fashion. A separate pointer, initialized to 1, keeps track of the next expected ID. When a new pair is inserted, it's added to the map. Then, we check if the map contains the value for the current pointer. If it does, we start collecting a chunk of contiguous values by incrementing the pointer until we find a missing ID. This method is straightforward but has slightly more overhead than using an array.
**Time:** The constructor is `O(1)`. For `insert`, the `put` operation is `O(1)` on average. The `while` loop runs `k` times for a chunk of size `k`. The total work for the `while` loop across all `n` insertions is `O(n)`, making the amortized time complexity for `insert` `O(1)`. The worst-case time for a single call is `O(n)`. · **Space:** `O(n)` to store up to `n` key-value pairs in the HashMap.
**Pros:** Simple to understand and implement.; Flexible for non-sequential or sparse keys, although not required by this specific problem.
**Cons:** Higher memory overhead compared to an array due to the HashMap's internal structure.; Hash map operations have an average time complexity of `O(1)`, which is not a worst-case guarantee like array access.
### Explanation
This approach maintains the state of the stream using a `HashMap` and an integer pointer.

*   **Data Structures:**
    *   `map`: A `HashMap<Integer, String>` to store the `(idKey, value)` pairs that arrive. This allows for flexible, unordered insertion.
    *   `ptr`: An integer, initialized to `1`, that keeps track of the next ID we are expecting in the ordered sequence.

*   **Constructor `OrderedStream(n)`:**
    *   Initializes an empty `HashMap`.
    *   Sets the `ptr` to `1`.

*   **Method `insert(idKey, value)`:**
    *   The incoming `(idKey, value)` pair is inserted into the `map`.
    *   A new `ArrayList` `chunk` is created to hold the output.
    *   A `while` loop checks if the `map` contains the key that `ptr` is currently pointing to.
    *   If it does, the corresponding value is added to the `chunk`, and `ptr` is incremented to look for the next consecutive ID.
    *   This process repeats until an ID is not found in the map, signifying a break in the contiguous sequence.
    *   The method then returns the `chunk`. If the inserted `idKey` was not the one expected by `ptr`, the loop doesn't execute, and an empty list is returned.

```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class OrderedStream {
    private Map<Integer, String> map;
    private int ptr;

    public OrderedStream(int n) {
        map = new HashMap<>();
        ptr = 1;
    }

    public List<String> insert(int idKey, String value) {
        map.put(idKey, value);
        
        List<String> chunk = new ArrayList<>();
        while (map.containsKey(ptr)) {
            chunk.add(map.get(ptr));
            ptr++;
        }
        return chunk;
    }
}
```
### Algorithm
- In the constructor, initialize a `HashMap<Integer, String>` and an integer `ptr` to `1`.
- In the `insert(idKey, value)` method:
  1. Store the `(idKey, value)` pair in the HashMap.
  2. Create an empty list `chunk` to store the result.
  3. Start a `while` loop that continues as long as the HashMap contains the key `ptr`.
  4. Inside the loop, add the value for `ptr` to the `chunk` and increment `ptr`.
  5. After the loop, return the `chunk`.

## Using an Array and a Pointer
This is the most efficient approach for this problem. It leverages the fact that `idKey`s are integers in a dense range from 1 to `n`. We can use an array of size `n+1` as a direct-access table to store the values. A pointer, initialized to 1, tracks the next expected ID. This avoids the overhead of a HashMap and provides guaranteed `O(1)` access time for storage.
**Time:** The constructor takes `O(n)` time to initialize the array. The `insert` operation involves an `O(1)` array write. The `while` loop runs `k` times for a chunk of size `k`. The total work done by the `while` loop across all `n` insertions is `O(n)`. Thus, the amortized time complexity for each `insert` call is `O(1)`. The worst-case time for a single call is `O(n)`. · **Space:** `O(n)` to store the `n` values in the array.
**Pros:** Optimal time and space efficiency for this problem's constraints.; Guaranteed `O(1)` time for storing/accessing values.; Better memory locality compared to a HashMap.
**Cons:** The constructor has a time complexity of `O(n)`.; Less flexible; only works well because the keys are a dense range of integers.
### Explanation
This approach optimizes storage and access by using an array, which is ideal given the problem's constraints where `idKey`s are a dense set of integers from `1` to `n`.

*   **Data Structures:**
    *   `stream`: A `String` array of size `n + 1`. We use `n + 1` to allow for 1-based indexing (`1` to `n`), making the code cleaner as we can map `idKey` directly to an array index.
    *   `ptr`: An integer, initialized to `1`, that points to the next expected ID in the sequence.

*   **Constructor `OrderedStream(n)`:**
    *   Initializes the `stream` array with size `n + 1`. All elements are `null` by default.
    *   Sets the `ptr` to `1`.

*   **Method `insert(idKey, value)`:**
    *   The `value` is stored at `stream[idKey]`. This is a constant time operation.
    *   A new `ArrayList` `chunk` is created.
    *   A `while` loop starts from the current `ptr`. It continues as long as `ptr` is within the array bounds and the element `stream[ptr]` is not `null` (meaning the value for that ID has been inserted).
    *   Inside the loop, `stream[ptr]` is added to the `chunk`, and `ptr` is incremented.
    *   When the loop finds a `null` slot, it means the contiguous sequence is broken, and the loop terminates.
    *   The collected `chunk` is returned.

```java
import java.util.ArrayList;
import java.util.List;

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

    public OrderedStream(int n) {
        stream = new String[n + 1];
        ptr = 1;
    }

    public List<String> insert(int idKey, String value) {
        stream[idKey] = value;
        
        List<String> chunk = new ArrayList<>();
        while (ptr < stream.length && stream[ptr] != null) {
            chunk.add(stream[ptr]);
            ptr++;
        }
        return chunk;
    }
}
```
### Algorithm
- In the constructor, initialize a `String` array `stream` of size `n + 1` and an integer `ptr` to `1`.
- In the `insert(idKey, value)` method:
  1. Place the `value` at index `idKey` in the `stream` array.
  2. Create an empty list `chunk`.
  3. Start a `while` loop that continues as long as `ptr` is within array bounds and `stream[ptr]` is not `null`.
  4. Inside the loop, add `stream[ptr]` to the `chunk` and increment `ptr`.
  5. After the loop, return the `chunk`.

# Solutions
### Java

```java
class OrderedStream { private String [] data ; private int ptr ; public OrderedStream ( int n ) { data = new String [ n ]; ptr = 0 ; } public List < String > insert ( int idKey , String value ) { data [ idKey - 1 ] = value ; List < String > ans = new ArrayList <>(); while ( ptr < data . length && data [ ptr ] != null ) { ans . add ( data [ ptr ++]); } return ans ; } } /** * Your OrderedStream object will be instantiated and called as such: * OrderedStream obj = new OrderedStream(n); * List<String> param_1 = obj.insert(idKey,value); */
```

### CPP

```cpp
class OrderedStream { public: vector < string > data ; int ptr = 0 ; OrderedStream ( int n ) { data . resize ( n , "" ); } vector < string > insert ( int idKey , string value ) { data [ idKey - 1 ] = value ; vector < string > ans ; while ( ptr < data . size () && data [ ptr ] != "" ) ans . push_back ( data [ ptr ++ ]); return ans ; } }; /** * Your OrderedStream object will be instantiated and called as such: * OrderedStream* obj = new OrderedStream(n); * vector<string> param_1 = obj->insert(idKey,value); */
```

### Python

```python
class OrderedStream : def __init__ ( self , n : int ): self . data = [ None ] * n self . ptr = 0 def insert ( self , idKey : int , value : str ) -> List [ str ]: self . data [ idKey - 1 ] = value ans = [] while self . ptr < len ( self . data ) and self . data [ self . ptr ]: ans . append ( self . data [ self . ptr ]) self . ptr += 1 return ans # Your OrderedStream object will be instantiated and called as such: # obj = OrderedStream(n) # param_1 = obj.insert(idKey,value)
```