C++ solution using an (unbalanced) custom BST, with heavy comments


  • 0
    A
    /**
     * 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 {
        
        /*
         * Basic idea: The set of disjoint intervals at any point itself is an ordered set.
         * Thinking of the intervals marked along the number line, it is easy to see that there is an ordering of intervals.
         * Since they are disjoint, we could either order them by the start point (l) or the end point (r), and get the same result.
         *
         * Supports insertion in O( log I ) and getIntervals() in O(I) where I is the number of intervals.
         *
         * Instead of using std::set<>, we implement the requried BST operations from scratch.
         */
        
        // Structure to hold a node in the BST. Each node in the BST is an interval, i.e. a pair [l, r] of numbers.
        struct TreeNode {
            int l, r; // [l, r] are the ends of the interval
            TreeNode *left, *right, *parent;
            TreeNode( TreeNode *parent_, int l_, int r_ ) : l ( l_ ), r( r_ ), left( nullptr ), right( nullptr ), parent( parent_ ) {}
        } *m_root;
        
        // The usual BST successor method
        TreeNode *successor( TreeNode *node ) {
            if( !node )
                return nullptr;
            if( !node->right ) {
                while( node->parent && node == node->parent->right )
                    node = node->parent;
                if( !node->parent )
                    return nullptr;
                node = node->parent;
            }
            if( node->right ) {
                node = node->right;
                while( node->left )
                    node = node->left;
            }
            return node;
        }
        
        // The usual BST predecessor method
        TreeNode *predecessor( TreeNode *node ) {
            if( !node )
                return nullptr;
            if( !node->left ) {
                while( node->parent && node == node->parent->left )
                    node = node->parent;
                if( !node->parent )
                    return nullptr;
                node = node->parent;
            }
            if( node->left ) {
                node = node->left;
                while( node->right )
                    node = node->right;
            }
            return node;
        }
        
        // This method takes two intervals on the tree, and if they can be coalesced, coalesces them.
        // Assumes BST structure is preserved.
        //
        // Basically, a pair of intervals like [1, 3] and [4, 7] can be coalesced into [1, 7].
        // This algorithm is similar to BST delete -- we delete one of the intervals and extend the other.
        // Since these form a pair of subsequent nodes in an in-order traversal of the tree, at least one of the two given nodes has < 2 children
        
        void coalesce( TreeNode *a, TreeNode *b ) {
            if( !a || !b || a == b )
                return;
            
            if( ( b->r + 1 == a->l ) == ( a->r + 1 == b->l ) )
                return;
            
            // To avoid the complicated case of removing a node with both children, we pick the easier one (the one with one or zero children) to splice out.
            TreeNode *spliceOut = ( (a->left && a->right ) ? b : a );
            TreeNode *other = (spliceOut == a ? b : a );
            assert( ! ( spliceOut->left && spliceOut->right ) );
            
            TreeNode *swapChild = nullptr;
            
            // parentPatch is the pointer to the pointer in the parent of spliceOut that currently points to spliceOut.
            // we shall later repoint the pointer to point to spliceOut's child, if any.
            TreeNode **parentPatch = ( spliceOut->parent ? 
                    &( spliceOut->parent->left == spliceOut ? spliceOut->parent->left : spliceOut->parent->right )
                    : nullptr
                    );
                    
            // Handle the case where spliceOut has a child : put the child in spliceOut's place
            if( spliceOut->left || spliceOut->right ) {
                swapChild = ( spliceOut->left ? spliceOut->left : spliceOut->right );
                swapChild->parent = spliceOut->parent;
            }
            ( parentPatch ? *parentPatch : m_root ) = swapChild; // swapChild could be nullptr
            
            // Do the actual task of extending the intervals, completing the coalesce operation.
            if( other->l == spliceOut->r + 1 )
                other->l = spliceOut->l;
            else
                other->r = spliceOut->r;
            
            // Free the spliced out node
            delete spliceOut;
        }
        
    public:
        /** Initialize your data structure here. */
        SummaryRanges() : m_root( nullptr ) {
            
        }
        
        // This method is similar to BST insert, but with some additional complications.
        // We keep working down the tree looking for the right place to insert, just as in BST insert,
        // making a decision to go left / right at each stage.
        //
        // However, one of four cases could occur when we have found the "right" place:
        // 1. val was already added, in which case there is an interval [l, r] that contains val.
        //      We have nothing to do in this case.
        // 2. There is an interval [val + 1, r] in the tree
        //      In this case, we extend the interval to [val, r],
        //      and then see if the interval can now be coalesced with its predecessor
        // 3. There is an interval [l, val - 1] in the tree
        //      In this case, we extend the interval to [l, val],
        //      and then see if the interval can now be coalesced with its successor
        // 4. None of the above -- val was not found in the tree, and does not lie at an interval edge
        //      In this case, we add the interval [val, val] to the tree at the appropriate location
        
        void addNum(int val) {
        
            if( !m_root ) {
                m_root = new TreeNode( nullptr, val, val );
                return;
            }
            
            TreeNode *curr = m_root, *parent = nullptr;
            while( curr ) {
                if( curr->l <= val && val <= curr->r ) {
                    // Case 1: already in our tree, nothing to do
                    return;
                }
                if( curr->l == val + 1 ) {
                    // Case 2: coalesce left
                    curr->l = val; // expand the interval to the left
                    TreeNode *pred = predecessor( curr );
                    coalesce( pred, curr );
                    return;
                }
                if( curr->r == val - 1 ) {
                    // Case 3: coalesce right
                    curr->r = val; // expand to the right
                    TreeNode *succ = successor( curr );
                    coalesce( succ, curr );
                    return;
                }
                
                // We haven't yet found our insert point, look around
                parent = curr;
                if( curr->r < val )
                    curr = curr->right;
                else
                    curr = curr->left;
            }
            
            // Case 4: val was not found. Insert the new interval [val, val] under the appropriate insertion point.
            ( parent->r < val ? parent->right : parent->left ) = new TreeNode( parent, val, val );
            
        }
        
        // This method is a straightforward in-order traversal. I like to use a recursive form to do the in-order traversal,
        // contained in a lambda function object. The function object captures the result vector and writes to it as a side-effect.
        vector<Interval> getIntervals() {
            std::vector<Interval> v;
            std::function<void( const TreeNode * )> inOrder = [&v, &inOrder]( const TreeNode *node ) {
                if( !node )
                    return;
                inOrder( node->left );
                v.emplace_back( node->l, node->r );
                inOrder( node->right );
            };
            inOrder( m_root );
            return v;
        }
    };
    
    /**
     * 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.