Share some idea using customized BST, 152ms, C++


  • 0
    F

    This solution is not a pretty one: the code is long and somehow takes time to read, since I define my own BST tree, and there are some basic operation mixture with algorithm itself. But I still want to share for kind of way to solve this interesting problem.

    There are lots of comments in the code, I hope you can understand by the comments. The basic idea for this algorithm is: build and maintain a BST with internal as node value, each time when add interval, do at most twice merge with exists nodes by following BST property; after merge, keep BST property the same.

    The complexity of this algorithm is:

    • addNum: O(logn)
    • getIntervals: O(# of intervals in tree)
    class SummaryRanges {
    public:
        struct RangeTreeNode {
            Interval range;
            RangeTreeNode* left;
            RangeTreeNode* right;
            RangeTreeNode(Interval _val) : range(_val), left(nullptr), right(nullptr) {}
            RangeTreeNode() : left(nullptr), right(nullptr) {}
        };
    
        SummaryRanges() {
            Interval root_val(INT_MAX, INT_MIN);
            root.range =  root_val;
        }
        
        /*
         * two things should be noticed: 
         *   1) everytime, at most two Intervals could be merge, so at most two times of merge may happen.
         *   2) based on 1), every time after merge happen, the BST properity should always be kept.
        */
        void addNum(int val) {
            // check if val already in some range in the tree, if so, current addNum is dup, ignore
            if(isInRange(val, root.left)) return ;
    
            // find if there exists some node that could do merge, if so, cur should return the lowest such node
            RangeTreeNode* parent = &root, *cur = root.left;
            while(cur != nullptr && cur->range.start-1 != val && cur->range.end+1 != val) {
                parent = cur;
                cur = (val < cur->range.start ? cur->left : cur->right);
            }
    
            // determine if such node exists or not, if not, then just simply insert the node into the tree
            if(cur == nullptr) {
                Interval ninterval(val, val);
                RangeTreeNode* nnode = new RangeTreeNode(ninterval);
                parent->left = (val < parent->range.start ? nnode : parent->left);
                parent->right = (val > parent->range.end ? nnode : parent->right);
            }else {
                // otherwise, we have such node, do merge TWICE: first is val with cur node, another one is with the successor or prvior
                // notice: in first merge, it is possible merge with left bound or right bound, so, depends on which side, different code handles
                // 
                if(cur->range.start-1 == val) {
                    // merege with left bound of current node, in this case,
                    // we should find the previor and check if we can merge or not
                    
                    /* following statement do first merge: */
                    cur->range.start = val;
    
                    /* following code do second merge: */
                    // also, second time merge should help with keeping BST properity
                    // the prvior, if exists, must occured in subtree, rooted with cur->left, the right most node
                    RangeTreeNode* rcur = cur->left, *rparent = cur->left;
                    for(;rcur != nullptr && rcur->right != nullptr; rparent = rcur, rcur = rcur->right) {}
                    
                    // find this right most node, here, we have two case: first one is cur->right is nullptr(consider a tree with just root node, then merge)
                    // another one is not nullptr, we need to take care of second case.
                    if(rcur != nullptr && rcur->range.end+1 == val) {
                        // do second time merge
                        cur->range.start = rcur->range.start;
                        /* NOTICE: do not make any assumption about node rcur:
                         * there exists a case that this rcur node doesn't have right child(this makes rcur node is right most node)
                         * but this node may have left child, so when deal with second merge, the binary search tree properity should be kept,
                         * therefore, adjust the left subtree of node rcur. if here use nullptr instead, bug occurs, some node will miss, BST is not correct
                        */ 
                        rparent->right = rcur->left;
    
                        // there also exists a case that rcur == cur->left, 
                        // in this case, this node just has left child and no right child
                        if(rparent == rcur) {
                            cur->left = rcur->left;
                        }
                        // after merge, the rcur node is no longer useful, delete it.
                        // afterall, the node is abandoned, except for pointer rcur point to this node,
                        // no other pointer points to it, whether like or not, this node bust be deleted
                        delete rcur;
                    }
                }else {
                    // similar with left bound merge, this statements take care of right bound
                    cur->range.end = val;
                    RangeTreeNode* lcur = cur->right, *lparent = cur->right;
                    for(;lcur != nullptr && lcur->left != nullptr; lparent = lcur, lcur = lcur->left) {}
                    if(lcur != nullptr && lcur->range.start-1 == val) {
                        cur->range.end = lcur->range.end;
                        lparent->left = lcur->right;
                        if(lparent == lcur) {
                            cur->right = lcur->right;
                        }
                        delete lcur;
                    }
                }
            }
            return ;
        }
        
        vector<Interval> getIntervals() {
            vector<Interval> ans;
            getIntervals(ans, root.left);
            return ans;
        }
    
        ~SummaryRanges() {
            del_tree(root.left);
        }
    
    private:
        // dummy root node, make life easier
        RangeTreeNode root;
    
        void getIntervals(vector<Interval> &ans, RangeTreeNode* rt) {
            if(rt == nullptr) return ;
            getIntervals(ans, rt->left);
            ans.push_back(rt->range);
            getIntervals(ans, rt->right);
        }
    
        bool isInRange(int val, RangeTreeNode* rt) {
            if(rt == nullptr) return false;
            return (val>=rt->range.start && val<=rt->range.end) || isInRange(val, rt->left) || isInRange(val, rt->right);
        }
    
        void del_tree(RangeTreeNode* rt) {
            if(rt == nullptr) return ;
            del_tree(rt->left);
            del_tree(rt->right);
            delete rt;
        }
    };
    

Log in to reply
 

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