Java fast log (N) solution (186ms) without using the TreeMap but a customized BST


  • 14
    public class SummaryRanges {
        class BSTNode {
            Interval interval;
            BSTNode left;
            BSTNode right;
            BSTNode(Interval in){
                interval = in;
            }
        }
        
        BSTNode findMin(BSTNode root) {
            if (root == null) return null;
            if (root.left == null ) return root;
            else return findMin(root.left);
        }
        
        BSTNode remove(Interval x, BSTNode root) {
            if (root == null) return null;
            else if ( x == null ) return root;
            else if (x.start > root.interval.end ) {
                root.right = remove(x, root.right);
            } else if (x.end < root.interval.start ) {
                root.left = remove(x, root.left);
            } else if ( root.left != null && root.right != null) {
                root.interval = findMin(root.right).interval;
                root.right = remove( root.interval, root.right);
            } else {
                root = ( root.left != null ) ? root.left : root.right;
            }
            return root;
        }
        
        BSTNode findKey(int val, BSTNode root) {
            if (root == null) return null;
            if (root.interval.start > val) {
                return findKey(val, root.left);
            } else if (root.interval.end < val) {
                return findKey(val, root.right);
            } else return root;
        }
        
        BSTNode addKey(int val, BSTNode root) {
            if (root == null) {
                root = new BSTNode( new Interval(val, val) ); 
            } else if (root.interval.start > val) {
                root.left = addKey(val, root.left);
            } else if (root.interval.end < val) {
                root.right = addKey(val, root.right);
            }  
            return root;
        }
        void inOrder(BSTNode root) {
            if (root != null) {
                inOrder(root.left);
                list.add(root.interval);
                inOrder(root.right);
            }
        }
        
        /** Initialize your data structure here. */
        BSTNode root;
        List<Interval> list = new ArrayList();
        public SummaryRanges() {
            root = null;
        }
        
        public void addNum(int val) {
            if (root == null) {
                root = addKey(val, root);
            } else {
                if ( findKey(val, root) != null) return;
                BSTNode left = findKey(val-1, root);
                BSTNode right = findKey(val+1, root);
                if (left == null && right == null) {
                    root = addKey(val, root);
                } else if (left != null && right == null) {
                    left.interval.end++;
                } else if (left == null && right != null) {
                    right.interval.start--;
                } else {
                    Interval l = left.interval;
                    int e = right.interval.end;
                    root = remove(right.interval, root);
                    l.end = e;
                }
            }
        }
        
        public List<Interval> getIntervals() {
            list.clear();
            inOrder(root);
            return list;
        }
    }

  • 0
    B

    Nice! Very similar to my own solution.

    enter link description here


  • 1
    F

    Nice solution, but how can this be log (n) if the tree is not balanced? Consider following input 1 3 5 7 9 11 13 15 17 .... It will have to traverse through entire tree to insert the latest interval.


  • 0

    Similar to QuickSort algorithm, this is the worst case, when picking the first one as pivot on a sorted array.....


  • 0
    S

    @yubad2000 Very nice solution. I had similar ideas and did it my own, but somehow my root node is never updated when the call finished. And I could not wrap my head around it. Could you take a look please?

    public class SummaryRanges {
    
    class Node{
        Node left;
        Node right;
        Interval interval;
        int start;
        
        public Node(int start, Interval interval){
            this.start = start;
            this.interval = interval;
        }
        
        public Node(Interval interval){
            this.interval = interval;
        }
        
        public int shouldExpandAndUpdateInterval(int otherVal){
            //1 means otherVal is greater than interval.end by 1 and current interval should be expanded by 1
            //-1 means otherVal is smaller than interval.start by 1 and current interval should be expanded by 1
            //0 means otherVal lies in between the current interval
          //2 means it should continue with the RIGHT subtree
          //-2 means it should continue with the LEFT subtree
            
            if(interval.end + 1 == otherVal) return 1;
            if(otherVal + 1 == start) return -1;
            else if(otherVal <= interval.end && otherVal >= interval.start) return 0;
            else if(otherVal - interval.end > 1) return 2;
            else return -2;
        }
    }
    
    Node root;
    
    /** Initialize your data structure here. */
    public SummaryRanges() {
        root = null;//new Node(Integer.MIN_VALUE, new Interval());
    }
    
    public void addNum(int val) {
        addNum(val, root);
    }
    
    public void addNum(int val, Node root) {
        if(root == null || root.start == Integer.MIN_VALUE){
            root = new Node(val, new Interval(val, val));
        }
        else if(root.shouldExpandAndUpdateInterval(val) == 0){
            //no merge needed, val is already in this node interval, no action needed in this case
        }
        else if(root.shouldExpandAndUpdateInterval(val) == -1){
            root.interval.start = val;
            root.start = val;
            //merge this root with its left subtree if necessary
            mergeWithLeft(root);
        }
        else if(root.shouldExpandAndUpdateInterval(val) == 1){
          //this val should be inserted into the RIGHT subtree somewhere or create a new interval for it
            root.interval.end = val;
            //merge this root with its right subtree if necessary
            mergeWithRight(root);
        }
        else if(root.shouldExpandAndUpdateInterval(val) == 2){
            addNum(val, root.right);
        }
        else if(root.shouldExpandAndUpdateInterval(val) == -2){
            addNum(val, root.left);
        }
    }
    
    private void mergeWithRight(Node root) {
        if(root.right == null) return;
        if(root.right.interval.start == root.interval.end || root.right.interval.start -1 == root.interval.end){
            Node left = root.right.left;
            Node right = root.right.right;
            root.interval.end = root.right.interval.end;
            root.left = left;
            root.right = right;
        }
    }
    
    private void mergeWithLeft(Node root) {
        if(root.left == null) return;
        if(root.left.interval.end == root.start || root.left.interval.end + 1 == root.start){
            Node left = root.left.left;
            Node right = root.left.right;
            //we'll merge the two intervals
            root.interval.start = root.left.interval.start;
            //append its left child's children to become its children
            root.left = left;
            root.right = right;
        }
        //else no action needed
    }
    
    public List<Interval> getIntervals() {
        List<Interval> result = new ArrayList<Interval>();
        dfs(root, result);
        return result;
    }
    
    private void dfs(Node root, List<Interval> result) {
        if(root == null) return;
        if(root.left != null) dfs(root.left, result);
        result.add(root.interval);
        if(root.right != null) dfs(root.right, result);
    }
    
    public static void main(String...strings){
        System.out.print("Begins!");
        SummaryRanges test = new SummaryRanges();
        int[] nums = new int[]{1,3,7,2,6};
        for(int i : nums){
            test.addNum(i);
            List<Interval> intervals = test.getIntervals();
            print(intervals);
        }
        System.out.print("Ended!");
    }
    
    private static void print(List<Interval> intervals) {
        for(Interval interval : intervals){
            System.out.print(interval.toString());
        }
        System.out.println();
    }
    }
    

    And here's my output when submitted to OJ:
    Input:
    ["SummaryRanges","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals"]
    [[],[1],[],[3],[],[7],[],[2],[],[6],[]]
    Output:
    [null,null,[],null,[],null,[],null,[],null,[]]
    Expected:
    [null,null,[[1,1]],null,[[1,1],[3,3]],null,[[1,1],[3,3],[7,7]],null,[[1,3],[7,7]],null,[[1,3],[6,7]]]

    Basically, my root is always emptied when my recursive call finished.
    However, I have single stepped through my code in Eclipse, the logic is all right.

    Any help would be really appreciated.


  • 0
    S

    @bdwalker Very cool! I've similar ideas, I posted my code below, could you help me take a look as well! Much appreciated!


  • 0

    @steve.j.sun said in Java fast log (N) solution (186ms) without using the TreeMap but a customized BST:

    private void mergeWithRight(Node root) {
    if(root == null) return; <==== should be root.right
    if(root.right.interval.start == root.interval.end || root.right.interval.start -1 == root.interval.end){
    Node left = root.right.left;
    Node right = root.right.right;
    root.interval.end = root.right.interval.end;
    root.left = left;
    root.right = right;
    }
    }

    Found a bug. Not sure that is the problem of the empty root.


  • 0
    S

    @yubad2000 Thanks for pointing that out, I missed that. But after adding that, it's still giving me the same empty result... I don't see anything wrong with the code, any help is really appreciated!


  • 1

    @steve.j.sun
    By tracing your program using the test case [1,7,3,2,...], you will see an issue.
    A BST should look like this

        [1,1]           
           \
          [7,7]
           /
       [3,3]
    

    for the first three numbers.
    When 2 comes in, you program changes the root to [1,2] and ONLY checks the right children, [7,7] , which CANNOT find [3,3] to merge.
    Same issue with the left merge. The correct way is to search the entire left/right subtree and to find whether there is a node can be merged.


  • 0
    S

    @yubad2000 Thanks for the response again. I agree that's a new bug in this code, but first I think I'd like to understand how I can update root. If you actually run this code, you'll see that root always becomes null when each addNum() call ends, I'm really puzzled by this for now, I'd like to get this part fixed first. Any idea on this is greatly appreciated!
    e.g. when addNum(1) ends, root becomes null, and continuously when we call addNum(7), it starts with root == null again.


  • 0

    @steve.j.sun said in Java fast log (N) solution (186ms) without using the TreeMap but a customized BST:

    public void addNum(int val, Node root) {
    if(root == null || root.start == Integer.MIN_VALUE){
    root = new Node(val, new Interval(val, val));
    }
    else

    Java is pass-by-value so that "root=" statement does not update the global variable "root", instead, only updated the local "root".
    You can either change the local variable name or use "this.root" to specify the variable scope.


  • 0
    S

    @yubad2000 Right, I knew that. But apparently I failed to follow that again. But I figured out the fix for it: I have to return the root to the next call, and construct new node as left or right subtree for root, but have to return root for next call. Here's my updated code, it passed 8/9 test cases:

    public class SummaryRanges {
    
    Node root;
    
    /** Initialize your data structure here. */
    public SummaryRanges() {
        root = null;//new Node(Integer.MIN_VALUE, new Interval());
    }
    
    public void addNum(int val) {
        root = addNum(val, root);
    }
    
    public Node addNum(int val, Node root) {
        if(root == null || root.start == Integer.MIN_VALUE){
            root = new Node(val, new Interval(val, val));
            return root;
        }
        else if(root.shouldExpandAndUpdateInterval(val) == -1){
            root.interval.start = val;
            root.start = val;
            //merge this root with its left subtree if necessary
            return mergeWithLeft(root, root.left);
        }
        else if(root.shouldExpandAndUpdateInterval(val) == 1){
          //this val should be inserted into the RIGHT subtree somewhere or create a new interval for it
            root.interval.end = val;
            //merge this root with its right subtree if necessary
            return mergeWithRight(root, root.right);
        }
        else if(root.shouldExpandAndUpdateInterval(val) == 2){
            root.right = addNum(val, root.right);
            return root;
        }
        else if(root.shouldExpandAndUpdateInterval(val) == -2){
            root.left = addNum(val, root.left);
            return root;
        }
        return root;
    }
    
    private Node mergeWithRight(Node mergedRoot, Node rightNode) {
        if(rightNode == null) return mergedRoot;
        //check this rightNode first before checking its left subtree
        if(rightNode.start == mergedRoot.interval.end || rightNode.start -1 == mergedRoot.interval.end){
            //expand this mergedRoot.interval.end
            mergedRoot.interval.end = rightNode.interval.end;
            
            Node left = rightNode.left;
            Node right = rightNode.right;
            if(left != null){
                left.right = right;
            } else {
                left = right;
            }
            mergedRoot.right = left;
        }
        if(rightNode.left != null && rightNode.left.left == null) {
            //this is the node that should be merged if possible since it has the smallest start point
            if(rightNode.left.start == mergedRoot.interval.end || rightNode.left.start - 1 == mergedRoot.interval.end){
                mergedRoot.interval.end = rightNode.left.interval.end;
                
                Node right = rightNode.left.right;
                rightNode.left = right;
            }
        }
        if(rightNode.left != null){
            return mergeWithRight(mergedRoot, rightNode.left);
        }
        return mergedRoot;
    }
    
    private Node mergeWithLeft(Node mergedRoot, Node leftNode) {
        if(leftNode == null) return mergedRoot;
        //check this leftNode itself first before checking its right subtree
        if(leftNode.interval.end == mergedRoot.start || leftNode.interval.end + 1 == mergedRoot.start){
            mergedRoot.start = leftNode.interval.start;
            mergedRoot.interval.start = leftNode.interval.start;
            
            Node left = leftNode.left;
            Node right = leftNode.right;
            if(left != null){
                left.right = right;
            } else {
                left = right;
            }
            mergedRoot.left = left;
        }
        if(leftNode.right != null && leftNode.right.right == null){
            //this is the node that should be merged with mergedRoot if possible since it has the largest end
            if(leftNode.right.interval.end == mergedRoot.start || leftNode.right.interval.end + 1 == mergedRoot.start){
                mergedRoot.start = leftNode.right.interval.start;
                mergedRoot.interval.start = leftNode.right.interval.start;
                
                Node left = leftNode.right.left;
                leftNode.right = left;
            }
        }
        if(leftNode.right != null){
            return mergeWithLeft(mergedRoot, leftNode.right);
        }
        return mergedRoot;
    }
    
    public List<Interval> getIntervals() {
        List<Interval> result = new ArrayList<Interval>();
        dfs(root, result);
        return result;
    }
    
    private void dfs(Node root, List<Interval> result) {
        if(root == null) return;
        if(root.left != null) dfs(root.left, result);
        result.add(root.interval);
        if(root.right != null) dfs(root.right, result);
    }
    

    }

    class Node{
    Node left;
    Node right;
    Interval interval;
    int start;

    public Node(int start){
        this.start = start;
    }
    
    public Node(int start, Interval interval){
            this.start = start;
            this.interval = interval;
    }
    
    public Node(Interval interval){
        this.interval = interval;
    }
    
    public int shouldExpandAndUpdateInterval(int otherVal){
        //1 means otherVal is greater than interval.end by 1 and current interval should be expanded by 1
        //-1 means otherVal is smaller than interval.start by 1 and current interval should be expanded by 1
        //0 means otherVal lies in between the current interval
        
        if(interval.end + 1 == otherVal) return 1;
        if(otherVal + 1 == start) return -1;
        else if(otherVal <= interval.end && otherVal >= interval.start) return 0;
        else if(otherVal - interval.end > 1) return 2;//this means it should continue with the RIGHT subtree
        else return -2;//this means it should continue with the LEFT subtree
    }
    }
    

    The last test case is an extreme test case, too long to be pasted here, and from my eyes, I could hardly spot the difference between my output and the expected output.
    So I guess the hope to get this code AC'ed is to find the bug in the code?!?
    I'm really impressed by Leetcode's test coverage, :) but I don't know where my code is making it unhappy. :(


  • 0
    S
    This post is deleted!

Log in to reply
 

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