We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Design an Ordered Stream

Difficulty: Easy

Problem Description

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.

Key Insights

  • The stream allows for unordered insertion of (idKey, value) pairs.
  • We need to return the values in order of their idKeys when they are inserted.
  • The output after each insertion should be the largest contiguous chunk of inserted values in order.
  • We can use an array to keep track of inserted values based on their idKey.

Space and Time Complexity

Time Complexity: O(1) for each insert operation on average, as it involves updating an array and checking for the next contiguous chunk. Space Complexity: O(n) for storing the inserted values.

Solution

To solve this problem, we can use an array of size n to store the values corresponding to their idKeys. The insert method will place the value in the correct index of the array based on the provided idKey. After insertion, we will check for contiguous values starting from the last successfully inserted idKey, collecting them into a chunk to return. This approach ensures that we can efficiently track and return the ordered chunks of values.

Code Solutions

class OrderedStream:
    def __init__(self, n: int):
        self.stream = [None] * (n + 1)  # Initialize an array of size n + 1
        self.ptr = 1  # Pointer to track the next expected idKey

    def insert(self, idKey: int, value: str):
        self.stream[idKey] = value  # Place the value at the corresponding index
        result = []
        
        # Collect values starting from the current pointer
        while self.ptr < len(self.stream) and self.stream[self.ptr] is not None:
            result.append(self.stream[self.ptr])
            self.ptr += 1
            
        return result
← Back to All Questions