Maximum XOR of Two Numbers in an Array (Trie)

Share

Given array nums, find maximum XOR of any two elements. Use a binary Trie for O(N) solution.

Example 1
Input: [3,10,5,25,2,8] → Output: 28 (5 XOR 25)
Example 2
Input: [0,0] → Output: 0

Solution Approach

Insert all numbers into a binary Trie. For each number, greedily try to go the opposite bit path to maximize XOR.

  • For each num, insert 32-bit representation into Trie (MSB first).
  • For each num, query Trie: at each bit, prefer going to opposite bit.
  • XOR accumulates the best bits.
Java
class Solution {
    int[][] trie = new int[32 * 30001][2];
    int node = 1;

    public int findMaximumXOR(int[] nums) {
        for (int num : nums) insert(num);
        int max = 0;
        for (int num : nums) max = Math.max(max, query(num));
        return max;
    }
    private void insert(int num) {
        int cur = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (trie[cur][bit] == 0) trie[cur][bit] = node++;
            cur = trie[cur][bit];
        }
    }
    private int query(int num) {
        int cur = 0, xor = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1, want = 1-bit;
            if (trie[cur][want] != 0) { xor |= (1<<i); cur = trie[cur][want]; }
            else cur = trie[cur][bit];
        }
        return xor;
    }
}
  • Time Complexity: O(N * 32)
  • Space Complexity: O(N * 32)