Design An Ordered Stream - Leetcode Solution

Problem Statement:

You are given n length of ordered list of disjoint intervals where each interval is represented by a pair of integers. The ith interval starts from the integer ai and ends at the integer bi. You have to design a stream as follows:

• You have to sequentially output the integers of each interval in a sorted order.

• After the output of last integer of each interval, you have to move to the next interval.

• If the current interval has no more integers to output, then continue on next interval.

• If the next interval has no integers to output then return empty string.

Write a class OrderedStream to implement above stream.

Solution:

Approach:

We can solve this problem using a simple approach. Here we will use an array of size n to store the integers of the intervals. We will initialize all elements of the array as Null. Then we will iterate through the given list of intervals and update the corresponding elements in the array with the integers of the intervals.

For the output of the Ordered Stream, we will keep track of the last integer that was output for each interval. We will maintain a pointer that points to the lowest index of the elements of the array that is not yet output. Then the output of the stream will be a sequence of the integers that starts from the index pointed by the pointer.

Implementation:

Here is the implementation of the OrderedStream class in Python:

class OrderedStream: def init(self, n: int): self.stream = [None] * n self.pointer = 0

def insert(self, id: int, value: str) -> List[str]:
    self.stream[id-1] = value

    if id - 1 == self.pointer:
        output = []
        while self.pointer < len(self.stream) and self.stream[self.pointer] is not None:
            output.append(self.stream[self.pointer])
            self.pointer += 1
        return output
    else:
        return []

In the constructor of the OrderedStream class, we initialize an array with n elements as None and set the pointer to 0.

In the insert function, we update the elements of the array with the given value for the corresponding id. Then, if the id equals to the current value of the pointer, it means that we can output some integers. So we start outputting the integers from the index pointed by the pointer until it finds a None element in the array. After the output of the integers, we increment the pointer.

If the id is not equal to the pointer, it means that we cannot output any integers at this moment. So we return the empty list.

Time Complexity:

For each insert operation, we output at most n integers from the array. So, the time complexity of the insert function is O(n). The time complexity of the OrderedStream constructor is O(1). Overall, the time complexity of the OrderedStream class is O(n).

Space Complexity:

We are using an array of size n to store the integers of the intervals. So, the space complexity of the OrderedStream class is O(n).

1