C++ solution with vector beats 96.52%


  • 0
    Y
    class SummaryRanges {
    public:
        /** Initialize your data structure here. */
        SummaryRanges() {
            
        }
        
        void addNum(int val) {
            int idx = find(val);
            if (idx == -2) return; // val already exists
            if (idx == -1) {
                if (!data.empty() && data[0].start == val + 1) {
                    data[0].start--;
                    return;
                }
                
                Interval i(val, val);
                data.insert(data.begin(), i);
            }
            else {
                bool left = false, right = false;
                if (data[idx].end == val - 1) left = true;
                if (idx + 1 < data.size() && data[idx + 1].start == val + 1) right = true;
                
                if (left && right) {
                    data[idx].end = data[idx + 1].end;
                    data.erase(data.begin() + idx + 1);
                }
                else if (left) data[idx].end++;
                else if (right) data[idx + 1].start--;
                else {
                    Interval i(val, val);
                    data.insert(data.begin() + idx + 1, i);
                }
            }
        }
        
        vector<Interval> getIntervals() {
            return data;
        }
        
    private:
        vector<Interval> data;
        
        int find(int val) { // find the last idx such that data[idx].end < val
            if (data.empty()) return -1;
            int lo = 0, hi = data.size() - 1, mid;
            while (lo < hi) {
                mid = lo + (hi - lo + 1) / 2;
                if (val >= data[mid].start && val <= data[mid].end) return -2;
                if (data[mid].end > val) hi = mid - 1;
                else lo = mid;
            }
            
            if (val >= data[lo].start && val <= data[lo].end) return -2;
            if (data[lo].end > val) return -1;
            else return lo;
        }
    };
    

  • 0
    A

    I guess the problem description should clarify which method is called more often.

    You solution has O(n) addNum but O(1) getIntervals

    while the normal BST & LinkedList solution has O(lgn) addNum and O(n) getIntervals


  • 0
    A

    @AdamCe The follow up has this information about operation frequency:

    Follow up:
    What if there are lots of merges and the number of disjoint intervals are small compared to the data stream's size?


Log in to reply
 

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