LeetCode 421: Maximum XOR of Two Numbers in an Array

Problem Restatement

We are given an integer array nums.

Return the maximum value of:

nums[i] ^ nums[j]

where ^ means bitwise XOR.

The indices may be the same according to the source statement:

0 <= i <= j < n

Using the same element gives XOR value 0, so it never hurts the maximum when there are at least two useful values.

The source constraints are:

1 <= nums.length <= 2 * 10^5
0 <= nums[i] <= 2^31 - 1

The standard example is:

nums = [3, 10, 5, 25, 2, 8]

with answer:

28

because:

5 ^ 25 = 28

Input and Output

Example function shape:

def findMaximumXOR(nums: list[int]) -> int:
    ...

Examples

Example 1:

nums = [3, 10, 5, 25, 2, 8]

The answer is:

28

One best pair is:

5 ^ 25

In binary:

  00101
^ 11001
= 11100

11100 in decimal is:

28

Example 2:

nums = [14, 70, 53, 83, 49, 91, 36, 80, 92, 51, 66, 70]

The answer is:

127

First Thought: Try Every Pair

The direct approach is to test every pair:

nums[i] ^ nums[j]

and keep the largest value.

This is simple, but it takes:

O(n^2)

With n up to 2 * 10^5, this is too slow.

We need to use the bit structure of XOR.

Key Insight

XOR is maximized by making higher bits equal to 1.

A bit in a ^ b is 1 exactly when the two bits are different.

So we build the answer from the highest bit to the lowest bit.

At each bit position, we ask:

Can the maximum XOR have this bit set to 1 while keeping the higher bits we already chose?

If yes, we keep it.

If no, we leave it as 0.

Prefix Idea

Suppose we only care about the top bits seen so far.

For each number, keep its prefix up to the current bit.

Then try a candidate answer:

candidate = answer | (1 << bit)

We need to know whether there are two prefixes p and q such that:

p ^ q == candidate

This can be rearranged as:

q = p ^ candidate

So if we store all prefixes in a set, we can check whether a matching prefix exists.

Algorithm

Initialize:

answer = 0
mask = 0

Then scan bits from 30 down to 0.

For each bit:

1. Add this bit to the mask.
2. Store all prefixes:

num & mask

3. Try setting this bit in the answer:

candidate = answer | (1 << bit)

4. Check if there are two prefixes that XOR to candidate.
5. If yes, update:

answer = candidate

At the end, return answer.

Correctness

The algorithm builds the maximum XOR value from most significant bit to least significant bit.

Assume that before processing a bit, answer is the largest possible XOR prefix for all higher bits.

The algorithm tries to set the current bit to 1, forming candidate.

If there are two number prefixes whose XOR equals candidate, then some pair of numbers can achieve the higher-bit pattern represented by candidate. Since setting a higher bit to 1 gives a larger value than any choice in lower bits, the greedy choice is optimal.

If no such pair exists, then no pair can achieve that higher-bit pattern, so the current bit must remain 0.

This preserves the invariant that answer is the largest achievable XOR prefix after each bit.

After all bits are processed, every bit of the maximum XOR has been decided, so answer is the maximum possible XOR value.

Complexity

Since 31 is constant, the time complexity is usually written as:

O(n)

Implementation

from typing import List

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        answer = 0
        mask = 0

        for bit in range(30, -1, -1):
            mask |= 1 << bit

            prefixes = {num & mask for num in nums}

            candidate = answer | (1 << bit)

            for prefix in prefixes:
                if prefix ^ candidate in prefixes:
                    answer = candidate
                    break

        return answer

Code Explanation

We start with:

answer = 0
mask = 0

answer stores the best XOR prefix found so far.

mask keeps only the bits we are currently considering.

We process bits from high to low:

for bit in range(30, -1, -1):

The largest value is at most 2^31 - 1, so bit 30 is the highest relevant bit.

We extend the mask:

mask |= 1 << bit

Then we collect prefixes:

prefixes = {num & mask for num in nums}

The candidate tries to make the current bit 1:

candidate = answer | (1 << bit)

Then we test whether two prefixes can produce that candidate:

if prefix ^ candidate in prefixes:

If true, the current bit can be 1, so we keep it:

answer = candidate

Finally:

return answer

Alternative Trie Solution

A binary trie also works.

Insert each number into a trie by bits.

For each number, greedily walk the opposite bit when possible, because opposite bits produce XOR bit 1.

from typing import List

class TrieNode:
    def __init__(self):
        self.child = [None, None]

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        root = TrieNode()

        for num in nums:
            node = root

            for bit in range(30, -1, -1):
                b = (num >> bit) & 1

                if node.child[b] is None:
                    node.child[b] = TrieNode()

                node = node.child[b]

        best = 0

        for num in nums:
            node = root
            value = 0

            for bit in range(30, -1, -1):
                b = (num >> bit) & 1
                want = b ^ 1

                if node.child[want] is not None:
                    value |= 1 << bit
                    node = node.child[want]
                else:
                    node = node.child[b]

            best = max(best, value)

        return best

The prefix-set solution is shorter. The trie solution is often easier to generalize to online queries.

Testing

def test_find_maximum_xor():
    s = Solution()

    assert s.findMaximumXOR([3, 10, 5, 25, 2, 8]) == 28

    assert s.findMaximumXOR([
        14, 70, 53, 83, 49, 91,
        36, 80, 92, 51, 66, 70,
    ]) == 127

    assert s.findMaximumXOR([0]) == 0

    assert s.findMaximumXOR([2, 4]) == 6

    assert s.findMaximumXOR([8, 10, 2]) == 10

    assert s.findMaximumXOR([7, 7, 7]) == 0

    assert s.findMaximumXOR([0, 2147483647]) == 2147483647

    print("all tests passed")

Test Notes