31ms O(n) Java solution using Trie


  • 4
    A

    We add the number into the trie and find the max possible XOR result at the same time.
    Node.set() method will set the new node in the trie if needed and return the new node.
    After setting the node, find the opposite bit in the trie to maximize the possible XOR result.

    public class Solution {
        public class Node {
            Node one;
            Node zero;
            Node() {
                this.one = null;
                this.zero = null;
            }
            Node set(int n) {
                if (n == 0) {
                    if (this.one == null) this.one = new Node();
                    return this.one;
                }
                if (this.zero == null) this.zero = new Node();
                return this.zero;
            }
        }
        
        public int findMaximumXOR(int[] nums) {
            Node root = new Node();
            int re = 0;
            for (int num : nums) {
                int digit = num;
                int tmp = 0;
                Node setNode = root;
                Node findNode = root;
                int pos = 30;
                while (pos >= 0) {
                    digit = (num >> pos) & 1;
                    setNode = setNode.set(digit);
                    if (digit == 1) {
                        if (findNode.one != null) {
                            tmp = tmp | (1 << pos);
                            findNode = findNode.one;
                        } else {
                            findNode = findNode.zero;
                        }
                    } else {
                        if (findNode.zero != null) {
                            tmp = tmp | (1 << pos);
                            findNode = findNode.zero;
                        } else {
                            findNode = findNode.one;
                        }
                    }
                    pos--;
                }
                re = Math.max(re, tmp);
            }
            return re;
        }
    }
    

  • 2
    O

    Thank you~ This solution is truely fast.

    Here I cleaned up some redundant codes:

        public class TrieNode {
            TrieNode[] next = new TrieNode[2];
            
            public TrieNode goTo(int bit) {
                if (next[bit] == null)
                    next[bit] = new TrieNode();
                return next[bit];
            }
        }
        
        public int findMaximumXOR(int[] nums) {
            int maxans = 0;
            TrieNode root = new TrieNode();
            
            for (int n : nums) {
                int maxTmp = 0;
                TrieNode i = root, j = root;
                
                for (int k = 30; k >= 0; k--) {
                    int bit = (n >> k) & 1;
                    i = i.goTo(bit);
                    if (j != null) {
                        if (j.next[1 ^ bit] != null) { 
                            j = j.next[1 ^ bit]; // i, j better go along opposite path in trie tree.
                            maxTmp |= 1 << k;
                        } else
                            j = j.next[bit]; // i, j go same direction -> no maxTmp increase. 
                    }
                }
                
                maxans = Math.max(maxans, maxTmp);
            }
            return maxans;
        }
    

  • 0
    C

    @ofLucas when j becomes null, can we break on the inner for loop?


  • 0

    @ofLucas Nicely done. Although I do not advocate using array as instance variable for node class in this situation. Your code costs twice as much time OP's approach according to my recent submissions.

    This trie solution also used array instance variable and suffered from severe speed issues. I am not very adamant about this assertion but I think it might be the case that array instance variable does introduce overhead. Otherwise I do not see how your code is inferior to OP's.


Log in to reply
 

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