Java solution using TreeMap, real O(logN) per adding.


  • 85
    Q

    Use TreeMap to easily find the lower and higher keys, the key is the start of the interval.
    Merge the lower and higher intervals when necessary. The time complexity for adding is O(logN) since lowerKey(), higherKey(), put() and remove() are all O(logN). It would be O(N) if you use an ArrayList and remove an interval from it.

    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());
        }
    }

  • 1
    S

    Nice to learn the TreeMap, did not have a good chance to use it yet :)


  • 2
    S

    Question: What if the val of addNum is already in the tree as start value?
    lowerKey and higherKey find those with 'strictly' lower or higher values, so I think it will end up with creating a new interval when it is supposed to be absorbed.


  • 0
    Q

    It returns directly if the val is already in the tree. The first line of addNum method: if(tree.containsKey(val)) return;


  • 0
    S

    gotcha, thank you.


  • 0
    H
    This post is deleted!

  • 0
    H

    But there is a "tree.remove(h)", what if the val has been removed, and it will end up creating a new {val, val} interval, because the tree does not contain the key any more.


  • 0
    Y

    very brilliant solution! really really smart!


  • 0
    A

    In the second else if condition:

    else if(l != null && tree.get(l).end + 1 >= val) {
    tree.get(l).end = Math.max(tree.get(l).end, val);

    why do we need, tree.get(l).end + 1 >= val
    we could have just said if it is equal or not, tree.get(l).end + 1 can't be greater than val, because in that case it means that the given number(val) already exists in the interval and the code will return from the first line of this function.

    Please explain if there is something I missed.


  • 0
    L

    val can be fit in the Interval, which means there may have duplicates.


  • 0
    L
    This post is deleted!

  • 1
    D
    //HI thanks for you idea, and code. for ours c++, we don't have  TreeMap, but We can       use map, it's a ordered map. but map doesn't  have lowerKey, so I implement one .The code is below:c++
    private:
        map<int, Interval> orderedmap;
        int lowerKey(map<int, Interval> &orderedmap, int key){
            auto pos = orderedmap.lower_bound(key);
            if(pos == orderedmap.begin()) {
                return -1;
            } 
            return (--pos)->first;
        }
        int higherKey(map<int, Interval> &orderedmap, int key){
        auto pos = orderedmap.upper_bound(key);
        if(pos == orderedmap.end() ){
            return -1;
        } 
        return pos->first;
    }
    public:
     /** Initialize your data structure here. */
         SummaryRanges() {
        
         }
        void addNum(int val) {
            if(orderedmap.find(val) != orderedmap.end()){
                return ;
           }
           int l = lowerKey(orderedmap,val);
           int r = higherKey(orderedmap,val);
           if(l != -1 && r != -1 && orderedmap[l].end+1 == val && r == val+1){
               orderedmap[l].end = orderedmap[r].end;
               orderedmap.erase(r);
           }else if(l != -1 && orderedmap[l].end+1 >= val){
               orderedmap[l].end = max(orderedmap[l].end ,val);
           }else if(r != -1 && r == val+1){
               orderedmap[val] = Interval (val,orderedmap[r].end);
               orderedmap.erase(r);
           }else{
              Interval iv(val,val);
              orderedmap[val] = Interval (val,val);
          }
    }
    
    vector<Interval> getIntervals() {
        vector<Interval> res;
        for(auto &i : orderedmap){
            res.push_back(i.second);
        }
        return res;
    }
    

    };


  • 1
    I

    @qianzhige
    getIntervals is O(n) ! For h, you can just use get(val + 1)


  • 1
    S

    @aman13 First,you need to know, the tree only contains the lowest key of one interval. Then for example, 1,2,3,2…… the tree will contain:
    1: 1 [1,1]
    2: 1 [1,2]
    3: 1 [1,3]
    4: here, you might encounter the case that tree.get(1).end=3 which larger than newly inputted two


  • 1
    M

    @qianzhige
    very brilliant idea, but why not use TreeSet?
    Here is my AC TreeSet version, also a little slower...

    public class SummaryRanges {
        TreeSet<Interval> set;
     
        /** Initialize your data structure here. */
        public SummaryRanges() {
            set = new TreeSet(new Comparator<Interval>() {
                @Override
                public int compare(Interval a, Interval b) {
                    return a.start == b.start? a.end - b.end: a.start - b.start;
                }
            });
        }
        
        public void addNum(int val) {
            Interval interval = new Interval(val, val);
            if (set.contains(interval)) return ;
            Interval low = set.lower(interval), high = set.higher(interval);
            // check if this val is a start of some interval
            if (high != null && high.start == val) return ;
            // merge three intervals
            if (low != null && low.end + 1 == val &&
                    high != null && val + 1 == high.start) {
                low.end = high.end;
                set.remove(high);
            } 
            // merge lower and this interval
            else if (low != null && low.end + 1 >= val) {
                low.end = Math.max(low.end, val);
            }
            // merge this and higher interval
            else if (high != null && val + 1 == high.start) {
                high.start = val;
            } 
            // insert this interval
            else {
                set.add(interval);
            }
        }
    
        public List<Interval> getIntervals() {
            return new ArrayList<>(tree.values());
        }
    }

  • 0
    C

    I think using floorKey instead of lowerKey is better.
    Here is my code:

    public class SummaryRanges {
        
        TreeMap<Integer, Interval> treeMap;
    
        /** Initialize your data structure here. */
        public SummaryRanges() {
            treeMap=new TreeMap<>();
        }
        
        public void addNum(int val) {
            Integer floor=treeMap.floorKey(val);
            if (floor==null || treeMap.get(floor).end<val-1) {
                Interval interval=treeMap.remove(val+1);
                treeMap.put(val, new Interval(val, interval==null?val:interval.end));
            }
            else {
                Interval interval=treeMap.get(floor);
                if (interval.end>=val) return;
                Interval next=treeMap.remove(val+1);
                interval.end=next==null?val:next.end;
                treeMap.put(floor, interval);
            }
        }
        
        public List<Interval> getIntervals() {
            return new ArrayList<>(treeMap.values());
        }
    }
    

  • 0

    @iaming
    Yes, get is O(n), but the intention here was to optimize the add to O(log(n)), since the get queries might be relatively small compared to the streaming add calls. A minior optimization that can be done on get is to create a new list only if the treeMap was updated since last getCall.

    If you want the get to be optimized to O(1), you can create the list during add call, which again makes it O(n).


  • 3

    Thanks for sharing! I'm wondering could we solve it like what we did for 128 Longest Consecutive Sequence.
    We don't try to find closest lower or higher entry, conversely only find val+/-1 and union consecutive range.
    In this way, the time complexity of add() would be O(1) and getIntervals() would be O(NlogN), am I correct?

    ps: I assume the N in O(NlogN) should be very small since I only keep two ends of interval.

        // Key - left or right boundary value of range, Value - size of range
        private Map<Integer, Integer> ranges = new HashMap<>();
        
        // Since middle val is removed, an extra set is required to de-duplicate
        private Set<Integer> dup = new HashSet<>();
        
        public void addNum(int val) {
            if (!dup.add(val)) return;
            int left = ranges.containsKey(val - 1) ? ranges.remove(val - 1) : 0;
            int right = ranges.containsKey(val + 1) ? ranges.remove(val + 1) : 0;
            int sum = left + right + 1;
            
            if (left > 0) ranges.put(val - left, sum);
            if (right > 0) ranges.put(val + right, sum);
            if (left == 0 || right == 0) ranges.put(val, sum); // remove middle val to speed up getInt()
        }
        
        public List<Interval> getIntervals() {
            List<Interval> ret = new ArrayList<>();
            List<Integer> keys = new ArrayList<>(ranges.keySet());
            Collections.sort(keys);
            
            int last = Integer.MIN_VALUE;
            for (int left : keys) {
                int size = ranges.get(left);
                if (last < left) {
                    ret.add(new Interval(left, left + size - 1));
                    last = left + size - 1;
                }
            }
            return ret;
        }
    

  • 0
    J

    @hyj143 tree.lowerKey will find the possible interval anyway


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.