How do you solve Maximum XOR of Two Numbers in an Array on LeetCode?

Maximum XOR of Two Numbers in an Array (LeetCode #421) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: XOR operation is maximized when bits differ, so we want to find pairs with differing bits.

What is the brute force solution for Maximum XOR of Two Numbers in an Array?

The brute force approach for Maximum XOR of Two Numbers in an Array is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking every possible pair of numbers in the array and calculating their XOR. This is straightforward but inefficient for large arrays. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Maximum XOR of Two Numbers in an Array?

Maximum XOR of Two Numbers in an Array uses the following concepts: Array, Hash Table, Bit Manipulation, Trie. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Maximum XOR of Two Numbers in an Array?

Start with the brute force approach to show your thought process, then optimize. Explain your reasoning clearly when transitioning to the optimal solution. Practice building and using a Trie, as it’s a common data structure in bit manipulation problems.

What are common mistakes when solving Maximum XOR of Two Numbers in an Array?

Not considering all pairs correctly in the brute force approach. Failing to understand how to construct and traverse a Trie.

#421

Maximum XOR of Two Numbers in an Array

Medium

ArrayHash TableBit ManipulationTrieHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a Trie (prefix tree) to efficiently store and query the binary representations of the numbers. This allows us to find the maximum XOR in linear time by leveraging the properties of binary numbers.

⚙️

Algorithm

3 steps

1Step 1: Create a Trie to store the binary representations of the numbers.
2Step 2: For each number, insert its binary representation into the Trie.
3Step 3: For each number, traverse the Trie to find the number that gives the maximum XOR with it, updating the maximum result accordingly.

solution.py38 lines

1class TrieNode:
2    def __init__(self):
3        self.children = {}
4
5class Trie:
6    def __init__(self):
7        self.root = TrieNode()
8
9    def insert(self, num):
10        node = self.root
11        for i in range(31, -1, -1):
12            bit = (num >> i) & 1
13            if bit not in node.children:
14                node.children[bit] = TrieNode()
15            node = node.children[bit]
16
17    def find_max_xor(self, num):
18        node = self.root
19        max_xor = 0
20        for i in range(31, -1, -1):
21            bit = (num >> i) & 1
22            toggled_bit = 1 - bit
23            if toggled_bit in node.children:
24                max_xor |= (1 << i)
25                node = node.children[toggled_bit]
26            else:
27                node = node.children[bit]
28        return max_xor
29
30class Solution:
31    def findMaximumXOR(self, nums):
32        trie = Trie()
33        for num in nums:
34            trie.insert(num)
35        max_result = 0
36        for num in nums:
37            max_result = max(max_result, trie.find_max_xor(num))
38        return max_result

ℹ

Complexity note: The time complexity is O(n) because we process each number in the array once to insert it into the Trie and once to find the maximum XOR. The space complexity is O(n) due to the storage of the Trie nodes.

1XOR operation is maximized when bits differ, so we want to find pairs with differing bits.
2Using a Trie allows us to efficiently explore possible differing bits for maximum XOR.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.