Coding Interview PatternsMaximum XOR of Two Numbers in an Array
MediumTrie
Maximum XOR of Two Numbers in an Array
Explanation & Solution
Description
Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.
You must solve this in O(n) time using a trie (bitwise trie).
Input:nums = [3,10,5,25,2,8]
0
3
1
10
2
5
3
25
4
2
5
8
Output: 28
Explanation: The maximum XOR is 5 XOR 25 = 28.
Constraints
1 <= nums.length <= 2 * 10^50 <= nums[i] <= 2^31 - 1
Approach
Trie pattern
1. Build a Bitwise Trie
- Create a binary trie where each node has two children:
0and1 - Each number is represented as a 32-bit binary string and inserted bit by bit from the most significant bit to the least significant bit
2. Insert the First Number
- Insert
nums[0]into the trie to initialize it - This gives us a baseline to compare against
3. Query and Insert Remaining Numbers
- For each subsequent number
nums[i]: - Query the trie to find the number already inserted that maximizes XOR with
nums[i] - At each bit position, try to go in the opposite direction (toggled bit) to maximize XOR
- If the opposite branch exists, take it and set that XOR bit to
1 - Otherwise, follow the same branch and set that XOR bit to
0 - Insert
nums[i]into the trie after querying
4. Track Maximum
- Keep a running maximum of all XOR results found during the queries
- Return the maximum XOR value
Key Insight
- By greedily choosing the opposite bit at each level of the trie (from MSB to LSB), we maximize the XOR value bit by bit
- Each insert and query takes O(32) = O(1) time, making the overall algorithm O(n) time and O(n) space
Visualization
Input:
[3, 10, 5, 25, 2, 8]
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps