Java 42ms solution using a trie and recursion


  • 0
    W

    I have this rather straightforward solution that finishes in 42 ms. Once or twice it gave me a time limit exception though. I'm not sure about complexity, as sometimes when the bit patterns are 1 0 and 0 1 I explore both branches. Any comment on the complexity analysis is very much appreciated. Here is the code:

    public class MaximumXORTwoNumbersArray {
    
        public static int findMaximumXOR(int[] nums) {
            Node node = buildTrie(nums);
            return find(node, node, 30, 0);
        }
    
        static int find(Node p, Node q, int count, int max) {
            if (count < 0) return max;
    
            if (p.hasLeft() && p.hasRight() && q.hasLeft() && q.hasRight())
                return Math.max(find(p.left, q.right, count - 1, max | (1 << count)),
                                find(p.right, q.left, count - 1, max | (1 << count)));
    
            if (p.hasLeft() && q.hasRight())
                return find(p.left, q.right, count - 1, max | (1 << count));
    
            if (p.hasRight() && q.hasLeft())
                return find(p.right, q.left, count - 1, max | (1 << count));
    
            if (p.hasRight() && q.hasRight())
                return find(p.right, q.right, count - 1, max);
    
            return find(p.left, q.left, count - 1, max);
        }
    
        static Node buildTrie(int[] nums) {
            Node root = new Node();
            int mask = 1 << 30;
            for (int i : nums)
                root = insert(i, mask, root);
            return root;
        }
    
        static Node insert(int i, int mask, Node node) {
            if (node == null) node = new Node();
            if (mask == 0) { node.val = i; return node; }
            if ((i & mask) != 0) // current bit is one
                node.right = insert(i, mask >> 1, node.right);
            else
                node.left  = insert(i, mask >> 1, node.left);
            return node;
        }
    
        static class Node {
            Node left;
            Node right;
            int val;
    
            boolean isLeaf() { return left == null && right == null; }
            boolean hasLeft() { return left != null; }
            boolean hasRight() {return right != null; }
        }
    }
    

Log in to reply
 

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