200ms easy java binary search code


  • 0
    R

    O(logn) for searching. O(1) for checking merging. However, adding and removing intervals may cost O(n).

    public class SummaryRanges {

    private List<Interval> ranges;
    
    public SummaryRanges() {
        ranges = new ArrayList<>();
    }
    
    public void addNum(int val) {
        // binary search
        int lo = 0, hi = ranges.size();
        int mid = (lo + hi) / 2;
        while (lo < hi) {
            Interval i = ranges.get(mid);
            if (i.start <= val && val <= i.end) {
                // num already added
                return;
            } else if (i.start > val) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
            mid = (lo + hi) / 2;
        }
        // does not exist duplicates, then add new interval
        ranges.add(lo, new Interval(val, val));
        
        // merge with the one after if necessary
        if (lo < ranges.size() - 1 && ranges.get(lo + 1).start == val + 1) {
            ranges.get(lo).end = ranges.get(lo + 1).end;
            ranges.remove(lo + 1);
        }
        
        // merge with the one before if necessary
        if (lo > 0 && ranges.get(lo - 1).end == val - 1) {
            ranges.get(lo - 1).end = ranges.get(lo).end;
            ranges.remove(lo);
        }
    }
    
    public List<Interval> getIntervals() {
        return ranges;
    }
    

    }


Log in to reply
 

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