LeetCode 421 Maximum XOR of Two Numbers in an Array(Med, Java, O(n))
Anni Huang
Problem Description
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 * 10^50 <= nums[i] <= 2^31 - 1
Key Insight: To maximize XOR, we need bits to be as different as possible, especially in higher-order positions since they contribute exponentially more value (2³¹ > sum of all lower bits).
Algorithm Walkthrough
Bit-by-Bit Greedy Construction with XOR Property Verification
This solution builds the maximum XOR result one bit at a time from most significant bit (MSB) to least significant bit (LSB), using mathematical XOR properties to verify if each bit can be set.
Step 1: Find the Highest Significant Bit
int max = 0;
for(var num: nums) max = Math.max(max, num);
if(max == 0) return 0;
int mask = 0x40000000; // Start from bit 30
while((mask & max) == 0) mask >>= 1;
Purpose: Optimize by skipping irrelevant high-order zero bits.
- Find the maximum number to determine the highest bit that matters
- Start checking from bit 30 and shift right until we find the first significant bit
- Example: If max = 25 (11001₂), we start from bit 4 instead of bit 30
Step 2: Greedy Bit-by-Bit Construction
int ret = 0; // Final result
int masks = 0; // Accumulates processed bit positions
while(mask != 0) {
masks |= mask; // Include current bit in mask
if(check(nums, masks, ret | mask)) // Can we set this bit?
ret |= mask; // Yes! Set this bit to 1
mask >>= 1; // Move to next lower bit
}
Core Logic:
masks: Tracks which bit positions we've already processedret | mask: Candidate result if we set current bit to 1check(): Verifies if the candidate is achievable- Greedy choice: Set bit to 1 if possible, otherwise leave as 0
Step 3: XOR Property Verification
private boolean check(int[] nums, int masks, int ans) {
Set<Integer> vis = HashSet.newHashSet(nums.length);
for(int num : nums) {
num &= masks; // Keep only processed bits
if(vis.contains(num ^ ans)) // XOR property: a⊕b=c ↔ a⊕c=b
return true;
vis.add(num);
}
return false;
}
XOR Property Used: If a ⊕ b = target, then a ⊕ target = b
Logic:
- For each masked number
a, check if the required partnerb = a ⊕ targetexists - If such a pair exists, we can achieve the target XOR value
num &= masksensures we only consider bits we've decided so far
Detailed Example:
Input: nums = [3, 10, 5, 25]
Binary representations:
3 = 00011₂
10 = 01010₂
5 = 00101₂
25 = 11001₂
Step 1: Find highest bit
- max = 25, start from bit 30, find first significant bit at position 4
Step 2: Process each bit
Iteration 1 - Bit 4:
mask = 16 (10000₂), masks = 16, candidate = 16
check([3,10,5,25], 16, 16):
Masked: [0,0,0,16]
For 0: check if (0⊕16)=16 exists → Yes! (25 masked = 16)
Return true → ret = 16
Iteration 2 - Bit 3:
mask = 8 (01000₂), masks = 24, candidate = 24
check([3,10,5,25], 24, 24):
Masked: [0,8,0,24]
For 0: check if (0⊕24)=24 exists → Yes!
Return true → ret = 24
Iteration 3 - Bit 2:
mask = 4 (00100₂), masks = 28, candidate = 28
check([3,10,5,25], 28, 28):
Masked: [0,8,4,24]
For 4: check if (4⊕28)=24 exists → Yes!
Return true → ret = 28
Iterations 4-5 - Bits 1,0:
- Both return false, so bits remain 0
Final Result: 28
Complexity Analysis
Time Complexity: O(32n) = O(n)
- At most 32 iterations (one per bit position in a 32-bit integer)
- Each iteration processes all n numbers once
- HashSet operations (contains, add) are O(1) average case
- Total: 32 × n × O(1) = O(n)
Space Complexity: O(n)
- HashSet in
check()method stores at most n masked numbers - All other variables use constant space
- No additional data structures or recursion stack needed
Key Optimizations:
- Skip high-order zero bits by finding the maximum value first
- Process only relevant bit positions
- Use bit masking to reduce problem scope at each iteration
Full Solution (Java)
class Solution {
public int findMaximumXOR(int[] nums) {
// Step 1: Find maximum value to determine highest significant bit
int max = 0;
for(var num: nums)
max = Math.max(max, num);
if(max == 0) return 0;
// Step 2: Find the highest bit position that matters
int mask = 0x40000000; // Start from bit 30 (2^30)
while((mask & max) == 0) mask >>= 1;
// Step 3: Build result bit by bit from MSB to LSB
int ret = 0; // Final result
int masks = 0; // Accumulator for processed bit positions
while(mask != 0) {
masks |= mask; // Include current bit
if(check(nums, masks, ret | mask)) // Can we set this bit?
ret |= mask; // Yes! Set bit to 1
mask >>= 1; // Move to next bit
}
return ret;
}
/**
* Check if target XOR value is achievable using XOR property:
* If a ⊕ b = target, then a ⊕ target = b
*
* @param nums Original array
* @param masks Bit mask for positions processed so far
* @param ans Target XOR value to verify
* @return true if target is achievable, false otherwise
*/
private boolean check(int[] nums, int masks, int ans) {
Set<Integer> vis = HashSet.newHashSet(nums.length);
for(int num : nums) {
num &= masks; // Keep only relevant bits
if(vis.contains(num ^ ans)) // Check if partner exists
return true;
vis.add(num);
}
return false;
}
}
Key Algorithm Properties:
- Greedy Approach: Makes locally optimal choices (set bit to 1 when possible)
- Mathematical Foundation: Leverages XOR properties instead of brute force
- Optimal Complexity: Achieves O(n) time without building complex data structures
- Bit-level Optimization: Processes only significant bit positions
- Space Efficient: Uses temporary HashSet rather than persistent data structures
This solution elegantly demonstrates how mathematical properties can transform a seemingly quadratic problem into an optimal linear solution.
Subscribe to my newsletter
Read articles from Anni Huang directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by
Anni Huang
Anni Huang
I am Anni HUANG, a software engineer with 3 years of experience in IDE development and Chatbot.