Skip to main content

Data Stream as Disjoint Intervals

Problem Description​

Given a data stream input of non-negative integers a1, a2, ..., an, summarize the numbers seen so far as a list of disjoint intervals.

Implement the SummaryRanges class:

  • SummaryRanges() Initializes the object with an empty stream.
  • void addNum(int value) Adds the integer value to the stream.
  • int[][] getIntervals() Returns a summary of the integers in the stream currently as a list of disjoint intervals [starti, endi]. The answer should be sorted by starting.

Examples​

Example 1:

Input
["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
Output
[null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]

Explanation
SummaryRanges summaryRanges = new SummaryRanges();
summaryRanges.addNum(1);      // arr = [1]
summaryRanges.getIntervals(); // return [[1, 1]]
summaryRanges.addNum(3);      // arr = [1, 3]
summaryRanges.getIntervals(); // return [[1, 1], [3, 3]]
summaryRanges.addNum(7);      // arr = [1, 3, 7]
summaryRanges.getIntervals(); // return [[1, 1], [3, 3], [7, 7]]
summaryRanges.addNum(2);      // arr = [1, 2, 3, 7]
summaryRanges.getIntervals(); // return [[1, 3], [7, 7]]
summaryRanges.addNum(6);      // arr = [1, 2, 3, 6, 7]
summaryRanges.getIntervals(); // return [[1, 3], [6, 7]]

Constraints​

  • 0 <= value <= 10^4
  • At most 3 * 10^4 calls will be made to addNum and getIntervals.
  • At most 10^2 calls will be made to getIntervals

Solution for Data Stream as Disjoint Intervals​

Intuition​

The intuition behind this implementation is to use a data structure that allows for easy ordering and searching, as well as efficient insertion and deletion of intervals. In this case, a std::map is used to store the disjoint intervals. The key is the start value of the interval and the value is the end value. By using a data structure like map which implements a balanced binary search tree, we can easily find the correct position of new value and merge it with the existing intervals if necessary, which will help us to maintain the disjoint property of the intervals.

Approach​

The approach used in this implementation is to use a data structure, in this case a std::map, to store the disjoint intervals. Each interval is stored as a key-value pair in the map, where the key is the start value of the interval and the value is the end value.

When a new value is added to the stream, the lower_bound() function is used to find the correct position of the new value in the map, and then the implementation checks if the new value can be added to an existing interval or if it needs to create a new one. It also checks if the new value can merge with the interval before or after it, and merges them if necessary.

The getIntervals() function iterates through the map and stores the intervals in a vector of vectors, which is returned.

By using the map's properties of ordering and searching, the implementation can easily find the correct position of the new value in the stream and merge it with the existing intervals if necessary.

This approach is efficient in terms of space and time complexity because it allows for easy ordering and searching, as well as efficient insertion and deletion of intervals, which is important for maintaining the disjoint property of the intervals.

Code in Different Languages​

Written by @mahek0620
 public class SummaryRanges {
 TreeMap<Integer, Interval> tree;

 public SummaryRanges() {
     tree = new TreeMap<>();
 }

 public void addNum(int val) {
     if(tree.containsKey(val)) return;
     Integer l = tree.lowerKey(val);
     Integer h = tree.higherKey(val);
     if(l != null && h != null && tree.get(l).end + 1 == val && h == val + 1) {
         tree.get(l).end = tree.get(h).end;
         tree.remove(h);
     } else if(l != null && tree.get(l).end + 1 >= val) {
         tree.get(l).end = Math.max(tree.get(l).end, val);
     } else if(h != null && h == val + 1) {
         tree.put(val, new Interval(val, tree.get(h).end));
         tree.remove(h);
     } else {
         tree.put(val, new Interval(val, val));
     }
 }

 public List<Interval> getIntervals() {
     return new ArrayList<>(tree.values());
 }
}

References​