LeetCode Solutions Blog

Maximum XOR of Two Numbers in an Array

Number: 421

Difficulty: Medium

Paid? No

Problem Description

Given an integer array nums, return the maximum result of nums[i] XOR nums[j] for any pair of indices such that 0 <= i < j < n. In other words, find two numbers in the array such that their XOR is as large as possible.

Key Insights

The XOR operation is bitwise, so the maximum result is primarily influenced by the higher-order bits.
A Trie (prefix tree) can be used to store the binary representation of the numbers enabling efficient bit-by-bit comparison.
By inserting numbers into the Trie and then checking for the complement bit (i.e., if bit is 0 look for 1 and vice versa), one can greedily maximize the XOR at each bit-level.
The solution runs in O(n * L) time, where L is the number of bits (typically 32 for standard integers).

Space and Time Complexity

Time Complexity: O(n * L) where L = 32, so essentially O(n).
Space Complexity: O(n * L) in the worst-case scenario for storing nodes in the Trie.

Solution

We use a Trie data structure to store the binary representations of the numbers in the array. For each number, we traverse the Trie trying to take the opposite branch (complement bit) at each level to maximize the resulting XOR. We then update the maximum XOR seen so far. This approach efficiently checks for the best possible XOR pair for every element in nums.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java with detailed line-by-line comments.

# Define the node for Trie
class TrieNode:
    def __init__(self):
        self.children = {}  # Dictionary to hold child nodes for bits 0 and 1

# Define the Trie data structure
class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    # Insert a number's binary representation into the Trie
    def insert(self, num):
        node = self.root
        # Consider 32-bit integers (from bit 31 to 0)
        for i in range(31, -1, -1):
            bit = (num >> i) & 1  # Extract the i-th bit
            if bit not in node.children:
                node.children[bit] = TrieNode()
            node = node.children[bit]
    
    # Query for the maximum XOR partner for the given number
    def query(self, num):
        node = self.root
        xor_sum = 0
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            toggled = 1 - bit  # Complement of the current bit
            if toggled in node.children:
                xor_sum |= (1 << i)  # Set the i-th bit in the result
                node = node.children[toggled]
            else:
                node = node.children.get(bit, node)
        return xor_sum

class Solution:
    def findMaximumXOR(self, nums):
        trie = Trie()
        max_xor = 0
        # Insert the first number to initialize the Trie
        trie.insert(nums[0])
        for num in nums[1:]:
            # For each number, query the best possible XOR companion
            current_xor = trie.query(num)
            max_xor = max(max_xor, current_xor)
            trie.insert(num)
        return max_xor

# Example usage:
# sol = Solution()
# print(sol.findMaximumXOR([3,10,5,25,2,8]))  # Expected output: 28