Java 194 ms using custom tree with merging nodes, O(#intervals) for space


  • 2
    B

    There are other solutions on the board that use TreeMap and binary search but I decided to try it by building my own binary search tree and merging nodes as I went to keep the tree as small as possible.

    public class SummaryRanges {
    private class IntervalNode
    {
        Interval i;
        IntervalNode left;
        IntervalNode right;
        
        public IntervalNode(int begin, int end)
        {
            i = new Interval(begin, end);
        }
        
        public boolean canMerge(int val)
        {
            return val >= i.start - 1 && val <= i.end + 1;
        }
        
        public void merge(int val)
        {
            if (val > i.end) i.end = val;
            if (val < i.start) i.start = val;
        }
        
        public boolean canMerge(IntervalNode other)
        {
            if (other.i.start >= i.start - 1 && other.i.start <= i.end + 1 ||
                i.start >= other.i.start - 1 && i.start <= other.i.end + 1) return true;
                
                return false;
        }
        
        public void mergeNodes(IntervalNode other)
        {
            if (other.i.start < i.start) i.start = other.i.start;
            if (other.i.end > i.end) i.end = other.i.end;
        }
    }
    
    private IntervalNode overallRoot;
    
    // pretty dumb rebalancing but whateva
    private void rebalance(IntervalNode root, IntervalNode subTree)
    {
        if (root.left == null)
        {
            root.left = subTree;
        }
        else
        {
            rebalance(root.left, subTree);
        }
    }
    
    private IntervalNode updateTree(IntervalNode root, IntervalNode prevInterval, int val)
    {
        if (root == null && prevInterval == null)
        {
            return new IntervalNode(val, val);
        }
        else if (root == null)
        {
            return root;
        }
        
        if (root.canMerge(val) && prevInterval == null)
        {
            root.merge(val);
            prevInterval = root;
        }
        else if (prevInterval != null && root.canMerge(prevInterval))
        {
            prevInterval.mergeNodes(root);
            if (root.right != null)
            {
                rebalance(root.right, root.left);
                return root.right;
            }
            else
            {
                return root.left;
            }
        }
        
        if (val > root.i.start)
        {
            root.right = updateTree(root.right, prevInterval, val);
        }
        else
        {
            root.left = updateTree(root.left, prevInterval, val);
        }
        
        return root;
    }
    
    public void addNum(int val) {
        if (overallRoot == null)
        {
            overallRoot = new IntervalNode(val, val);
        }
        else
        {
            overallRoot = updateTree(overallRoot, null, val);            
        }
    }
    
    private void inorder(IntervalNode root, List<Interval> results)
    {
        if (root != null)
        {
            inorder(root.left, results);
            results.add(root.i);
            inorder(root.right, results);
        }
    }
    
    public List<Interval> getIntervals() {
        List<Interval> results = new ArrayList<Interval>();
        inorder(overallRoot, results);
        return results;
    }
    

    }


Log in to reply
 

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