Data Stream As Disjoint Intervals

Moderate
0/80
Average time to solve is 30m
34 upvotes
Asked in company
eBay

Problem statement

You are given a stream of 'n' non-negative integers as the input, and you have to group the stream of integers in the form of disjoint intervals.


Your task is to Implement the ‘DisjointIntervals’ class having the two functions:


1) The first function is ‘addInteger(int val)’, which takes an integer ‘val’ as an argument and adds it to the stream.

2) The second function is ‘getDisjointIntervals()’, which returns a summary of the integers in the stream currently as a list of disjoint intervals.


Example:

Input: 'n' = 5 , stream =  [
                  [1, 1],
                  [1, 3],
                  [2],
                  [1, 2],
                  [2],
                ]

Output: [
          [ [1, 1],  [3, 3] ],
          [ [1,3] ] 
        ]

Explanation: First of all, 1 is added to the stream, and the disjoint interval will be {1, 1}. When 3 will be added to the stream, then the disjoint intervals will be {1, 1}, {3, 3}. But when 2 is added to the stream then the disjoint interval will be {1, 3} as 2 lies between these two sets of disjoint intervals, and both the intervals {1, 1} and {3, 3} merge.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first input line contains an integer ‘n’, representing the total number of queries.

Then the next ‘n’ lines contain ‘n’ queries. A query can be of two types:
1 val → adds the integer ‘val’ to the stream.
2 → returns a list of disjoint intervals.
Output format: 
For each test case, print all the disjoint intervals for each query of type 2, and output the answer to the query in a single line.

Each query must be answered in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given functions.
Sample Input 1:
 6
 1 3
 2
 1 6
 2
 1 5
 2
Sample Output 1:
 3 3
 3 3 6 6
 3 3 5 6
Explanation for sample Input 1:
First 3 is added to the stream, and the disjoint interval will be {3, 3}. When 6 will be added to the stream, then the disjoint intervals will be {3, 3},{6, 6}. But when 5 is added to the stream, then the disjoint interval will be {3, 3}, {5, 6} as 5 merges with the interval {6, 6} because the difference between interval {5, 5} and {6, 6} is less than 2.
Sample Input 2:
6
1 1
2
1 4
2
1 3
2
Sample Output 2:
1 1
1 1 4 4
1 1 3 4
Explanation for sample Input 1:
First, 1 is added to the stream, and the disjoint interval will be {1, 1}. When 4 will be added to the stream, then the disjoint intervals will be {1, 1},{4, 4}. But when 3 is added to the stream, then the disjoint interval will be {1, 1}, {3, 4} as 3 merges with the interval {4, 4}.
Constraints:
1 <= 'n' <=  10 ^ 5
0 <= 'val' <= 10 ^ 4

Time Limit: 1 sec.
Hint

Can you solve this problem by using linear search?

Approaches (2)
Brute Force Approach

In this approach, for any new number ‘Val’, we will find the position of the first interval whose starting value is greater than the added ‘Val’ to the stream using linear search.

  • It has three cases:
    • It will be inserted at the beginning of the list or it gets combined with the first interval of the list.
    • It will be inserted at the end of the list or combine with the last interval in the list.
    • It will be inserted between two intervals and then we will try to merge it with the previous and next interval to it.

Algorithm:

 

  • Create a 2D array ‘Intervals’ to store the intervals.
  • Whenever the function ‘addInteger’ is called with an integer ‘Val’ we will first check if the array is empty initially then insert {Val, Val} into the list.
  • Create a variable ‘optimalIndex’ initialized to the size of the array ‘Intervals’. Now do a linear search on the array and find the first position where the start of the interval is greater than the ‘Val’ and save this position in the ‘optimalIndex’ variable. Also while doing a linear search if we find any interval which already contains the ‘Val’ we will return from the function from here only.
  • Now if the value of ‘optimalIndex’ = size of the array ‘Interval’ then:
    • If it can be merged with the last interval i.e Val <= (End of last interval + 1) then make ‘end of the last interval’ = ‘Val’.
    • Otherwise insert {Val, Val} at the last of the array.
    • And return from the function from here only.
  • Now if the value of ‘optimalIndex’ = 0 then:
    • If it can be merged with the first interval i.e (Val + 1) >= Start of the first interval then make ‘start of the first interval’ = ‘Val’.
    • Otherwise insert {Val, Val} at the beginning of the array.
    • And return from the function from here only.
  • Now insert {Val, Val} at the ‘optimalIndex’ value in the array.
  • Now check it can be merged with the interval at (optimalIndex + 1)th position:
    • If ‘start of the interval at (optimalIndex+1)th position’ - ‘end of the inserted interval’ = 1 then update ‘end of the inserted interval’ = ‘end of the interval at (optimalIndex+1)th position’ and erase the interval at the (optimalIndex+1)th position.
  • Now check it can be merged with the interval at (optimalIndex - 1)th position:
    • If ‘start of the interval at the optimalIndex position’ - ‘end of the (optimalIndex-1)th interval’ = 1 then update ‘end of the (optimalIndex-1)th interval’ = ‘end of the interval at optimalIndex position’ and erase the interval at the optimalIndex position.
  • And whenever ‘getDisjointIntervals’ functions is called simply return the array ‘Intervals’.
Time Complexity

O(N ^ 2), where ‘N’ is the total number of queries.

 

Since there are ‘N’ queries and for each of these queries, we will either call the ‘addInteger’ function, which we take O(N) time for performing a linear search for each of the integer added to the stream giving time complexity of O(N) per query, or the ‘getDisjointIntervals’ functions which will take O(N) time to get all the required intervals. So overall time complexity will be O(N ^ 2). 

Space Complexity

O(1).

 

We are using only Constant extra space. So overall space complexity will be O(1). 

Code Solution
(100% EXP penalty)
Data Stream As Disjoint Intervals
Full screen
Console