Java, TreeMap, O(ln n) per add, O(n ln(n)) per get, beats 98.8%


  • 1
    T

    Trivial solution idea: look up neighboring intervals, checking x - 1, x, x + 1 using binary search tree.

    Implementation optimizations:

    • used TreeMap (over TreeSet) to remove and retrieve an interval with a single operation
    • used SortedMap over HashMap/HashSet to get ordering "for free" and need only one data structure for begin and end
    • avoided unnecessary Interval object creation in addNum
    import static java.lang.Math.*;
    public class SummaryRanges {
        Map<Interval, Interval> intervals =
            new TreeMap<>((a, b) -> max(a.start, b.start) <= min(a.end, b.end) ? 0 : a.start - b.start);
        Interval query = new Interval();
        Interval accum = null;
    
        public void addNum(int x) {
            accum = remove(x);
            merge(remove(x - 1));
            merge(remove(x + 1));
            if (accum == null || x < accum.start || accum.end < x)
                merge(new Interval(x, x));
            intervals.put(accum, accum);
        }
    
        public List<Interval> getIntervals() {
            return new ArrayList<>(intervals.keySet());
        }
    
        Interval remove(int x) {
            query.start = query.end = x;
            return intervals.remove(query);
        }
    
        void merge(Interval operand) {
            if (accum == null) {
                accum = operand;
            } else if (operand != null) {
                accum.start = min(accum.start, operand.start);
                accum.end = max(accum.end, operand.end);
            }
        }
    }
    

Log in to reply
 

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