C++ solution using vector and binary search with explanation


  • 8
    S

    For a new number n, find and return the index of interval [s, t] such that s is the largest 'start' that is smaller than n. If no such interval exists, return -1. This is done using binary search.

    For example,

    • new number 5, intervals [[1,1], [4,6], [8,8]], binary search returns 1.

    • new number 0, intervals [[1,1], [4,6], [8,8]], binary search returns -1.

    After we find this 'index', there are three circumstances:

    1. intervals[index] already contains val. Do nothing.

    2. val can be merged into intervals[index+1]. Modify intervals[index+1].start to val.

    3. val can be merged into intervals[index]. Modify intervals[index].end to val.

    4. val can't be merged into either interval. Insert Interval( val, val).

    Finally, after inserting val, we need to check whether intervals[index] and intervals[index+1] can be merged.

    class SummaryRanges {
    private:
        vector<Interval> intervals = vector<Interval>();
        
        int binarySearch(vector<Interval> intervals, int val) {
            return binarySearchHelper(intervals, 0, intervals.size(), val);
        }
        
        int binarySearchHelper(vector<Interval> intervals, int start, int end, int val) {
            if (start == end) return -1;
            if (start+1 == end && intervals[start].start < val) return start;
            
            int mid = (start + end)/2;
            if (intervals[mid].start == val) {
                return mid;
            } else if (intervals[mid].start < val) {
                return binarySearchHelper(intervals, mid, end, val);
            } else { //intervals[mid] > val
                return binarySearchHelper(intervals, start, mid, val);
            }
        }
        
    public:
        /** Initialize your data structure here. */
        SummaryRanges() {
            
        }
        
        /** For a new number n, find the last(biggest) interval
         *  [s,t], such that s < n. If no such interval exists, 
         *  return -1.
         */
        void addNum(int val) {
            int index = binarySearch(intervals, val);
            
            // intervals[index] contains val
            if (index != -1 && intervals[index].end >= val) {
                return;
            }
            
            if (index != intervals.size()-1 && val + 1 == intervals[index+1].start) {
                intervals[index+1].start = val;
            } else if (index != -1 && val - 1 == intervals[index].end) {
                intervals[index].end = val;
            } else {
                intervals.insert(intervals.begin() + index + 1, Interval(val, val));
            }
            
            //merge intervals[index] with intervals[index+1]
            if (index != -1 && intervals[index].end + 1 == intervals[index+1].start) {
                intervals[index].end = intervals[index+1].end;
                intervals.erase(intervals.begin()+index+1);
            }
            
            return;
        }
        
        vector<Interval> getIntervals() {
            return this->intervals;
        }
    };

  • 0

    This solution is pretty straight-forward. To addNum, the binary search takes O(log N) and then to insert the number into the intervals, best case it will take O(1) and worst case O(N). So the total time is best O(log N), and worst O(N + log N).


  • 0

    Python solution with the same idea:

    class SummaryRanges(object):
    
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self.intervals = []
    
        def _binary_search(self, val):
            if len(self.intervals) == 0:
                return -1
            left, right = 0, len(self.intervals) - 1
            while left + 1 < right:
                mid = left + (right - left) / 2
                if self.intervals[mid].start == val:
                    return mid
                elif self.intervals[mid].start > val:
                    right = mid
                else:
                    left = mid
            if self.intervals[right].start <= val:
                return right
            elif self.intervals[left].start <= val:
                return left
            return -1
        
        def addNum(self, val):
            """
            :type val: int
            :rtype: void
            """
            """ 
            For a new number val, find the last(biggest) interval
            [s,t], such that s <= val. If no such interval exists, 
            return -1.
            """
            index = self._binary_search(val)
            if index != -1 and self.intervals[index].end >= val:
                return
            if index != len(self.intervals) - 1 and self.intervals[index + 1].start == val + 1:
                self.intervals[index + 1].start = val
            elif index != -1 and val - 1 == self.intervals[index].end:
                self.intervals[index].end = val
            else:
                self.intervals = self.intervals[:index + 1] + [Interval(val, val)] + self.intervals[index + 1:]
            
            if index != -1 and index != len(self.intervals) - 1 and self.intervals[index].end + 1 == self.intervals[index + 1].start:
                self.intervals[index].end = self.intervals[index + 1].end
                self.intervals = self.intervals[:index + 1] + self.intervals[index + 2:]
    
        def getIntervals(self):
            """
            :rtype: List[Interval]
            """
            return self.intervals
    

  • 0
    G

    I love your solution! I just want to point out that there might be a bug in your solution. When you merge the intervals, you check if index != -1 but you don't check if index < intervals.size(). Although the code still works, that's just because the compiler somehow returns 0 when you access an element out of the vector's bounds. For example, on a vector of size 5, intervals[10].start returns 0 instead of crashing. :o So, in the case of addNum(1) then addNum(2), I would expect the code to make [1,1], then make[1,2], then when it gets to the merge intervals code, it'll try to access intervals[index+1].start. Index is 0, and size of intervals is 1, so element at index 1, shouldn't exist. I expect it to crash but it doesn't. Thanks for reading!


Log in to reply
 

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