Java binary search solution 190ms


  • 0

    Key point:

    1. Use the binary search to find an index in the existing list of intervals or find whether the number is already in the list.
    2. The returning index point to an interval which's start > val.
    3. Update this interval start to val if its start == val+1.
    4. Check the end value of the interval prior to this one if the returning index does not point to the first one.
    5. Merge these two intervals when they are connected by val. Or update the end value of the prior if its end value == val-1. Otherwise, add a new Interval for val.
        public class SummaryRanges {
            List<Interval> list;
            /** Initialize your data structure here. */
            public SummaryRanges() {
                list = new ArrayList();
            }
            
            public void addNum(int val) {
                if (list.isEmpty()) {
                    list.add(new Interval(val, val) );
                } else {
                    int len = list.size();
                    Interval lastone = list.get(len-1);
                    if (val > lastone.end) {
                        if ( val == lastone.end+1 ) lastone.end = val;
                        else list.add(new Interval(val, val));
                        return;
                    }
                    int s = 0;
                    int e = len;
                    while (s<e) {
                        int m = s+((e-s)/2);
                        Interval mid = list.get(m);
                        if ( mid.start <= val  && val <= mid.end) return;
                        if (val < mid.start ) e = m;
                        else s = m+1;
                    }
                    Interval inv = list.get(s);
                    Interval pre = s > 0 ?  list.get(s-1) : null;
                    if ( (inv.start-1) == val ) {
                        inv.start = val;
                        if ( pre != null && (pre.end+1) == val ) {
                            pre.end = inv.end;
                            list.remove(s);
                        }
                    } else {
                        if ( pre != null && (pre.end+1) == val ) {
                            pre.end = val;
                        } else {
                            list.add(s, new Interval(val, val));
                        }
                    }
                }
            }
            
            public List<Interval> getIntervals() {
                return list;
            }
        }
    

Log in to reply
 

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