Maximum XOR of Two Numbers in an Array - Video Solutions

Problem Overview: Given an integer array nums, you need to find two numbers whose XOR value is the largest possible. The challenge is identifying the pair that maximizes the XOR operation without checking every combination when the array becomes large.

Approach 1: Brute Force Pair Comparison (O(n²) time, O(1) space)

The most direct strategy checks every possible pair in the array. Iterate through the array using two nested loops and compute nums[i] ^ nums[j] for each pair. Track the maximum value seen so far and return it after scanning all combinations. This method uses basic array traversal and bit manipulation operations.

The logic is easy to implement and useful for validating correctness on small datasets. However, the time complexity grows quickly because every element is compared with every other element. With n numbers, the algorithm performs roughly n*(n-1)/2 XOR operations, making it impractical for large inputs.

Approach 2: Trie-Based Bit Optimization (O(n * W) time, O(n * W) space)

A more efficient solution builds a binary Trie based on the bit representation of each number. Each level of the Trie represents a bit position (usually 31 down to 0 for 32‑bit integers). While inserting numbers, you store paths for 0 and 1 bits. To maximize XOR, traverse the Trie preferring the opposite bit at each level because XOR becomes 1 when bits differ.

For every number in the array, walk the Trie from the most significant bit to the least significant bit. If the current bit is 0, try moving to the 1 branch; if the bit is 1, try moving to the 0 branch. This greedy decision maximizes the resulting XOR value bit by bit. Each insertion and query touches at most W bits, where W is the integer bit length (typically 32).

The Trie structure allows you to efficiently search for the best complementary number already inserted. Instead of comparing against all elements, you narrow the search using bit decisions. The result is near-linear performance relative to the input size.

Recommended for interviews: Interviewers expect the Trie-based approach because it demonstrates strong understanding of bitwise operations and optimized search structures. Starting with the brute force approach shows you understand the problem baseline. Transitioning to the Trie solution shows algorithmic maturity and familiarity with advanced bitwise greedy strategies used in many XOR-related problems.