Design an Ordered Stream

Easy

#1520Time: 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.

Patterns

Design Data Stream

Data structures

Array Hash Table

Prompt

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:

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1import java.util.ArrayList;2import java.util.HashMap;3import java.util.List;4import java.util.Map;5 6class OrderedStream {7    private Map<Integer, String> map;8    private int ptr;9 10    public OrderedStream(int n) {11        map = new HashMap<>();12        ptr = 1;13    }14 15    public List<String> insert(int idKey, String value) {16        map.put(idKey, value);17        18        List<String> chunk = new ArrayList<>();19        while (map.containsKey(ptr)) {20            chunk.add(map.get(ptr));21            ptr++;22        }23        return chunk;24    }25}

Complexity

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.

Trade-offs

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.

This is the most efficient approach for this problem. It leverages the fact that idKeys 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.

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.

Walkthrough

This approach optimizes storage and access by using an array, which is ideal given the problem's constraints where idKeys 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.

1import java.util.ArrayList;2import java.util.List;3 4class OrderedStream {5    private String[] stream;6    private int ptr;7 8    public OrderedStream(int n) {9        stream = new String[n + 1];10        ptr = 1;11    }12 13    public List<String> insert(int idKey, String value) {14        stream[idKey] = value;15        16        List<String> chunk = new ArrayList<>();17        while (ptr < stream.length && stream[ptr] != null) {18            chunk.add(stream[ptr]);19            ptr++;20        }21        return chunk;22    }23}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class 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); */

1class 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); */

1class 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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem