LeetCode 421 - Maximum XOR of Two Numbers in an Array

The problem gives us an array of non-negative integers called nums. We must choose two indices i and j such that 0 <= i <= j < n, then compute: The goal is to return the largest XOR value that can be produced from any pair in the array.

leetcodemediumarrayhash-tablebit-manipulationtrie

LeetCode Problem 421

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Bit Manipulation, Trie

Solution

LeetCode 421 - Maximum XOR of Two Numbers in an Array

Problem Understanding

The problem gives us an array of non-negative integers called nums. We must choose two indices i and j such that 0 <= i <= j < n, then compute:

nums[i] XOR nums[j]

The goal is to return the largest XOR value that can be produced from any pair in the array.

The XOR operation compares bits position by position:

  • 0 XOR 0 = 0
  • 1 XOR 1 = 0
  • 0 XOR 1 = 1
  • 1 XOR 0 = 1

This means XOR becomes large when two numbers differ at high bit positions. For example:

5  = 00101
25 = 11001
XOR= 11100 = 28

The input array can contain up to 2 * 10^5 numbers, and each number can be as large as 2^31 - 1. These constraints are important because they immediately rule out slow quadratic solutions for large inputs.

A naive solution that checks every pair would require:

O(n^2)

comparisons, which becomes too expensive when n = 200000.

The problem guarantees:

  • At least one number exists in the array
  • All numbers are non-negative
  • Values fit within 31 bits

Important edge cases include arrays with only one element, arrays where all numbers are identical, arrays containing zero, and arrays where the maximum XOR depends on differing high-order bits rather than low-order bits.

Approaches

Brute Force Approach

The most direct solution is to try every possible pair of numbers.

For every index i, we iterate through every index j >= i, compute:

nums[i] XOR nums[j]

and track the maximum result seen so far.

This works because it exhaustively checks all valid combinations, so the largest XOR value cannot be missed.

However, the time complexity is:

O(n^2)

With 200000 elements, this would require roughly:

200000^2 = 40,000,000,000

operations in the worst case, which is far too slow.

Optimal Approach, Bitwise Trie

The key insight is that XOR becomes large when corresponding bits differ.

To maximize XOR for a number, we want to find another number whose bits are opposite whenever possible.

For example, if the current bit is:

  • 1, we prefer to pair it with 0
  • 0, we prefer to pair it with 1

Since numbers are represented in binary, we can process them bit by bit from the most significant bit down to the least significant bit.

A Trie, also called a prefix tree, is ideal for this because it stores numbers according to their binary representation. Each level of the Trie corresponds to one bit position.

When searching for the best XOR partner for a number:

  • At each bit position, we greedily try to move to the opposite bit
  • If the opposite bit exists, we gain a 1 in the XOR result at that position
  • Otherwise, we move to the same bit

This greedy choice works because higher bits contribute more to the final numeric value than lower bits.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Checks every pair directly
Optimal Trie O(n * 31) O(n * 31) Uses binary Trie for efficient XOR maximization

Algorithm Walkthrough

Step 1: Build a Binary Trie

We create a Trie where each node has two possible children:

  • 0
  • 1

Each number is inserted bit by bit from the 31st bit down to the 0th bit.

We use 31 bits because the constraints guarantee values fit within signed 32-bit integers.

For example, the number 5 becomes:

000...00101

Each bit determines which child we move to in the Trie.

Step 2: Insert Every Number

As we process the array, we insert each number into the Trie.

This organizes numbers by their binary prefixes, allowing efficient bitwise searches later.

Step 3: Search for the Best XOR Partner

For each number, we traverse the Trie again.

At each bit position:

  1. Extract the current bit
  2. Compute the opposite bit
  3. Try moving to the opposite bit first
  4. If it exists, set the corresponding XOR bit to 1
  5. Otherwise move to the same bit

This greedy strategy maximizes higher-order bits first, which guarantees the maximum numeric XOR value.

Step 4: Track the Maximum XOR

For every number, we compute its best possible XOR value against numbers already in the Trie.

We continuously update the global maximum.

Step 5: Return the Final Result

After processing all numbers, the stored maximum is the answer.

Why it works

The algorithm works because XOR is maximized when bits differ at the highest possible positions. The Trie allows us to efficiently search for the best complementary bit at every level. Since we process bits from most significant to least significant, greedy choices at higher positions always dominate any later choices. Therefore, the constructed XOR value is optimal for each number, and taking the maximum across all numbers produces the correct final answer.

Python Solution

from typing import List

class TrieNode:
    def __init__(self):
        self.children = {}

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

        def insert(num: int) -> None:
            node = root

            for bit_position in range(31, -1, -1):
                bit = (num >> bit_position) & 1

                if bit not in node.children:
                    node.children[bit] = TrieNode()

                node = node.children[bit]

        def find_best_xor(num: int) -> int:
            node = root
            current_xor = 0

            for bit_position in range(31, -1, -1):
                bit = (num >> bit_position) & 1
                opposite_bit = 1 - bit

                if opposite_bit in node.children:
                    current_xor |= (1 << bit_position)
                    node = node.children[opposite_bit]
                else:
                    node = node.children[bit]

            return current_xor

        for num in nums:
            insert(num)

        maximum_xor = 0

        for num in nums:
            maximum_xor = max(maximum_xor, find_best_xor(num))

        return maximum_xor

The solution begins by defining a TrieNode class. Each node stores child pointers for binary digits 0 and 1.

The insert function places a number into the Trie one bit at a time. We iterate from bit 31 down to 0, extracting each bit using:

(num >> bit_position) & 1

If the corresponding child node does not exist, we create it.

The find_best_xor function performs the greedy XOR search. At every bit position, we attempt to move toward the opposite bit because opposite bits produce 1 in XOR. When such a branch exists, we update the current XOR value using:

current_xor |= (1 << bit_position)

This sets the current bit in the XOR result.

If the opposite branch does not exist, we move along the matching bit branch instead.

After building the Trie with all numbers, we query the Trie for every number and keep the maximum XOR encountered.

Go Solution

package main

type TrieNode struct {
	children [2]*TrieNode
}

func insert(root *TrieNode, num int) {
	node := root

	for bitPosition := 31; bitPosition >= 0; bitPosition-- {
		bit := (num >> bitPosition) & 1

		if node.children[bit] == nil {
			node.children[bit] = &TrieNode{}
		}

		node = node.children[bit]
	}
}

func findBestXOR(root *TrieNode, num int) int {
	node := root
	currentXOR := 0

	for bitPosition := 31; bitPosition >= 0; bitPosition-- {
		bit := (num >> bitPosition) & 1
		oppositeBit := 1 - bit

		if node.children[oppositeBit] != nil {
			currentXOR |= (1 << bitPosition)
			node = node.children[oppositeBit]
		} else {
			node = node.children[bit]
		}
	}

	return currentXOR
}

func findMaximumXOR(nums []int) int {
	root := &TrieNode{}

	for _, num := range nums {
		insert(root, num)
	}

	maximumXOR := 0

	for _, num := range nums {
		current := findBestXOR(root, num)

		if current > maximumXOR {
			maximumXOR = current
		}
	}

	return maximumXOR
}

The Go implementation follows the same algorithmic structure as the Python version. Instead of using dictionaries for child nodes, Go uses a fixed-size array:

children [2]*TrieNode

This is more memory efficient and faster because there are only two possible branches.

Go integers safely support the required bit operations under the given constraints. Nil pointer checks replace Python dictionary membership checks.

Worked Examples

Example 1

Input:

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

Binary Representations

Number Binary
3 00011
10 01010
5 00101
25 11001
2 00010
8 01000

Searching for Best XOR

When evaluating 5:

Bit Position Current Bit Preferred Bit Exists? XOR Bit Set?
4 0 1 Yes Yes
3 0 1 Yes Yes
2 1 0 Yes Yes
1 0 1 No No
0 1 0 No No

The resulting XOR becomes:

11100 = 28

This corresponds to:

5 XOR 25 = 28

No larger XOR exists in the array.

Example 2

Input:

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

Key Observation

The maximum XOR is:

127

Binary form:

127 = 1111111

This means the chosen pair differs at every bit position within the relevant range.

During Trie traversal, the algorithm repeatedly finds opposite bits at high positions, producing the maximum possible XOR value.

Complexity Analysis

Measure Complexity Explanation
Time O(n * 31) Each number is inserted and queried across 32 bits
Space O(n * 31) Trie may contain up to 32 nodes per number

Since 31 is constant, the practical complexity is linear with respect to the number of elements.

The Trie depth never exceeds 32 levels because integers are bounded by 32-bit representation. Therefore each insertion and lookup runs in constant time relative to bit width.

Test Cases

from typing import List

class TrieNode:
    def __init__(self):
        self.children = {}

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

        def insert(num: int) -> None:
            node = root

            for bit_position in range(31, -1, -1):
                bit = (num >> bit_position) & 1

                if bit not in node.children:
                    node.children[bit] = TrieNode()

                node = node.children[bit]

        def find_best_xor(num: int) -> int:
            node = root
            current_xor = 0

            for bit_position in range(31, -1, -1):
                bit = (num >> bit_position) & 1
                opposite_bit = 1 - bit

                if opposite_bit in node.children:
                    current_xor |= (1 << bit_position)
                    node = node.children[opposite_bit]
                else:
                    node = node.children[bit]

            return current_xor

        for num in nums:
            insert(num)

        maximum_xor = 0

        for num in nums:
            maximum_xor = max(maximum_xor, find_best_xor(num))

        return maximum_xor

solution = Solution()

assert solution.findMaximumXOR([3,10,5,25,2,8]) == 28  # provided example 1
assert solution.findMaximumXOR([14,70,53,83,49,91,36,80,92,51,66,70]) == 127  # provided example 2

assert solution.findMaximumXOR([0]) == 0  # single element
assert solution.findMaximumXOR([2,4]) == 6  # simple XOR
assert solution.findMaximumXOR([8,10,2]) == 10  # different bit patterns
assert solution.findMaximumXOR([7,7,7]) == 0  # all identical numbers
assert solution.findMaximumXOR([0,1]) == 1  # includes zero
assert solution.findMaximumXOR([1,2,4,8,16]) == 24  # powers of two
assert solution.findMaximumXOR([5,25]) == 28  # direct optimal pair
assert solution.findMaximumXOR([2147483647,0]) == 2147483647  # max 31-bit value
Test Why
[3,10,5,25,2,8] Validates standard example
[14,70,53,...] Validates large XOR across many values
[0] Tests single-element input
[2,4] Tests simple two-number XOR
[8,10,2] Tests mixed bit patterns
[7,7,7] Tests identical values
[0,1] Ensures zero handled correctly
[1,2,4,8,16] Tests powers of two
[5,25] Tests direct optimal pair
[2147483647,0] Tests upper constraint boundary

Edge Cases

Single Element Array

If the array contains only one number, the only valid pair is the number with itself:

x XOR x = 0

A buggy implementation might incorrectly assume two distinct numbers are required. This solution handles the case naturally because the Trie contains the same number being queried.

All Numbers Identical

Consider:

[7,7,7]

Every XOR result equals zero because identical bits always produce zero in XOR.

Some implementations incorrectly attempt to force differing paths in the Trie even when none exist. This implementation safely falls back to the matching bit branch whenever the opposite branch is unavailable.

Numbers with Large High Bits

Consider:

[2147483647, 0]

The maximum XOR comes entirely from high-order bits.

A common mistake is iterating through too few bit positions. This implementation processes all 32 relevant bits from 31 down to 0, ensuring large values are handled correctly.

Arrays Containing Zero

Zero is important because:

0 XOR x = x

Sometimes the maximum XOR includes zero paired with a large value.

The Trie correctly stores zero as a path consisting entirely of 0 bits, allowing comparisons against any other number without special handling.