# Maximum XOR With an Element From Array
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-xor-with-an-element-from-array)
Canonical: https://scaleengineer.com/dsa/problems/maximum-xor-with-an-element-from-array
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array, Trie
---
## Problem
You are given an array `nums` consisting of non-negative integers. You are also given a `queries` array, where `queries[i] = [xi, mi]`.

The answer to the `ith` query is the maximum bitwise `XOR` value of `xi` and any element of `nums` that does not exceed `mi`. In other words, the answer is `max(nums[j] XOR xi)` for all `j` such that `nums[j] <= mi`. If all elements in `nums` are larger than `mi`, then the answer is `-1`.

Return _an integer array_ `answer` _where_ `answer.length == queries.length` _and_ `answer[i]` _is the answer to the_ `ith` _query._

**Example 1:**

**Input:** nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
**Output:** [3,3,7]
**Explanation:**
1) 0 and 1 are the only two integers not greater than 1. 0 XOR 3 = 3 and 1 XOR 3 = 2. The larger of the two is 3.
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.

**Example 2:**

**Input:** nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
**Output:** [15,-1,5]

**Constraints:**

* `1 <= nums.length, queries.length <= 105`
* `queries[i].length == 2`
* `0 <= nums[j], xi, mi <= 109`

# Approaches
## Brute Force Iteration
This approach directly translates the problem statement into code. For each query, it iterates through the entire `nums` array to find the numbers that satisfy the condition `nums[j] <= m_i` and calculates the maximum XOR value.
**Time:** O(N * Q), where N is the length of `nums` and Q is the length of `queries`. For each of the Q queries, we perform a linear scan of the N elements in `nums`. · **Space:** O(Q) to store the result array. The auxiliary space used is O(1).
**Pros:** Simple to understand and implement.; Requires minimal auxiliary space.
**Cons:** Very inefficient due to its O(N * Q) time complexity.; Will result in a 'Time Limit Exceeded' error for large inputs as specified in the problem constraints.
### Explanation
We initialize an `answer` array to store the results for each query. We loop through each query `[x_i, m_i]` from the `queries` array. For each query, we initialize a variable `max_xor` to -1. This variable will keep track of the maximum XOR value found so far for the current query. We then iterate through every number `num` in the `nums` array. Inside this inner loop, we check if `num <= m_i`. If the condition is met, we calculate the bitwise XOR of `x_i` and `num`. We then update `max_xor` to be the maximum of its current value and the newly calculated XOR value. After iterating through all numbers in `nums`, the value of `max_xor` is the answer for the current query. If no number satisfied the condition, `max_xor` remains -1. We store this result in our `answer` array. Finally, after processing all queries, we return the `answer` array.

```java
class Solution {
    public int[] maximizeXor(int[] nums, int[][] queries) {
        int n = queries.length;
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            int x = queries[i][0];
            int m = queries[i][1];
            int maxVal = -1;
            for (int num : nums) {
                if (num <= m) {
                    maxVal = Math.max(maxVal, x ^ num);
                }
            }
            answer[i] = maxVal;
        }
        return answer;
    }
}
```
### Algorithm
1. Initialize an `answer` array of the same size as `queries`.
2. For each query `[xi, mi]` in `queries`:
   a. Initialize `max_xor = -1`.
   b. Iterate through each number `num` in `nums`.
   c. If `num <= mi`:
      i. Calculate `current_xor = xi XOR num`.
      ii. Update `max_xor = max(max_xor, current_xor)`.
   d. Store `max_xor` in the `answer` array for the current query.
3. Return the `answer` array.

## Offline Processing with Trie (Prefix Tree)
This approach optimizes the process by sorting both the numbers and the queries. By processing queries in increasing order of their `m_i` limit, we can efficiently manage the set of valid numbers using a Trie data structure. This avoids re-scanning the `nums` array for each query.
**Time:** O(N log N + Q log Q + (N+Q)*L), where N is the length of `nums`, Q is the length of `queries`, and L is the number of bits (constant). The complexity is dominated by the sorting steps, making it O(N log N + Q log Q). · **Space:** O(Q + N*L), where Q is for storing `indexedQueries` and the `ans` array, and O(N*L) is for the Trie in the worst case, where L is the number of bits (constant, e.g., 31).
**Pros:** Highly efficient and passes the time limits for the given constraints.; The offline processing technique is a powerful pattern for similar problems where queries have range constraints.
**Cons:** More complex to implement compared to the brute-force approach.; Requires additional space for the Trie data structure and for storing augmented queries.
### Explanation
The main idea is to answer queries "offline". Instead of answering them in the given order, we reorder them to process them more efficiently. We sort the `nums` array in ascending order. We also sort the `queries` array based on their `m_i` values. Since we need to return the answers in the original order, we augment the queries with their original indices before sorting, e.g., `[x_i, m_i, original_index]`. We use a Trie (Prefix Tree) to store the binary representations of numbers. Each node in the Trie has two children, representing bits 0 and 1. We iterate through the sorted queries. For each query `[x, m, original_idx]`, we first add all numbers from the sorted `nums` array that are less than or equal to `m` into the Trie. Since both `nums` and queries (by `m`) are sorted, we can do this with a single pointer on the `nums` array, which advances monotonically. After updating the Trie with all numbers `<= m`, we query the Trie with `x` to find the number that gives the maximum XOR value. To do this, we traverse the Trie from the most significant bit to the least significant. At each bit position, we try to take a path that is opposite to the corresponding bit of `x` to maximize the XOR result. If such a path doesn't exist, we take the only available path. If the Trie is empty when we process a query (meaning no number in `nums` is `<= m`), the answer is -1. The result for each query is stored in an answer array at its original index. Finally, we return the fully populated answer array.

```java
class TrieNode {
    TrieNode[] children = new TrieNode[2];
}

class Trie {
    TrieNode root = new TrieNode();
    private static final int MAX_BIT = 30;

    public void insert(int num) {
        TrieNode curr = root;
        for (int i = MAX_BIT; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (curr.children[bit] == null) {
                curr.children[bit] = new TrieNode();
            }
            curr = curr.children[bit];
        }
    }

    public int getMaxXor(int num) {
        TrieNode curr = root;
        int maxXor = 0;
        for (int i = MAX_BIT; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int oppositeBit = 1 - bit;
            if (curr.children[oppositeBit] != null) {
                maxXor |= (1 << i);
                curr = curr.children[oppositeBit];
            } else {
                curr = curr.children[bit];
            }
        }
        return maxXor;
    }
}

class Solution {
    public int[] maximizeXor(int[] nums, int[][] queries) {
        Arrays.sort(nums);
        int numQueries = queries.length;
        int[][] indexedQueries = new int[numQueries][3];
        for (int i = 0; i < numQueries; i++) {
            indexedQueries[i][0] = queries[i][0];
            indexedQueries[i][1] = queries[i][1];
            indexedQueries[i][2] = i;
        }

        Arrays.sort(indexedQueries, (a, b) -> Integer.compare(a[1], b[1]));

        int[] ans = new int[numQueries];
        Trie trie = new Trie();
        int numsIndex = 0;

        for (int[] query : indexedQueries) {
            int x = query[0];
            int m = query[1];
            int originalIndex = query[2];

            while (numsIndex < nums.length && nums[numsIndex] <= m) {
                trie.insert(nums[numsIndex]);
                numsIndex++;
            }

            if (numsIndex == 0) {
                ans[originalIndex] = -1;
            } else {
                ans[originalIndex] = trie.getMaxXor(x);
            }
        }
        return ans;
    }
}
```
### Algorithm
1. Create an `indexedQueries` array where each element is `[x, m, original_index]`.
2. Sort the `nums` array in ascending order.
3. Sort the `indexedQueries` array based on the `m` value in ascending order.
4. Initialize an empty Trie, an `answer` array of size `queries.length`, and a pointer `numsIndex = 0`.
5. For each `[x, m, originalIndex]` in `sortedQueries`:
6.   While `numsIndex < nums.length` and `nums[numsIndex] <= m`:
7.     Insert `nums[numsIndex]` into the Trie.
8.     Increment `numsIndex`.
9.   If `numsIndex == 0` (Trie is empty):
10.    Set `answer[originalIndex] = -1`.
11.  Else:
12.    Query the Trie with `x` to find the maximum XOR value.
13.    Set `answer[originalIndex]` to this maximum value.
14. Return `answer`.

# Solutions
### Java

```java
class Trie { private Trie [] children = new Trie [ 2 ]; 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 if ( node . children [ v ] != null ) { node = node . children [ v ]; } else { return - 1 ; } } return ans ; } } class Solution { public int [] maximizeXor ( int [] nums , int [][] queries ) { Arrays . sort ( nums ); int n = queries . length ; Integer [] idx = new Integer [ n ]; for ( int i = 0 ; i < n ; ++ i ) { idx [ i ] = i ; } Arrays . sort ( idx , ( i , j ) -> queries [ i ][ 1 ] - queries [ j ][ 1 ]); int [] ans = new int [ n ]; Trie trie = new Trie (); int j = 0 ; for ( int i : idx ) { int x = queries [ i ][ 0 ], m = queries [ i ][ 1 ]; while ( j < nums . length && nums [ j ] <= m ) { trie . insert ( nums [ j ++]); } ans [ i ] = trie . search ( x ); } return ans ; } }
```

### CPP

```cpp
class Trie { private: Trie * children [ 2 ]; public: 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 if ( node -> children [ v ]) { node = node -> children [ v ]; } else { return - 1 ; } } return ans ; } }; class Solution { public: vector < int > maximizeXor ( vector < int >& nums , vector < vector < int >>& queries ) { sort ( nums . begin (), nums . end ()); int n = queries . size (); vector < int > idx ( n ); iota ( idx . begin (), idx . end (), 0 ); sort ( idx . begin (), idx . end (), [ & ]( int i , int j ) { return queries [ i ][ 1 ] < queries [ j ][ 1 ]; }); vector < int > ans ( n ); Trie trie ; int j = 0 ; for ( int i : idx ) { int x = queries [ i ][ 0 ], m = queries [ i ][ 1 ]; while ( j < nums . size () && nums [ j ] <= m ) { trie . insert ( nums [ j ++ ]); } ans [ i ] = trie . search ( x ); } return ans ; } };
```

### Python

```python
class Trie : __slots__ = [ "children" ] def __init__ ( self ): self . children = [ None ] * 2 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 ] elif node . children [ v ]: node = node . children [ v ] else : return - 1 return ans class Solution : def maximizeXor ( self , nums : List [ int ], queries : List [ List [ int ]]) -> List [ int ]: trie = Trie () nums . sort () j , n = 0 , len ( queries ) ans = [ - 1 ] * n for i , ( x , m ) in sorted ( zip ( range ( n ), queries ), key = lambda x : x [ 1 ][ 1 ]): while j < len ( nums ) and nums [ j ] <= m : trie . insert ( nums [ j ]) j += 1 ans [ i ] = trie . search ( x ) return ans
```