Maximum XOR of Two Numbers in an Array — Binary Trie

Problem Statement

LeetCode 421 — Maximum XOR of Two Numbers in an Array | Difficulty: Medium

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

Constraints:

1 <= nums.length <= 2 * 10^5
0 <= nums[i] <= 2^31 - 1

Examples:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: 5 XOR 25 = 28 is the maximum.

Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127

Input: nums = [0]
Output: 0

Why This Problem Matters

This is the introduction to the binary trie (also called a bit-trie or XOR trie) — a structure where each level represents one bit of the integer. Binary tries appear in IP-routing tables, network packet classifiers, persistent data structures, and competitive programming. Once you internalise the pattern, problems like LC 1707 (Maximum XOR With an Element From Array) and LC 1938 (Maximum Genetic Difference Query) become straightforward variations.

The naive O(N^2) double loop times out at N = 2 times 10^5 (4 times 10^10 operations). The binary trie reduces this to O(N times 32) — a six-orders-of-magnitude speedup. Amazon, Google, and competitive programming firms ask this as a litmus test for whether you can think bitwise.

The Core Insight

XOR is maximised by opposing bits: at every bit position, we want the two operands to differ (1 XOR 0 = 1). Working from the most significant bit (MSB) downward, the greedy strategy is:

Insert every number into a binary trie keyed on bit 30 down to bit 0 (32-bit ints; bit 31 is sign so we skip for non-negative inputs).
For each number, walk the trie greedily: at every bit, try to take the opposite child if it exists; otherwise take the same-bit child.
The path you walk gives you the partner that maximises XOR with the current number.

This greedy works because higher bits dominate: setting bit 30 in the XOR is worth 2^30, more than every lower bit combined. So it is always correct to prioritise opposite bits at the top.

Visual Dry Run

Take nums = [3, 10, 5, 25] in 5-bit form:

Build the trie (root → bit 4 → ... → bit 0). After inserting all four numbers, query for 5 = 00101:

Bit 4 = 0 → try child 1 (opposite). 1-child exists (25 has bit4=1). Take it.
Bit 3 = 0 → try child 1. Below 25-path bit3=1 exists. Take it.
Bit 2 = 1 → try child 0. Below 25-path bit2=0 exists. Take it.
Bit 1 = 0 → try child 1. Yes (25 bit1=0... actually 0). Take 0 instead.
Bit 0 = 1 → try child 0. 25 bit0=1, no 0-sibling. Take 1.

Reconstructing — the trie steered us to 25, giving 5 XOR 25 = 28. The greedy path is bit-by-bit; at every level we took the opposite child whenever possible.

Trie skeleton (only top bits shown):
        root
       /    \
      0      1
     /        \
    0          1
   / \          \
  0   1          0
  ...            ...
  numbers        (25 lives here)

Solution (Optimal) — Binary Trie Greedy

Python

class TrieNode:
    __slots__ = ("children",)
    def __init__(self):
        self.children = [None, None]
 
class Solution:
    def findMaximumXOR(self, nums: list[int]) -> int:
        BITS = 31  # bits 30..0 cover up to 2^31 - 1
        root = TrieNode()
 
        def insert(num: int) -> None:
            node = root
            for i in range(BITS - 1, -1, -1):
                b = (num >> i) & 1
                if node.children[b] is None:
                    node.children[b] = TrieNode()
                node = node.children[b]
 
        def max_xor(num: int) -> int:
            node = root
            xor_val = 0
            for i in range(BITS - 1, -1, -1):
                b = (num >> i) & 1
                opposite = 1 - b
                if node.children[opposite] is not None:
                    xor_val |= (1 << i)        # bit contributes
                    node = node.children[opposite]
                else:
                    node = node.children[b]
            return xor_val
 
        # Insert first, then query — single pass also works
        for n in nums:
            insert(n)
 
        return max(max_xor(n) for n in nums)

JavaScript

var findMaximumXOR = function (nums) {
  const BITS = 31;
  const root = [null, null];
 
  const insert = (num) => {
    let node = root;
    for (let i = BITS - 1; i >= 0; i--) {
      const b = (num >> i) & 1;
      if (!node[b]) node[b] = [null, null];
      node = node[b];
    }
  };
 
  const maxXor = (num) => {
    let node = root, ans = 0;
    for (let i = BITS - 1; i >= 0; i--) {
      const b = (num >> i) & 1;
      const opp = 1 ^ b;
      if (node[opp]) {
        ans |= (1 << i);
        node = node[opp];
      } else {
        node = node[b];
      }
    }
    return ans;
  };
 
  for (const n of nums) insert(n);
  let best = 0;
  for (const n of nums) best = Math.max(best, maxXor(n));
  return best;
};

Complexity

Time: O(N times 32) for insert + O(N times 32) for query = O(N) effectively.
Space: O(N times 32) for the trie nodes.

Common Mistakes

Iterating bits from LSB to MSB — XOR maximisation requires MSB first because higher bits dominate.
Using all 32 bits including sign — for non-negative inputs, bit 31 is always 0; iterating it wastes time but does not break correctness.
Inserting into the trie inside the query loop — fine, but you must not query before any inserts have happened (first iteration would crash on None children).
Returning XOR of a number with itself — happens if you only have one element. The problem allows i == j per the modern statement (XOR with self = 0).
Forgetting that JavaScript bitwise ops are 32-bit signed — for inputs near 2^31 you may see weird negatives; use >>> 0 to coerce to unsigned, or stick to BITS = 31.
Building a hash-based trie instead of a 2-element array — works but slower due to hashing overhead.

Interview Tips

Open with the naive O(N^2) approach and explicitly compute its cost — interviewers love seeing that you understand the bottleneck.
Describe the bit-trie verbally before coding: "each level is one bit, left child is 0, right child is 1."
Justify the greedy with the dominance argument: 2^30 is more than the sum of all lower bits.
Mention that the constant 31 (or 32) makes this effectively linear.
A subtle alternative is the prefix hash-set trick (also O(N times 32)) but the trie generalises better to follow-up problems.

Follow-up Questions

Maximum XOR with a constraint nums[j] <= x? That is LC 1707 — augment the trie with min-values per node and query offline sorted by x.
What if numbers can be negative? Use BITS = 32 and treat numbers as unsigned bit patterns.
Maximum XOR pair across two arrays? Insert one array into the trie, query with the other. Same O((N+M) times 32) cost.
Find the actual pair, not just the value? Store the index at each leaf; return both during the max-xor walk.
Streaming version? Maintain the trie incrementally — inserts are O(32) so it works online.

Key Takeaways

The binary trie turns O(N^2) XOR problems into O(N times 32).
Greedy MSB-first works because higher bits dominate — set bit 30 over any combination of lower bits.
Trie children are just [None, None] — no need for objects or hashmaps.
The pattern generalises: insert N numbers, query each for "best partner under constraint X".
This is the gateway to LC 1707, LC 1938, and competitive XOR queries — master it first.
Always go MSB to LSB and prefer the opposite child whenever it exists.

Problem Statement#

Why This Problem Matters#

The Core Insight#

Visual Dry Run#

Solution (Optimal) — Binary Trie Greedy#

Python#

JavaScript#

Complexity#

Common Mistakes#

Interview Tips#

Follow-up Questions#

Key Takeaways#

Related reading