1656. Design an Ordered Stream

[sophryu99]

Approach

https://leetcode.com/problems/design-an-ordered-stream/description/

We need to store n incoming value (idKey, value) at the given index. And with every incoming index, we have to check

1. If the current index is less than the incoming index, then we have to return an empty list
2. Else, we have to return a sliced list from the incoming index to the first index where there is no insertion yet.

Approach

1. Initialize a list of size n with None
2. Maintain the current index with self.ptr
3. For every insert call, with idKey, value:
   • Assign the list[idKey-1] to the value # Since array is 0-index reduce 1
   • Check if the current index is less than incoming index(idKey-1) and return []
   • Else return sliced list from incoming index(idKey-1) till we do not encounter None.

class OrderedStream:

   def __init__(self, n):
        self.stream = [None]*n
        self.ptr = 0

    def insert(self, idKey, value):
        idKey -= 1
        self.stream[idKey] = value
        if self.ptr < idKey:
            return []
        else:
            while self.ptr < len(self.stream) and self.stream[self.ptr] is not None:
                self.ptr += 1
            return self.stream[idKey:self.ptr]
# Your OrderedStream object will be instantiated and called as such:
# obj = OrderedStream(n)
# param_1 = obj.insert(idKey,value)

• Time Complexity: O(1) insertion and slicing of array
• Space Complexity: O(n) for the stream array