Maximum XOR of Two Numbers in an Array - Solution & Explanation
Problem Statement
Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.
Example 1:
Input: nums = [3,10,5,25,2,8] Output: 28 Explanation: The maximum result is 5 XOR 25 = 28.
Example 2:
Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70] Output: 127
Constraints:
1 <= nums.length <= 2 * 1050 <= nums[i] <= 231 - 1
Approach Overview
Problem Overview: Given an integer array nums, you need to find two numbers whose XOR value is the largest possible. The challenge is identifying the pair that maximizes the XOR operation without checking every combination when the array becomes large.
Approach 1: Brute Force Pair Comparison (O(n²) time, O(1) space)
The most direct strategy checks every possible pair in the array. Iterate through the array using two nested loops and compute nums[i] ^ nums[j] for each pair. Track the maximum value seen so far and return it after scanning all combinations. This method uses basic array traversal and bit manipulation operations.
The logic is easy to implement and useful for validating correctness on small datasets. However, the time complexity grows quickly because every element is compared with every other element. With n numbers, the algorithm performs roughly n*(n-1)/2 XOR operations, making it impractical for large inputs.
Approach 2: Trie-Based Bit Optimization (O(n * W) time, O(n * W) space)
A more efficient solution builds a binary Trie based on the bit representation of each number. Each level of the Trie represents a bit position (usually 31 down to 0 for 32‑bit integers). While inserting numbers, you store paths for 0 and 1 bits. To maximize XOR, traverse the Trie preferring the opposite bit at each level because XOR becomes 1 when bits differ.
For every number in the array, walk the Trie from the most significant bit to the least significant bit. If the current bit is 0, try moving to the 1 branch; if the bit is 1, try moving to the 0 branch. This greedy decision maximizes the resulting XOR value bit by bit. Each insertion and query touches at most W bits, where W is the integer bit length (typically 32).
The Trie structure allows you to efficiently search for the best complementary number already inserted. Instead of comparing against all elements, you narrow the search using bit decisions. The result is near-linear performance relative to the input size.
Recommended for interviews: Interviewers expect the Trie-based approach because it demonstrates strong understanding of bitwise operations and optimized search structures. Starting with the brute force approach shows you understand the problem baseline. Transitioning to the Trie solution shows algorithmic maturity and familiarity with advanced bitwise greedy strategies used in many XOR-related problems.
Approach 1: Brute Force Approach
This approach involves iterating over all possible pairs of numbers in the array and calculating their XOR. We keep track of the maximum XOR value encountered during these iterations.
Though straightforward, this method is not efficient for large arrays, as it involves checking each pair of numbers.
The function findMaximumXOR takes an integer array and its size as arguments. It iterates over all pairs of elements in the array, calculating the XOR for each pair and updating the maximum XOR found so far. Finally, it returns the maximum XOR value.
Complexity
Time Complexity: O(n^2), where n is the number of elements in the array, because it checks every pair.
Space Complexity: O(1), as it uses only a constant amount of space.
Approach 2: Trie-Based Approach
This approach makes use of a Trie data structure to efficiently maximize the XOR computation. By examining the binary representation of numbers, we can leverage the Trie to only explore branches that potentially maximize the XOR result.
The Trie helps in finding complementary patterns (bits) efficiently by using bit manipulation and path traversal.
This solution constructs a Trie to store the binary representation of each number. As each number is inserted into the Trie, we simultaneously seek to maximize the XOR by traversing potentially complementing paths (opposite bits in Trie nodes).
Complexity
Time Complexity: O(n * W), where n is the number of elements and W is the number of bits in the maximum number.
Space Complexity: O(n * W), for storing the Trie.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2), where n is the number of elements in the array, because it checks every pair. |
| Trie-Based Approach | Time Complexity: O(n * W), where n is the number of elements and W is the number of bits in the maximum number. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Comparison | O(n²) | O(1) | Small arrays or quick baseline solution to verify correctness |
| Trie-Based Bit Optimization | O(n * W) ≈ O(n) | O(n * W) | Large arrays where near-linear performance is required |
Video Solution
maximum xor of two numbers in an array leetcode | leetcode 421 | bitwise solution • Naresh Gupta • 26,529 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum XOR of Two Numbers in an Array easy or hard?
How to solve Maximum XOR of Two Numbers in an Array in O(n)?
Maximum XOR of Two Numbers in an Array Python or Java solution?
What is the best approach for Maximum XOR of Two Numbers in an Array?
Is Maximum XOR of Two Numbers in an Array asked at Google Amazon Meta?
What data structure is used in Maximum XOR of Two Numbers in an Array?
What is the time complexity of Maximum XOR of Two Numbers in an Array?
Ready to solve this problem?
Practice Maximum XOR of Two Numbers in an Array with our built-in code editor and test cases.
Practice on FleetCode