LeetCode 421 Maximum XOR of Two Numbers in an Array(Med, Java, O(n))

Problem Description

• LeetCode 421 Maximum XOR of Two Numbers in an Array

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^5
• 0 <= 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 processed
• ret | mask: Candidate result if we set current bit to 1
• check(): 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 partner b = a ⊕ target exists
• If such a pair exists, we can achieve the target XOR value
• num &= masks ensures 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.