LeetCode 421 Maximum XOR of Two Numbers - Example and Complexity Analysis

Trace simplified: nums = [3, 5] (binary: 011, 101).

Insert 3 (011): root → 0 → 1 → 1.

Query max XOR for 5 (101):

• At root, take the opposite of $1$ (take $0$). Because $0$ exists, take it. XOR bit becomes $1$.
• At level 2, want opposite of 0 (want 1). 1 exists! Take it. XOR bit = 1.
• At level 3, want opposite of 1 (want 0). Only 1 exists. Take 1. XOR bit = 0.
• XOR = 110 = 6.

Insert 5. Done.

Max XOR: $6$ (which is 3 XOR 5 = 011 XOR 101 = 110).

$O(n \cdot L)$ time where $L$ is bit length (32). $O(n \cdot L)$ space for Trie.