Java Trie Concise 25 Lines with Comments
This question is a little difficult for a medium... Took me a bit of time to figure it out. \n\nAccording to the input constraint, we will defintely want an som
This question is a little difficult for a medium... Took me a bit of time to figure it out. \n\nAccording to the input constraint, we will defintely want an somewhat linear time solution. Trie is a good choice here because we can decompose each number down to their binary representation, so when we are looking for a max path for any given number, we can immediately discard a large portion of it instead of just one by one. \n\nOur strategy would be to\n- Find the max depth\n\n- Pad 0 in front to any number with lower depth (e.g. `if max depth = 6, then 3 = 0b000011`)\n\n- Store the left most digit directly under Trie root node, right most digit should be Trie leaf node. \n\n- Always greedily choose the opposite digit (1 -> 0 or 0 -> 1) if that path exists. It works because we are going from largest digit to smallest.\n\nThe idea above translates into the code below\nSolution **Trie**:\n\n```\nclass Solution {\n    public int findMaximumXOR(int[] nums) {\n        Trie root = new Trie();\n        int ans = 0, max = 0, depth = 0; //depth of trie \n        for (int n : nums) max = Math.max(n, max);\n        for (;max > 0; max >>= 1) depth++; //depth = max num binary string length\n\n        for (int n : nums){\n            int sum = 0;\n            Trie cur = root, tmp = cur; //cur for adding n into Trie, tmp for finding the max path\n            for (int i = depth - 1; i >= 0; i--){\n                sum <<= 1;\n                int d = (n & (1 << i)) > 0? 1 : 0; //start checking from left end. 1 if positive, 0 if 0.\n                if (cur.nodes[d] == null) cur.nodes[d] = new Trie();\n                if (tmp.nodes[1 - d] != null) sum++; //always choose the opposite path if they exist\n                cur = cur.nodes[d];\n                tmp = sum % 2 == 0? tmp.nodes[d] : tmp.nodes[1 - d];\n            }\n\n            ans = Math.max(sum, ans);\n        }\n\n        return ans;\n    }\n\n    private class Trie{\n        Trie[] nodes;\n        Trie(){\n            nodes = new Trie[2];\n        }\n    }\n}\n```
['Trie', 'Java']