medium Maximum XOR of Two Numbers in an Array

Maximum XOR of Two Numbers in an Array

Problem. Given an array nums of non-negative integers, return the maximum value of nums[i] ^ nums[j] over all pairs (i may equal j, though the max never comes from a number XOR-ed with itself — that is 0). For nums = [3, 10, 5, 25] the answer is 28, from 5 ^ 25. (LeetCode 421.)

This is the module’s payoff page: it fuses two ideas — XOR (from the XOR deep-dive) and a binary trie — into a greedy that beats the obvious quadratic scan. The whole trick rests on one fact about XOR: 1 ^ 0 = 1 but 1 ^ 1 = 0 ^ 0 = 0. So to make a high bit of the XOR equal to 1, the two numbers must differ at that bit — and because a higher bit outweighs every lower bit combined, you should chase differences from the top down. That is a greedy, and a trie is the data structure that answers “does a number differing from me at this bit exist?” in O(1) per bit.

The naive baseline & its cost

Try every pair: two nested loops, compute nums[i] ^ nums[j], keep the max. Correct and five lines — but O(n2) time. LeetCode allows n up to 2 × 105, so n2 = 4 × 1010 — far too slow. We need to drop the n2.

The bit insight — greedy from the most significant bit

Fix the number of bits L (here L = 32 for a 32-bit int). Build the answer one bit at a time, from bit L−1 down to bit 0. At each bit you want the XOR to be 1 if possible, because setting a higher bit is worth more than anything you could gain in all the lower bits combined (2k > 2k−1 + … + 20). To make bit k of some pair’s XOR equal 1, you need two numbers whose bit k differs.

A binary trie makes this searchable. Insert every number as a root-to-leaf path of L bits, MSB first — child 0 or child 1 at each level. Then, for each number x, walk the trie from the root: at each bit prefer the child labelled with the opposite of x’s bit (that edge means “a stored number differs here” → this XOR bit can be 1). If that opposite child exists, take it and set the bit in the running answer; otherwise you are forced down the same-bit child and that XOR bit is 0. Do this for every x and keep the best. Because the number itself is in the trie, the forced branch always exists — no dead ends.

Traced example — nums = [3, 10, 5, 25]

Five bits suffice (25 = 11001):

All four are inserted into the trie. Now query with x = 5 (00101), walking MSB→LSB and preferring the opposite bit. “Available?” asks whether any stored number shares the prefix chosen so far and has the desired bit next:

The greedy locks onto partner 25 and reports 5 ^ 25 = 28 (00101 ^ 11001 = 11100). Querying the other numbers never beats it (e.g. x = 25 symmetrically finds 5 and also yields 28), so the global maximum is 28 — matching the brute-force check over all six pairs.

Java: bit-trie greedy

public class MaximumXor {
    static class TrieNode {
        TrieNode[] child = new TrieNode[2];   // child[0], child[1]
    }

    public int findMaximumXOR(int[] nums) {
        TrieNode root = new TrieNode();
        final int HIGH = 31;                  // bits 31..0 of a 32-bit int

        // Insert every number, most-significant bit first.
        for (int num : nums) {
            TrieNode node = root;
            for (int b = HIGH; b >= 0; b--) {
                int bit = (num >> b) & 1;
                if (node.child[bit] == null) node.child[bit] = new TrieNode();
                node = node.child[bit];
            }
        }

        int best = 0;
        // For each number, greedily prefer the opposite bit to maximize the XOR.
        for (int num : nums) {
            TrieNode node = root;
            int cur = 0;
            for (int b = HIGH; b >= 0; b--) {
                int bit  = (num >> b) & 1;
                int want = bit ^ 1;           // opposite bit -> XOR bit of 1
                if (node.child[want] != null) {
                    cur |= (1 << b);         // we can set this XOR bit
                    node = node.child[want];
                } else {
                    node = node.child[bit];   // forced: same bit -> XOR bit 0
                }
            }
            best = Math.max(best, cur);
        }
        return best;
    }

    public static void main(String[] args) {
        MaximumXor s = new MaximumXor();
        System.out.println(s.findMaximumXOR(new int[]{3, 10, 5, 25}));       // 28
        System.out.println(s.findMaximumXOR(new int[]{3, 10, 5, 25, 2, 8})); // 28
        System.out.println(s.findMaximumXOR(new int[]{0}));                  // 0
    }
}

Go: bit-trie greedy

package main

import "fmt"

type trieNode struct {
	child [2]*trieNode // child[0], child[1]
}

func findMaximumXOR(nums []int) int {
	root := &trieNode{}
	const high = 31 // bits 31..0 of a 32-bit value

	// Insert every number, most-significant bit first.
	for _, num := range nums {
		node := root
		for b := high; b >= 0; b-- {
			bit := (num >> b) & 1
			if node.child[bit] == nil {
				node.child[bit] = &trieNode{}
			}
			node = node.child[bit]
		}
	}

	best := 0
	for _, num := range nums {
		node := root
		cur := 0
		for b := high; b >= 0; b-- {
			bit := (num >> b) & 1
			want := bit ^ 1 // opposite bit -> XOR bit of 1
			if node.child[want] != nil {
				cur |= 1 << b // we can set this XOR bit
				node = node.child[want]
			} else {
				node = node.child[bit] // forced: same bit -> XOR bit 0
			}
		}
		if cur > best {
			best = cur
		}
	}
	return best
}

func main() {
	fmt.Println(findMaximumXOR([]int{3, 10, 5, 25}))       // 28
	fmt.Println(findMaximumXOR([]int{3, 10, 5, 25, 2, 8})) // 28
	fmt.Println(findMaximumXOR([]int{0}))                  // 0
}

Why the greedy is optimal (not just a heuristic)

An exchange argument. Suppose the true maximum XOR has its highest 1 at bit k. The greedy processes bits top-down, so it reaches bit k with the same prefix (all higher XOR bits were 0 for the optimum, and the greedy also could not have set them — no pair differs there, or it would have set an even higher bit). At bit k the optimum differs, so some stored number provides the opposite bit; the trie’s opposite child therefore exists and the greedy takes it, setting bit k. Any XOR with a 1 at bit k already exceeds every XOR whose top 1 is below k (place value 2k dominates the sum of all lower bits), so fixing the highest attainable bit first can never be a mistake. Induct down the remaining bits within the branch. The greedy’s result is thus ≥ the optimum, hence equal.

Complexity

• Time: inserting n numbers is n walks of L = 32 bits = O(n · L); querying is another O(n · L). With L = 32 fixed, that is O(32n) = O(n) — a full order below the naive O(n2).
• Space: the trie holds at most O(n · L) nodes (each number adds ≤ L new nodes) → O(32n). The naive scan is O(1) space — the trie buys speed with memory.

Judgment layer — when the trie is worth it

• Use the trie when n is large. That is the entire point: it converts O(n2) into O(32n). At n = 2 × 105 that is the difference between ~6 × 106 operations and 4 × 1010 — feasible vs. not.
• Do not build a trie for tiny n. For n up to a few hundred, O(n2) is trivially fast, and the brute-force double loop is five lines you cannot get wrong under pressure — no node allocations, no MSB indexing bugs, no O(32n) pointer memory. Clever is a liability when n2 already fits in microseconds.
• The named alternative — the hash-set prefix greedy. There is a second O(32n) solution with no explicit trie: build the answer bit by bit from the top; at each step guess the next answer bit is 1, put every number’s current prefix in a HashSet, and check whether two prefixes XOR to that guess (equivalently, prefix ^ guess is present). It matches the trie’s asymptotics with O(n) space and tighter code, but it re-hashes all prefixes on every one of the 32 bit-rounds and is less intuitive. Prefer the trie when you want the clearer “walk preferring the opposite bit” mental model, or when the problem grows into related trie territory — XOR with a value constraint, maximum XOR in a query range, or a persistent/offline variant. Prefer the hash-set version when you want the least code and do not anticipate those extensions.
• Interview move: state the O(n2) baseline, note it is fine for small n, then present the trie for scale and mention the hash-set greedy as the equivalent-complexity alternative. That sequence shows you optimize for the actual constraint rather than reaching for the fanciest structure reflexively.

Edge cases & traps

• Sign bit / negative inputs. The problem guarantees non-negative nums[i] ≤ 231−1, so bit 31 is always 0 for every number; the greedy never finds an opposite bit there, never sets bit 31 in cur, and the result stays non-negative. If inputs could be negative, setting bit 31 would make cur a negative int in Java and Math.max would misjudge — you would compare the XOR magnitudes as unsigned or restrict to the meaningful bit width.
• (num >> b) & 1 is safe for the sign bit. Java’s >> is arithmetic (sign-extending), but masking with & 1 keeps only the target bit, so reading bit b is correct regardless of sign. (Still, per the point above, guard the value of cur, not the bit reads.)
• Single-element / empty array. One element yields 0 (it can only XOR with itself). Guard an empty array if your constraints permit it (the loop leaves best = 0).
• Consistent bit width. Insertion and query must use the same HIGH. Mixing widths misaligns the trie paths and silently returns wrong answers.

Takeaways

• Max XOR is greedy from the MSB: a higher differing bit outweighs all lower bits, so chase differences top-down.
• A binary trie answers “is there a number differing from me at this bit?” in O(1) per bit → O(32n) overall, beating the O(n2) scan.
• The greedy is provably optimal via an exchange argument on the highest attainable bit — not a heuristic.
• Worth it for large n; for tiny n the double loop is simpler and just as fast. The hash-set prefix greedy is an equal-complexity alternative; the trie wins on clarity and extensibility.

Maximum-XOR (LeetCode 421) developed from the XOR place-value greedy and the binary-trie structure, with an exchange-argument optimality proof; all samples were compiled and run, and the answer cross-checked against brute force over all pairs.