O(n) solution | 20 lines of code | c++


  • 0
    P

    Create 2 hash.
    hash1(vector) : of size max number seen in the stream which contains non zero values in batches. Example, [1,3] [6, 7] => [0, 1, 2, 3, 0, 0, 1, 2]
    hash2(map) : which contains 2nd element of each interval as key, diff from first element of interval as value.

     * Definition for an interval.
     * struct Interval {
     *     int start;
     *     int end;
     *     Interval() : start(0), end(0) {}
     *     Interval(int s, int e) : start(s), end(e) {}
     * };
     */
    class SummaryRanges {
    public:
        //int fsize = 0;
        vector<int> hash1;
        map<int, int> hash2;
        /** Initialize your data structure here. */
        SummaryRanges() {
            int fsize = 0;
        }
        
        void addNum(int val) {
            int n = hash1.size();
            while(n++ <= val) hash1.push_back(0);
            if(hash1[val] == 0) {
                hash1[val] = hash1[val-1]+1;
                if(hash1[val-1] != 0) hash2.erase(val-1);
            }
            int i = val+1;
            while(i < hash1.size() && hash1[i] != 0)
            {
                hash1[i] = hash1[i-1]+1;
                i++;
            }
            hash2[i-1] = hash1[i-1];
        }
        
        vector<Interval> getIntervals() {
            map<int, int>::iterator it;
            vector<Interval> res;
            for(it=hash2.begin(); it != hash2.end(); ++it)
            {
                Interval in = Interval(it->first-(it->second-1), it->first);
                res.push_back(in);
                
            }
            return res;
        }
    };
    
    /**
     * Your SummaryRanges object will be instantiated and called as such:
     * SummaryRanges obj = new SummaryRanges();
     * obj.addNum(val);
     * vector<Interval> param_2 = obj.getIntervals();
     */```

Log in to reply
 

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