Java fast simple code using TreeMap with detailed explanation


  • 3

    The idea is map all map all val to its left bond of containing interval for fast lookup.
    Store intervals in TreeMap as it seems to require output intervals in ascending order.(if ascending order is not required, I would use a hashmap for maximum performance)

    5 cases
    0: isolated val

    1: val already in existing interval
    e.g [1,6] 3, do nothing

    1. val is connected to interval on its left
      e.g [1,2] 3

    2. val is connected to interval on its right
      e.g. [4, 7] 3

    3. val is connected on both side
      e.g [1,2] [4, 7] 3.

    The algorithm actually finds the possible left or right intervals to val, (or both). remove the old intervals,
    insert the new interval in the TreeMap. Update valueToBond hashmap to ensure the right bound val can find its correct left bound. Note that some val in the middle of the interval won't find correct left bound. But that is OK as we will not access to the middle values in the future! The left bound, right bound values must find their correct left bound.

     public class SummaryRanges {
            private Map<Integer, Integer> valueToBond;//map val to containing interval left bound
            private Map<Integer, Interval> bondToInterval; // store intervals in TreeMap <left bound, interval>
            
            public SummaryRanges() {
                valueToBond = new HashMap<>();
                bondToInterval = new TreeMap<>();
            }
            
            public void addNum(int val) {
                //contained in an existing interval
                if (valueToBond.containsKey(val)) {
                    return;
                }
                //isolated number, no connection to its left or right
                if (!valueToBond.containsKey(val - 1) && !valueToBond.containsKey(val + 1)) {
                    valueToBond.put(val, val);
                    bondToInterval.put(val, new Interval(val, val));
                    return;
                }
                //may connect to left, right or both
                int left = valueToBond.containsKey(val - 1) ? valueToBond.get(val - 1) : val;
                int right = valueToBond.containsKey(val + 1) ? bondToInterval.get(valueToBond.get(val + 1)).end : val;
                valueToBond.put(val, left);
                valueToBond.put(right, left);
                bondToInterval.remove(val + 1);
                bondToInterval.put(left, new Interval(left, right));
            }
            
            public List<Interval> getIntervals() {
                return new ArrayList<>(bondToInterval.values());
            }
        }

Log in to reply
 

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