Maximum XOR of Two Numbers in an Array: Bitwise Trie Approach

LeetCode Maximum XOR of Two Numbers in an Array (Problem 421) asks: given an integer array nums, return the maximum result of nums[i] XOR nums[j] where 0 <= i <= j < n.

For example, given nums = [3, 10, 5, 25, 2, 8], the answer is 28 because 5 XOR 25 = 28. Brute-forcing every pair takes O(n^2) time. You can do much better by thinking about XOR one bit at a time.

Why this problem matters

XOR maximization combines two skills that appear across many interview problems: bitwise thinking and greedy construction. You need to understand how XOR works at the bit level, and you need to build the answer from the most significant bit downward, locking in each bit greedily.

This problem also introduces the idea of using a trie on binary representations of integers. That same technique shows up in problems involving XOR queries, subarray XOR problems, and networking (longest prefix matching). If you can solve this problem cleanly, you have the tools for an entire category of bitwise trie problems.

The approach

The hash set approach works bit by bit, starting from the most significant bit (MSB). At each bit position, you ask: "Can I set this bit to 1 in the answer?"

The key insight relies on a property of XOR: if a ^ b = c, then a ^ c = b. So if you want to check whether some pair of numbers in the array has a certain XOR prefix, you can put all the prefixes into a set and check whether, for any prefix p in the set, p ^ candidate is also in the set.

Here is how it works:

1. Start with max_xor = 0
2. For each bit position from the MSB down to bit 0:
   • Set the candidate to max_xor | (1 << bit). This is the best possible answer if you can set this bit.
   • Extract the prefix of every number down to this bit position. Put all prefixes into a set.
   • For each prefix p, check if p ^ candidate exists in the set. If yes, two numbers produce this candidate prefix when XOR-ed.
   • If found, update max_xor = candidate. Otherwise, leave the bit unset.

def find_maximum_xor(nums: list[int]) -> int:
    max_xor = 0
    mask = 0
    for bit in range(31, -1, -1):
        mask |= 1 << bit
        prefixes = {num & mask for num in nums}
        candidate = max_xor | (1 << bit)
        for p in prefixes:
            if p ^ candidate in prefixes:
                max_xor = candidate
                break
    return max_xor

Step-by-step walkthrough

Let's trace through nums = [3, 10, 5, 25, 2, 8]. In binary (5 bits): 3 is 00011, 10 is 01010, 5 is 00101, 25 is 11001, 2 is 00010, 8 is 01000. The maximum XOR is 5 ^ 25 = 28 (11100).

We build the answer starting from bit 4 (the MSB for these numbers) and work down.

At each step, the algorithm either locks in the bit (when a valid pair exists) or leaves it as 0. The final answer is 11100 in binary, which is 28. The pair that achieves this is 5 and 25.

Trie alternative

You can also solve this with a bitwise trie. Insert every number into a trie where each level corresponds to a bit position (MSB first, using 0 and 1 as children). Then for each number, walk the trie greedily: at each level, try to go the opposite direction of the current bit. Going opposite maximizes the XOR at that position.

def find_maximum_xor_trie(nums: list[int]) -> int:
    root = {}
    for num in nums:
        node = root
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            if bit not in node:
                node[bit] = {}
            node = node[bit]

    max_xor = 0
    for num in nums:
        node = root
        curr_xor = 0
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            opposite = 1 - bit
            if opposite in node:
                curr_xor |= 1 << i
                node = node[opposite]
            else:
                node = node[bit]
        max_xor = max(max_xor, curr_xor)
    return max_xor

Both approaches run in O(32n) time, which simplifies to O(n). The hash set version is shorter and easier to code under pressure. The trie version makes the greedy logic more explicit and extends naturally to streaming or query-based variants.

Complexity analysis

Each of the 32 bit positions requires one pass through the array. The prefix set (or trie) holds at most n entries. Since 32 is a constant, the overall complexity is linear.

Edge cases to watch for

• All zeros. If every element is 0, the max XOR is 0. The algorithm handles this naturally since no candidate bit can ever be set.
• Two elements. The only pair is nums[0] ^ nums[1]. The algorithm still works correctly, just with a set of size 2 at each level.
• Duplicate elements. a ^ a = 0. If the array has duplicates, the max XOR might still come from a different pair. Duplicates do not break the set-based approach since the set deduplicates prefixes automatically.
• Single element. The problem states i <= j, so nums[0] ^ nums[0] = 0 is the only option. Return 0.
• Large values. The loop runs from bit 31 down to 0, covering all 32-bit integers. No overflow risk in Python.

The building blocks

This problem decomposes into two reusable building blocks that CodeBricks drills independently:

1. Bitwise prefix extraction

The idea of examining numbers one bit at a time from the MSB, building up prefixes with a mask. This same pattern appears in Bitwise AND of Numbers Range (finding the common prefix) and in Sum of Two Integers (bit-level addition). Whenever a problem involves optimizing or comparing numbers at the bit level, extracting prefixes with num & mask is the go-to technique.

2. XOR complement lookup

Using the identity a ^ b = c implies a ^ c = b to turn a pair search into a set lookup. This is the same structural trick as Two Sum, where you check whether the complement of each element exists in a hash map. In Two Sum you look for target - num. Here you look for prefix ^ candidate. The pattern is identical: reduce an O(n^2) pair search to O(n) with a hash set.

Once you can fluently apply prefix extraction and complement lookup, this problem becomes a direct combination of the two. You stop thinking about XOR mechanics and start seeing the bit-by-bit greedy construction immediately.

From understanding to recall

The hash set XOR approach is elegant once you see it. But reproducing it from memory under time pressure is a different challenge. You need to remember the mask accumulation, the candidate construction, and the XOR complement check. Each detail is simple on its own, but getting them all right in sequence takes practice.

Spaced repetition builds that recall. You write the bit loop from scratch today, again in three days, then a week later. Each repetition strengthens the connection between "maximize XOR" and "bit-by-bit greedy with set lookup." After a few reps, the code flows out automatically when you recognize the pattern.

Related posts

• Implement Trie - The foundational trie data structure. Understanding how tries work with character-by-character traversal directly prepares you for the bitwise trie variant used here.
• Single Number - Uses XOR cancellation (a ^ a = 0) to find the lone unpaired element. A simpler application of XOR properties that builds intuition for this problem.
• Sum of Two Integers - Another bit manipulation problem that works bit by bit. Uses XOR for partial sums and AND for carries, exercising the same bit-level thinking needed here.