# Maximum XOR of Two Numbers in an Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array)
Canonical: https://scaleengineer.com/dsa/problems/maximum-xor-of-two-numbers-in-an-array
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array, Hash Table, Trie
**Companies:** [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs)
---
## Problem
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 * 105`
* `0 <= nums[i] <= 231 - 1`

# Approaches
## Brute Force
The most straightforward approach is to check every possible pair of numbers in the array. We can use two nested loops to iterate through all pairs `(i, j)`, calculate `nums[i] XOR nums[j]`, and keep track of the maximum value found.
**Time:** O(N^2), where N is the number of elements in the array. This is because of the two nested loops, each iterating up to N times. · **Space:** O(1)
**Pros:** Simple to understand and implement.; Requires no extra space, making its space complexity constant.
**Cons:** Extremely inefficient for large inputs due to its quadratic time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error on most competitive programming platforms for the given constraints.
### Explanation
This method exhaustively checks every unique pair of elements in the input array `nums`. It maintains a variable, `maxResult`, initialized to zero. The outer loop iterates from the first element to the last, and the inner loop iterates from the current element of the outer loop to the last. This ensures that each pair is considered exactly once (including a number with itself, which results in an XOR of 0). For each pair, their bitwise XOR is computed. If this result is larger than the current `maxResult`, `maxResult` is updated. This process guarantees that we find the maximum possible XOR value among all pairs.

```java
class Solution {
    public int findMaximumXOR(int[] nums) {
        int maxResult = 0;
        int n = nums.length;
        if (n < 2) {
            return 0;
        }
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                maxResult = Math.max(maxResult, nums[i] ^ nums[j]);
            }
        }
        return maxResult;
    }
}
```
### Algorithm
- Initialize a variable `maxResult` to 0.
- Use two nested loops to iterate through all possible pairs of numbers `(nums[i], nums[j])` in the array.
- For each pair, calculate their XOR value: `currentXOR = nums[i] ^ nums[j]`.
- Compare `currentXOR` with `maxResult` and update `maxResult` if `currentXOR` is greater.
- After checking all pairs, `maxResult` will hold the maximum XOR value.

## Bit Manipulation with HashSet
A more optimized approach involves building the maximum XOR result bit by bit, from the most significant bit (MSB) to the least significant bit (LSB). We can greedily try to make each bit of the result a '1' and use a `HashSet` to efficiently check if this is possible.
**Time:** O(N * L), where N is the number of elements and L is the number of bits in the integers (here, L is constant, ~32). The outer loop runs L times, and inside it, we iterate through N elements twice (once to build the set, once to check). · **Space:** O(N), where N is the number of elements in the array. This is for storing the prefixes in the `HashSet` in each iteration.
**Pros:** Significantly more efficient than the brute-force approach, with linear time complexity.; Provides a good foundation for understanding the more advanced Trie-based solution.
**Cons:** The logic can be non-intuitive at first glance.; Uses O(N) extra space for the HashSet, which might be significant for very large N.
### Explanation
This approach leverages the properties of XOR. We want to maximize the result, so we should try to make the most significant bits '1' whenever possible. We iterate from bit 31 down to 0. For each bit `i`, we determine if it's possible to have a '1' at this position in the final answer, given the choices we've made for the higher bits.

Let's say `maxResult` stores the result built so far. We test if we can form a new result `temp = maxResult | (1 << i)`. This `temp` would be a valid prefix for our answer if there exist two numbers `a` and `b` in the input array such that `a ^ b = temp`. This is equivalent to `a ^ temp = b`. 

To check this efficiently, we first compute the prefixes of all numbers in `nums` using a `mask` that covers bits from 31 down to `i`. We store these prefixes in a `HashSet`. Then, for each `prefix` in the set, we check if `prefix ^ temp` also exists in the set. If we find such a pair, we know that a '1' is achievable at bit `i`, so we update `maxResult = temp`. Otherwise, we move to the next bit, leaving the `i`-th bit of `maxResult` as '0'.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int findMaximumXOR(int[] nums) {
        int maxResult = 0;
        int mask = 0;
        // Integers are 32-bit, but since constraints are non-negative, we can start from bit 30 or 31.
        for (int i = 31; i >= 0; i--) {
            // The mask grows to include more bits from the left.
            // e.g., 100...0 -> 110...0 -> 111...0
            mask = mask | (1 << i);

            Set<Integer> prefixes = new HashSet<>();
            for (int num : nums) {
                prefixes.add(num & mask);
            }

            // Greedily try to set the i-th bit of the result to 1.
            int greedyTry = maxResult | (1 << i);

            for (int prefix : prefixes) {
                if (prefixes.contains(prefix ^ greedyTry)) {
                    // If for a prefix 'p', 'p ^ greedyTry' also exists, it means we found two numbers
                    // whose prefixes XOR to our greedy target. So, this bit can be 1.
                    maxResult = greedyTry;
                    break;
                }
            }
        }
        return maxResult;
    }
}
```
### Algorithm
- Initialize `maxResult = 0` and `mask = 0`.
- Iterate from the most significant bit (MSB), say bit 31, down to the least significant bit (LSB), bit 0.
- In each iteration `i`, update the `mask` to include the current bit: `mask = mask | (1 << i)`.
- Create a `HashSet` to store the prefixes of all numbers in `nums`. The prefix is calculated by `num & mask`.
- Greedily assume the `i`-th bit of the final answer can be 1. Let this potential answer be `greedyTry = maxResult | (1 << i)`.
- To check if this is possible, we need to find if there are two numbers `a` and `b` in `nums` such that their prefixes `(a & mask) ^ (b & mask) == greedyTry`. This is equivalent to checking if for any prefix `p` in our set, `p ^ greedyTry` also exists in the set.
- If such a pair of prefixes is found, it means our greedy assumption was correct. We update `maxResult = greedyTry` and proceed to the next bit.
- If not, the `i`-th bit of the result must be 0, so we leave `maxResult` as is.
- After iterating through all bits, `maxResult` will hold the answer.

## Trie (Prefix Tree)
The most efficient and standard solution for this problem uses a Trie (Prefix Tree). By storing the binary representations of all numbers in a Trie, we can efficiently query for each number `x` to find the number `y` in the set that maximizes `x ^ y`.
**Time:** O(N * L), where N is the number of elements and L is the number of bits in the integers (~32). Building the Trie takes O(N*L) and querying for all numbers also takes O(N*L). Since L is constant, the complexity is effectively linear, O(N). · **Space:** O(N * L), where N is the number of elements and L is the number of bits. In the worst case, each number creates a unique path of L nodes in the Trie.
**Pros:** Optimal time complexity, linear in the number of elements.; It's a canonical and versatile technique for a wide range of bitwise problems.
**Cons:** Requires implementation of a custom Trie data structure.; Space complexity can be higher than the HashSet approach in the worst case, as it stores the entire prefix structure.
### Explanation
A Trie is a perfect data structure for this problem because it organizes numbers based on their bit prefixes. To maximize an XOR result, we want to find a pair of numbers whose bits differ as much as possible, especially at the most significant positions.

First, we build the Trie. We iterate through each number in the input array `nums`. For each number, we traverse its binary representation from the most significant bit (31) to the least significant (0) and insert it into the Trie. Each node in the Trie represents a bit, and its children point to the next bits (0 or 1).

After building the Trie, we iterate through `nums` a second time. For each number `num`, we traverse the Trie to find its ideal XOR partner. Starting from the MSB of `num`, we look for the opposite bit in the Trie. For example, if the current bit of `num` is `0`, we try to find a path for `1` in the Trie. If we succeed, we know this bit position in our XOR result will be `1`, and we move to that child node. If the path for the opposite bit doesn't exist, we have no choice but to follow the path for the same bit, which results in a `0` at this bit position in the XOR result. We do this for all 32 bits, constructing the maximum possible XOR for `num`. We keep track of the overall maximum found across all numbers.

```java
class TrieNode {
    TrieNode[] children;
    public TrieNode() {
        children = new TrieNode[2]; // 0 and 1
    }
}

class Solution {
    public int findMaximumXOR(int[] nums) {
        TrieNode root = new TrieNode();

        // 1. Insert all numbers into the Trie.
        for (int num : nums) {
            TrieNode curr = root;
            for (int i = 31; i >= 0; i--) {
                int bit = (num >> i) & 1;
                if (curr.children[bit] == null) {
                    curr.children[bit] = new TrieNode();
                }
                curr = curr.children[bit];
            }
        }

        int maxResult = 0;

        // 2. For each number, find the max XOR partner in the Trie.
        for (int num : nums) {
            TrieNode curr = root;
            int currentXOR = 0;
            for (int i = 31; i >= 0; i--) {
                int bit = (num >> i) & 1;
                int oppositeBit = 1 - bit;

                if (curr.children[oppositeBit] != null) {
                    // We can maximize this bit to 1.
                    currentXOR = (currentXOR << 1) | 1;
                    curr = curr.children[oppositeBit];
                } else {
                    // We have to settle for 0 at this bit.
                    currentXOR = (currentXOR << 1) | 0;
                    curr = curr.children[bit];
                }
            }
            maxResult = Math.max(maxResult, currentXOR);
        }

        return maxResult;
    }
}
```
### Algorithm
- **Trie Node Definition**: Define a `TrieNode` class with an array (or map) of two children, one for bit `0` and one for bit `1`.
- **Build the Trie**: 
  - Create a root `TrieNode`.
  - For each number in `nums`, insert its 32-bit binary representation into the Trie. Traverse from the MSB (bit 31) to the LSB (bit 0), creating nodes as necessary.
- **Find Maximum XOR**: 
  - Initialize `maxResult = 0`.
  - For each number `num` in `nums` again:
    - Traverse the Trie from the root to find the number that gives the maximum XOR with `num`.
    - For each bit of `num` (from MSB to LSB), greedily look for the opposite bit in the Trie. 
    - If the opposite bit's path exists, take it. This means the corresponding bit in the XOR result will be `1`.
    - If it doesn't exist, you must take the path of the same bit. The corresponding bit in the XOR result will be `0`.
    - Build the `currentMaxXOR` for `num` bit by bit.
    - Update the global `maxResult` with `Math.max(maxResult, currentMaxXOR)`.
- **Return `maxResult`**.

# Solutions
### Java

```java
class Trie { private Trie [] children = new Trie [ 2 ]; public Trie () { } public void insert ( int x ) { Trie node = this ; for ( int i = 30 ; i >= 0 ; -- i ) { int v = x >> i & 1 ; if ( node . children [ v ] == null ) { node . children [ v ] = new Trie (); } node = node . children [ v ]; } } public int search ( int x ) { Trie node = this ; int ans = 0 ; for ( int i = 30 ; i >= 0 ; -- i ) { int v = x >> i & 1 ; if ( node . children [ v ^ 1 ] != null ) { ans |= 1 << i ; node = node . children [ v ^ 1 ]; } else { node = node . children [ v ]; } } return ans ; } } class Solution { public int findMaximumXOR ( int [] nums ) { Trie trie = new Trie (); int ans = 0 ; for ( int x : nums ) { trie . insert ( x ); ans = Math . max ( ans , trie . search ( x )); } return ans ; } }
```

### CPP

```cpp
class Trie { public: Trie * children [ 2 ]; Trie () : children { nullptr , nullptr } {} void insert ( int x ) { Trie * node = this ; for ( int i = 30 ; ~ i ; -- i ) { int v = x >> i & 1 ; if ( ! node -> children [ v ]) { node -> children [ v ] = new Trie (); } node = node -> children [ v ]; } } int search ( int x ) { Trie * node = this ; int ans = 0 ; for ( int i = 30 ; ~ i ; -- i ) { int v = x >> i & 1 ; if ( node -> children [ v ^ 1 ]) { ans |= 1 << i ; node = node -> children [ v ^ 1 ]; } else { node = node -> children [ v ]; } } return ans ; } }; class Solution { public: int findMaximumXOR ( vector < int >& nums ) { Trie * trie = new Trie (); int ans = 0 ; for ( int x : nums ) { trie -> insert ( x ); ans = max ( ans , trie -> search ( x )); } return ans ; } };
```

### Python

```python
class Trie : __slots__ = ( "children" ,) def __init__ ( self ): self . children : List [ Trie | None ] = [ None , None ] def insert ( self , x : int ): node = self for i in range ( 30 , - 1 , - 1 ): v = x >> i & 1 if node . children [ v ] is None : node . children [ v ] = Trie () node = node . children [ v ] def search ( self , x : int ) -> int : node = self ans = 0 for i in range ( 30 , - 1 , - 1 ): v = x >> i & 1 if node . children [ v ^ 1 ]: ans |= 1 << i node = node . children [ v ^ 1 ] else : node = node . children [ v ] return ans class Solution : def findMaximumXOR ( self , nums : List [ int ]) -> int : trie = Trie () for x in nums : trie . insert ( x ) return max ( trie . search ( x ) for x in nums )
```