1656. Design an Ordered Stream

Problem Description

The problem deals with a stream of n unique (idKey, value) pairs where idKey is an integer ranging from 1 to n, and value is a string. The objective is to design a system that can accept these pairs in any arbitrary order and return chunks of values sorted by their idKey. Additionally, as we process and insert new (idKey, value) pairs, we should return the largest chunk of consecutive idKey values, in increasing order, that have been inserted up to that point.

The problem requires us to implement a class that can track the order of incoming data pairs and return the sorted output in parts (chunks), without waiting for all data to be inserted.

Intuition

To solve this, we need a way to keep track of the inserted values and know which value corresponds to which idKey. As these values can be inserted in any order, a simple list can store the values at their respective (idKey - 1) index (since array indices are 0-based, but our idKeys are 1-based).

The main challenge is figuring out whether we have a contiguous sequence of idKey values from the current pointer position. To handle this, we maintain a pointer that starts at 0 and only moves forward when we add a new value that fills the gap.

When we insert a value, we'll place it at the idKey - 1 index of our data array. Then, we check from the current pointer's position forward to see if we have consecutive values without any gaps. We keep moving the pointer and collecting values until we hit an idKey that hasn't been filled yet. This collection of values is the chunk we want to return.

The idea is similar to having a lock with rotating disks, each disk representing an idKey with its respective value, and the pointer aligning the next open slot. When all 'disks' up to a particular point are aligned (values are filled), we can return the idKeys and their values in order up to that point.

Learn more about Data Stream patterns.

Solution Approach

The solution uses a simple array-based approach to store the incoming values. This approach efficiently solves the problem by exploiting the idKey to index mapping and a pointer to keep track of the next idKey that should be output.

The OrderedStream class initializes an array (or list in Python) to hold n values, which are initially set to None to indicate they have not been filled yet. The ptr variable is used as a pointer to the current position we expect the next idKey to fill.

The core of the solution is in the insert method, which has the following steps:

1. Insert Value: Store the value at the idKey - 1 index of the data array, since idKey is 1-based and the array index is 0-based.

2. Get Chunk: Once the value is inserted, we need to collect a chunk of consecutive values, starting from where the ptr points. So we initiate an empty list ans to store the chunk of values.

3. Advance Pointer: Starting from ptr, iterate through the data array until you find an idKey that has not been filled (contains None). During this iteration, add the non-None values to the ans list and increment ptr after each non-None value is found. This step is crucial since it moves the ptr past the values that have been used to form the current chunk.

4. Return Chunk: Once a None value is encountered, or the end of the list is reached, stop collecting values and return the ans list. This list represents the largest possible chunk of values that can be formed in consecutive idKey order at this point in the stream.

The algorithm's efficiency comes from its direct use of the idKey as an array index and its linear scan from the ptr position to identify the contiguous sequence. No sorting is necessary because the idKey already indicates where the value belongs, and the process only involves inserting and scanning forward.

The overall time complexity for each insert operation is O(n) in the worst case, where n is the number of values the stream is set to contain.

Here is the crucial part of the implementation:

1def insert(self, idKey: int, value: str) -> List[str]:
2    self.data[idKey - 1] = value
3    ans = []
4    while self.ptr < len(self.data) and self.data[self.ptr]:
5        ans.append(self.data[self.ptr])
6        self.ptr += 1
7    return ans

In this snippet, the insert method implements the solution approach, ensuring that a chunk of consecutive ordered values is returned each time a new (idKey, value) pair is inserted into the stream.

Example Walkthrough

Let's say we're given a stream with n = 5 unique (idKey, value) pairs, and they are inserted in the following order: (3, "C"), (1, "A"), (5, "E"), (4, "D"), and (2, "B"). We will use the solution approach to handle the stream of data and illustrate how the chunks are returned after each insert.

When we first initialize our OrderedStream for n = 5, our data array and ptr look like this:

1data: [None, None, None, None, None]
2ptr: 0

First Insertion: A pair (3, "C") is inserted.

1. We put value "C" at index 3 - 1 in our data array.
2. The ptr is still at 0, and since data[0] is None, we can't form a chunk.
3. No chunk is returned.
4. Data and ptr are now:

1data: [None, None, "C", None, None]
2ptr: 0

Second Insertion: A pair (1, "A") is inserted.

1. We put value "A" at index 1 - 1.
2. Now, ptr points to data [0] which is no longer None, and it's the start of a new chunk.
3. We collect values until we hit a None value, resulting in a chunk ["A"].
4. The ptr is incremented by 1.
5. Data and ptr are now:

1data: ["A", None, "C", None, None]
2ptr: 1

Third Insertion: A pair (5, "E") is inserted.

1. We put value "E" at index 5 - 1.
2. The ptr points to data[1] which is still None, so no new chunk can be formed.
3. No chunk is returned.
4. Data and ptr are unchanged:

1data: ["A", None, "C", None, "E"]
2ptr: 1

Fourth Insertion: A pair (4, "D") is inserted.

1. We put value "D" at index 4 - 1.
2. Since ptr is still at 1 and data[1] is None, no consecutive chunk is formed.
3. No chunk is returned.
4. Data and ptr are unchanged:

1data: ["A", None, "C", "D", "E"]
2ptr: 1

Fifth Insertion: A pair (2, "B") is inserted.

1. We put value "B" at index 2 - 1.
2. Now ptr at index 1 finds a non-None value, and we can start forming a new chunk.
3. We collect values starting from ptr - ["B", "C", "D"] - and keep incrementing ptr for each non-None value.
4. The chunk forming stops as data[4] (for idKey 5) is None.
5. We return the chunk ["B", "C", "D"].
6. The ptr has moved to index 4.

1data: ["A", "B", "C", "D", None]
2ptr: 4

As you can see, each insertion leads to the result of the insert function, which is the largest chunk of consecutive values that can be formed at that time. After all pairs have been inserted, we've managed to return all the chunks using the solution approach, and the data array contains all values sorted by their idKeys.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the __init__ method is O(n) as it initializes a list of size n with None.

The time complexity of the insert method is O(n) in the worst case. This worst-case scenario occurs when all the previous elements (from the current ptr to the idKey - 1) are filled in, and the method appends all of them to the ans list in a single call to insert. However, on average, assuming the inserts are distributed evenly, the complexity for each call would be O(1) as each inserted value would only cause a single write and at most one read (when the ptr immediately moves forward). The complexity of moving the pointer forward is O(1) for each step since it only involves checking a value and incrementing an index.

Space Complexity

The space complexity of the OrderedStream object is O(n). This space is required to store the stream of data of size n. No additional significant space is used during the insert operations; the ans list temporarily holds a number of elements equal to the number of elements from ptr to the current idKey, but since it does not grow larger than n, it does not affect the overall space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.