O(logN) got Output Limit Exceeded but works fine for Custom Testcase??


  • 0
    M

    I use stl::map to store the pair (start, end) for each interval. Look like it is an O(logN) algorithm for each "addNum" operation. However, I got Output Limit Exceeded after submission. I pasted the "Last executed input" into Custom Testcase but my code worked fine. Can anybody help me find out what's wrong?

    class SummaryRanges {
    private:
        map<int, int> itvlMap;  // mapping start --> end
        
    public:
        /** Initialize your data structure here. */
        SummaryRanges() {
        }
        
        void addNum(int val) {
            int n = itvlMap.size();
            
            if (n == 0)
            {
                itvlMap.insert(make_pair(val, val));
                return;
            }
            
            auto it = itvlMap.lower_bound(val);
            
            if (it == itvlMap.end())
            {
                auto it_last = it;
                it_last--;
                
                int lastItvlStart = it_last->first;
                int lastItvlEnd = it_last->second;
                
                if (val - lastItvlEnd > 1)
                    itvlMap.insert(it, make_pair(val, val));
                else
                    it_last->second = val;
            }
            else if (it == itvlMap.begin())
            {
                int nextItvlStart = it->first;
                int nextItvlEnd = it->second;
                
                if (nextItvlStart - val > 1)
                    itvlMap.insert(it, make_pair(val, val));
                else
                {
                    itvlMap.insert(it, make_pair(val, nextItvlEnd));
                    itvlMap.erase(it);
                }
            }
            else
            {
                auto it_last = it;
                it_last--;
                
                int lastItvlStart = it_last->first;
                int lastItvlEnd = it_last->second;
                int nextItvlStart = it->first;
                int nextItvlEnd = it->second;
                
                int leftDist = val - lastItvlEnd;
                int rightDist = nextItvlStart - val;
                
                if (rightDist > 1 && leftDist > 1)
                    itvlMap.insert(it, make_pair(val, val));
                else
                {
                    if (leftDist == 1 && rightDist != 1)
                        it_last->second = val;
                    else if (rightDist == 1 && leftDist != 1)
                    {
                        itvlMap.insert(it, make_pair(val, nextItvlEnd));
                        itvlMap.erase(it);
                    }
                    else if (rightDist == 1 && leftDist == 1)
                    {
                        it_last->second = nextItvlEnd;
                        itvlMap.erase(it);
                    }
                }
            }
         }
        
        vector<Interval> getIntervals() {
            vector<Interval> res;
            
            for (auto& itvl : itvlMap)
                res.push_back(Interval(itvl.first, itvl.second));
            
            return res;
        }
    };
    

  • 0

    @Mark_Zang Here is my map solution in C++. Good luck.

    class SummaryRanges {
    private:
        map<int, Interval> intervals_map;
    public:
        /** Initialize your data structure here. */
        SummaryRanges() {
            
        }
        
        void addNum(int val) {
            if(intervals_map.count(val)) return ;
            auto next = intervals_map.upper_bound(val);
            auto pre = (next==intervals_map.begin())? intervals_map.end() : prev(next);
            if(next!=intervals_map.end() && pre!=intervals_map.end() && next->second.start==val+1 && pre->second.end==val-1)
            {
                pre->second.end = next->second.end;
                intervals_map.erase(next);
            }
            else if(pre!=intervals_map.end() && pre->second.end>=val-1) pre->second.end = max(val, pre->second.end);
            else if(next!=intervals_map.end() && next->second.start==val+1)
            {
                intervals_map[val] = {val, next->second.end};
                intervals_map.erase(next);
            }
            else if(next==intervals_map.end() && !intervals_map.empty() && intervals_map.rbegin()->second.end>=val) return ;
            else intervals_map[val] = {val, val};
        }
        
        vector<Interval> getIntervals() {
            vector<Interval> v;
            for(auto& pair: intervals_map) v.push_back(pair.second);
            return v;
        }
    };
    

Log in to reply
 

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