Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/352.html

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 starti.

 

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 <= 104
  • At most 3 * 104 calls will be made to addNum and getIntervals.
  • At most 102 calls will be made to getIntervals.

 

Follow up: What if there are lots of merges and the number of disjoint intervals is small compared to the size of the data stream?

Algorithm

Use TreeMap

To get previous range last index, and next range first index. Then compare and decide if merge or not.

Integer l = tree.lowerKey(val);  // @note: Returns the greatest key strictly less than the given key

Integer h = tree.higherKey(val); // @note: Returns the least key strictly greater than the given key

Interval start/end check

Every time a new number val comes in, a new interval [val, val] is generated, and an empty interval array res is created, and a variable cur is used to store the position of the new interval.

Traverse the existing interval array intervals, for each traversed current interval interval,

  • If the end position of the interval to be added plus 1 is smaller than the start position of the current interval, indicating that the two are not connected, add the current interval to res.
  • Otherwise, when the start position of the interval to be added is greater than the end position of the current position plus 1, it means that there is no intersection between the two, and the current interval can be added to res,
    • But at this time, cur should be incremented by 1 because the position to be added to the interval is behind the current interval.
  • Otherwise, the two will overlap and need to be merged,
    • At this time, use the smaller of the two starting positions to update the starting position of the interval to be added,
    • In the same way, use the larger of the two end positions to update the end position of the interval to be added.

Finally, the interval to be added is placed at the cur position in res, and then res is assigned to intervals

Follow up: What if there are lots of merges and the number of disjoint intervals are small compared to the data stream’s size?

  • lots of merges -> add() cannot be too costy
  • the number of disjoint intervals are small -> get() can be costy

to reduce cost of add(), use O(logn) for insertion of points (no merge), and maintain order get will have to calculate the disjoint intervals on the fly (basically lazy loading, do a merge on get() trigger)

Code

  • import java.util.*;
    
    public class Data_Stream_as_Disjoint_Intervals {
    
        public static void main(String[] args) {
            Data_Stream_as_Disjoint_Intervals out = new Data_Stream_as_Disjoint_Intervals();
            SummaryRanges s = out.new SummaryRanges();
    //
    //        ["SummaryRanges","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals",
    //            "addNum","getIntervals","addNum","getIntervals"]
    //        [[],[1],[],[3],[],[7],[],[2],[],[6],[]]
    
    //        s.addNum(1);
    //        s.addNum(3);
    //        s.addNum(7);
    //        s.addNum(2);
    ////        s.intervals.stream().forEach(i -> System.out.println(Arrays.toString(i)));
    //        s.addNum(6);
    //        s.intervals.stream().forEach(i -> System.out.println(Arrays.toString(i)));
    
            s.addNum(49);
            s.addNum(97);
            s.addNum(53);
            s.addNum(5);
            s.addNum(33);
            s.addNum(65);
            s.addNum(62);
    //        s.intervals.stream().forEach(i -> System.out.println(Arrays.toString(i)));
            int[][] r = s.getIntervals();
            System.out.println(Arrays.toString(s.getIntervals()));
        }
    
        public class SummaryRanges_TreeMap {
    
            // val to interval
            TreeMap<Integer, Interval> tree;
    
            public SummaryRanges_TreeMap() {
                tree = new TreeMap<>();
            }
    
            public void addNum(int val) {
                if(tree.containsKey(val)) {
                    return;
                }
    
                Integer l = tree.lowerKey(val);  // @note: Returns the greatest key strictly less than the given key,
                Integer h = tree.higherKey(val); // @note: Returns the least key strictly greater than the given key
    
                if(l != null && h != null && tree.get(l).end + 1 == val && val + 1 == h) {
                    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());
            }
        }
    
        class SummaryRanges {
            PriorityQueue<int[]> intervals;
            List<int[]> resultTmp = new ArrayList<>();
    
            /** Initialize your data structure here. */
            public SummaryRanges() {
                intervals = new PriorityQueue<>(new Comparator<int[]>() {
                    @Override
                    public int compare(int[] o1, int[] o2) {
                        return o1[0] - o2[0];
                    }
                });
            }
    
            public void addNum(int val) {
                int[] newInterval = new int[]{val, val};
                List<int[]> result = new ArrayList<>();
                int newIntervalIndex = 0;
    
                for (int[] interval : resultTmp) {
                    if (newInterval[1] + 1 < interval[0]) {
                        result.add(newIntervalIndex, interval);
    //                    ++newIntervalIndex; // @note: right newIntervalIndex to insert
                    } else if (newInterval[0] > interval[1] + 1) {
                        result.add(newIntervalIndex, interval);
                        ++newIntervalIndex;
                    } else {
                        newInterval[0] = Math.min(newInterval[0], interval[0]);
                        newInterval[1] = Math.max(newInterval[1], interval[1]);
    //                    result.add(newIntervalIndex, newInterval);
    //                    ++resultPonter;
                    }
                }
    
                result.add(newIntervalIndex, newInterval);
                resultTmp = result;
    
                intervals.clear();
                resultTmp.forEach(intervals::offer);
    
            }
    
            public int[][] getIntervals() {
                return intervals.toArray(new int[intervals.size()][]); // @note
            }
        }
    
    /**
     * Your SummaryRanges object will be instantiated and called as such:
     * SummaryRanges obj = new SummaryRanges();
     * obj.addNum(val);
     * int[][] param_2 = obj.getIntervals();
     */
    }
    
    ############
    
    class SummaryRanges {
        private TreeMap<Integer, int[]> mp;
    
        public SummaryRanges() {
            mp = new TreeMap<>();
        }
    
        public void addNum(int val) {
            Integer l = mp.floorKey(val);
            Integer r = mp.ceilingKey(val);
            if (l != null && r != null && mp.get(l)[1] + 1 == val && mp.get(r)[0] - 1 == val) {
                mp.get(l)[1] = mp.get(r)[1];
                mp.remove(r);
            } else if (l != null && val <= mp.get(l)[1] + 1) {
                mp.get(l)[1] = Math.max(val, mp.get(l)[1]);
            } else if (r != null && val >= mp.get(r)[0] - 1) {
                mp.get(r)[0] = Math.min(val, mp.get(r)[0]);
            } else {
                mp.put(val, new int[] {val, val});
            }
        }
    
        public int[][] getIntervals() {
            int[][] res = new int[mp.size()][2];
            int i = 0;
            for (int[] range : mp.values()) {
                res[i++] = range;
            }
            return res;
        }
    }
    
    /**
     * Your SummaryRanges object will be instantiated and called as such:
     * SummaryRanges obj = new SummaryRanges();
     * obj.addNum(val);
     * int[][] param_2 = obj.getIntervals();
     */
    
  • class SummaryRanges {
    public:
        SummaryRanges() {}
        
        void addNum(int val) {
            vector<int> newInterval{val, val};
            int i = 0, overlap = 0, n = intervals.size();
            for (; i < n; ++i) {
                if (newInterval[1] + 1 < intervals[i][0]) break; 
                if (newInterval[0] <= intervals[i][1] + 1) {
                    newInterval[0] = min(newInterval[0], intervals[i][0]);
                    newInterval[1] = max(newInterval[1], intervals[i][1]);
                    ++overlap;
                }
            }
            if (overlap > 0) {
                intervals.erase(intervals.begin() + i - overlap, intervals.begin() + i);
            }
            intervals.insert(intervals.begin() + i - overlap, newInterval);
        }
        vector<vector<int>> getIntervals() {
            return intervals;
        }
    private:
        vector<vector<int>> intervals;
    };
    
  • # Definition for an interval.
    # class Interval(object):
    #     def __init__(self, s=0, e=0):
    #         self.start = s
    #         self.end = e
    
    class SummaryRanges:
    
      def __init__(self):
        self.intervals = []
    
      def insert(self, newInterval: List[int]):
        """
        :type intervals: List[Interval]
        :type newInterval: Interval
        :rtype: List[Interval]
        """
        intervals = self.intervals
        # print intervals
        if not intervals:
          intervals.append(newInterval)
          return
        s, e = newInterval[0], newInterval[1]
        left = list(filter(lambda x: x[1] < newInterval[0], intervals))
        right = list(filter(lambda x: x[0] > newInterval[1], intervals))
        # print left, right, (s, e)
        if left + right != intervals:
          s = min(intervals[len(left)][0], s)
          e = max(intervals[~len(right)][1], e)
        newIntv = [s, e]
        if left and left[-1][1] + 1 == s:
          newIntv[0] = left[-1][0]
          left = left[:-1]  # cut out last one, which is merged with newIntv
        if right and right[0][0] - 1 == e:
          newIntv[1] = right[0][1]
          right = right[1:]  # cut out first one, which is merged with newIntv
        self.intervals = left + [newIntv] + right
    
      def addNum(self, val: int) -> None:
        self.insert([val, val])
    
      def getIntervals(self) -> List[List[int]]:
    
        return self.intervals
    
    # Your SummaryRanges object will be instantiated and called as such:
    # obj = SummaryRanges()
    # obj.addNum(val)
    # param_2 = obj.getIntervals()
    
    
    ############
    
    
    class SummaryRanges: # better and easier, manual filter() via while
        def __init__(self):
            self.intervals = []
    
        def addNum(self, val: int) -> None:
            new_interval = [val, val]
            merged_intervals = []
            i = 0
    
            # before overlap part
            while i < len(self.intervals) and self.intervals[i][1] < val - 1:
                merged_intervals.append(self.intervals[i])
                i += 1
    
            # process overlap
            while i < len(self.intervals) and self.intervals[i][0] <= val + 1:
                new_interval[0] = min(new_interval[0], self.intervals[i][0])
                new_interval[1] = max(new_interval[1], self.intervals[i][1])
                i += 1
    
            merged_intervals.append(new_interval)
    
            # after overlap part
            while i < len(self.intervals):
                merged_intervals.append(self.intervals[i])
                i += 1
    
            self.intervals = merged_intervals
    
        def getIntervals(self) -> List[List[int]]:
            return self.intervals
    
    
    ############
    
    '''
    >>> mp = SortedDict()
    >>> mp.bisect_right(3)
    0
    
    
    >>> mp = SortedDict()
    >>> mp[1]=[1,1]
    >>> mp[3]=[3,3]
    >>> mp[5]=[5,5]
    >>>
    >>> mp
    SortedDict({1: [1, 1], 3: [3, 3], 5: [5, 5]})
    >>> mp.bisect_right(-10)
    0
    >>> mp.bisect_right(100)
    3
    >>> mp.bisect_right(2)
    1
    >>> mp.values()
    SortedValuesView(SortedDict({1: [1, 1], 3: [3, 3], 5: [5, 5]}))
    >>> list(mp.values())
    [[1, 1], [3, 3], [5, 5]]
    >>>
    '''
    from sortedcontainers import SortedDict
    
    class SummaryRanges:
        def __init__(self):
            self.mp = SortedDict()
    
        def addNum(self, val: int) -> None:
            n = len(self.mp)
            ridx = self.mp.bisect_right(val)
            lidx = n if ridx == 0 else (ridx - 1) # n is similar to java treemap returning null
            keys = self.mp.keys()
            values = self.mp.values()
            if (
                lidx != n
                and ridx != n
                and values[lidx][1] + 1 == val
                and values[ridx][0] - 1 == val
            ):
                self.mp[keys[lidx]][1] = self.mp[keys[ridx]][1]
                self.mp.pop(keys[ridx])
            elif lidx != n and val <= values[lidx][1] + 1: # <= because, it could be [1 -> 10], and new add is [5,5]
                self.mp[keys[lidx]][1] = max(val, self.mp[keys[lidx]][1])
            elif ridx != n and val >= values[ridx][0] - 1:
                self.mp[keys[ridx]][0] = min(val, self.mp[keys[ridx]][0])
            else:
                self.mp[val] = [val, val]
    
        def getIntervals(self) -> List[List[int]]:
            return list(self.mp.values())
    
    
    # # Your SummaryRanges object will be instantiated and called as such:
    # # obj = SummaryRanges()
    # # obj.addNum(val)
    # # param_2 = obj.getIntervals()
    
    

All Problems

All Solutions