Not very concise but easy to read Java solution O(logN) per input


  • 2
    S

    Java is not my primary languages. However, this question is not easy to implement in C++. I tried the pb_ds/tree, it solves the problem, but for sure not as convenient as Java TreeMap.

    public class SummaryRanges {
    
        /** Initialize your data structure here. */
        private TreeMap<Integer, Integer> tree;
        
        public SummaryRanges() {
            tree = new TreeMap<>();
        }
        
        public void addNum(int val) {
            // Value existed as key
            if (tree.get(val) != null)
                return;
    
            // Value existed inside intervals
            Map.Entry<Integer, Integer> low = tree.lowerEntry(val);
            if (low != null && low.getValue() >= val)
                return;
    
            // Value can merge to end
            if (low != null && low.getValue() + 1 == val) {
                if (tree.get(val + 1) != null) {
                    int start = low.getKey();
                    int end = tree.get(val + 1);
                    tree.remove(val + 1);
                    tree.remove(low.getKey());
                    tree.put(start, end);
                }
                else
                    tree.put(low.getKey(), val);
                return;
            }
    
            // Value can merge to start
            Map.Entry<Integer, Integer> high = tree.higherEntry(val);
            if (high != null && high.getKey() == val + 1) {
                int end = high.getValue();
                tree.remove(high.getKey());
                tree.put(val, end);
                return;
            }
    
            // Isolated new value
            tree.put(val, val);
        }        
        
        public List<Interval> getIntervals() {
            List<Interval> l = new LinkedList<>();
    
            for (Map.Entry<Integer, Integer> entry : tree.entrySet())
                l.add(new Interval(entry.getKey(), entry.getValue()));
    
            return l;        
        }
    }

Log in to reply
 

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