1707. Maximum XOR With an Element From Array

Problem Description

In this problem, you're given an array nums of non-negative integers and an array queries, where each query queries[i] consists of a pair [x_i, m_i]. For each query, you have to find the maximum bitwise XOR value between x_i and any element within nums that does not exceed m_i. This means you are looking for the value max(nums[j] XOR x_i) for all indices j where nums[j] <= m_i. However, if there is no such element in nums that is less than or equal to m_i, the answer for that query will be -1. You need to solve this for all queries and return an array containing the answers.

Intuition

The task is to optimize the search for the maximum XOR pair within constraints. A brute-force approach to check each possible pair would be highly inefficient, especially for large datasets. Hence, an advanced data structure is necessary to reduce the complexity, and a Trie (prefix tree) is well-suited for this job.

A Trie is created for the binary representations of the numbers in nums. It is a tree where each level represents a bit position in the binary representation of the numbers. The left child stands for 0 and the right child for 1. This allows us to traverse the Trie to look for the number that would give us the maximum XOR with the given x, which is essentially finding the complement of x in the Trie.

The trick to making it work with the query constraints (nums[j] <= m_i) is sorting both nums and the queries by m values and only insert nums elements into the Trie that are less than or equal to m_i, doing this progressively as we go through the sorted queries. This ensures our Trie only contains valid elements for each query's m condition. We do a search for each x in the Trie and compute the maximum XOR value we can achieve. If we cannot find any number in the Trie that matches the condition for x, we return -1 for that query.

Learn more about Trie patterns.

Solution Approach

The solution to the problem utilizes a Trie data structure in conjunction with a sort-then-search strategy. Here's a breakdown of the key steps in the algorithm:

1. Sort nums: Begin by sorting the nums array in non-decreasing order. This allows us to efficiently insert numbers into our Trie that are less than or equal to the current query's m_i.

2. Sort Queries by m_i: Similarly, we sort the queries based on the m_i values. We pair each query with its original index in an (index, query) tuple so that we can populate the answer in its correct position later. We sort these pairs primarily by m_i to align our insertion strategy into the Trie.

3. Trie Insertion & Search:

   • We create a Trie. Each node in the Trie will have up to two children, representing a binary 0 or 1.
   • As we traverse our sorted queries, we insert only those elements from nums into the Trie which are less than or equal to m_i. We process queries one by one and ensure at each step that our Trie contains all elements from nums that meet the current m constraint by inserting elements from nums as we go along until we reach or exceed m_i.
   • After ensuring that the Trie has all the valid elements for a particular m_i, we then search for the maximum XOR value for x_i using the Trie. We traverse down the Trie nodes, always preferring the path that leads us to an opposite bit of x_i, as this will maximize the XOR value. If such a path exists at every bit decision point, we accumulate the bit to our answer.

4. Answer Construction:

   • Throughout the above process, we keep track of the answer for each sorted query by looking for the best XOR match in the Trie. If we can't find a match (which would mean the Trie is empty for this query), we mark the answer as -1.
   • We store each query answer with the corresponding original index that we kept from the step of sorting the queries.
   • After processing all queries, we return the results in the original order of the queries.

The algorithms and data structures used are as follows:

• Sorting: To align the queries with the increasing order of nums.
• Bit Manipulation: For insertion and searching within the Trie, using right-shifts and bitwise OR operations.
• Trie (Prefix tree): A binary Trie where each path represents the bits of the number, facilitating efficient maximum XOR searches.

The core idea behind the search operation in the Trie is to take the opposite path of the current bit of x_i (if available) to maximize the XOR value. This is derived from the property of XOR that 0 XOR 1 = 1 and 1 XOR 0 = 1, which yields a higher number if the bits differ.

In the provided Python solution, the [Trie](/problems/trie_intro) class defines insert and search functions:

• The insert function takes a number x and inserts it into the Trie bit by bit from the most significant bit to the least.
• The search function takes an integer x and seeks out the number in the Trie that maximizes the XOR result with x. It returns -1 if no such number can be found in the current Trie structure.
• The maximizeXor function is where the main algorithm is encapsulated.

All of these components combined efficiently resolve the problem of finding the maximum XOR value for each query within the specified conditions.

Example Walkthrough

Let's take an example to illustrate the solution approach described.

Suppose we are given the following:

• nums = [0, 1, 2, 3, 4]
• queries = [[3, 1], [1, 3]]

First, we sort nums, but in this case, nums is already sorted.

Now, let's sort the queries based on their m_i values, along with their original indices:

• Queries sorted by m_i: [([3, 1], 0), ([1, 3], 1)]

Now we initialize the Trie data structure, which will be used to insert elements from nums and search for maximum XOR.

We start processing the queries in sorted order of m_i:

1. For the first query [3, 1]:

   • We insert the numbers from nums that are less or equal to 1 into the Trie, which includes 0 and 1.
   • We then search for the maximum XOR of 3 with the elements in the Trie.
   • The maximum XOR is 3 XOR 1 = 2 (binary: 11 XOR 01 = 10), so the answer for this query is 2.

2. Before moving to the next query, we insert any numbers from nums into the Trie that are less than or equal to the next query's m_i (which is 3) and not already present in the Trie. In this case, we insert 2 and 3.

3. For the second query [1, 3]:

   • We don't need to insert any new elements into the Trie because the Trie already contains all elements from nums less than or equal to 3.
   • Now, we search for the maximum XOR of 1 with elements in the Trie.
   • The maximum XOR is 1 XOR 2 = 3 (binary: 01 XOR 10 = 11), so the answer for this query is 3.

Finally, we construct the answer array with answers in the original query order based on their original indices:

• Answer array: [2, 3]

So, for our example queries:

• The answer to the first query [3, 1] is 2.
• The answer to the second query [1, 3] is 3.

Thus, we return [2, 3] as the solution.

Python Solution

1class Trie:
2    def __init__(self):
3        # Each Trie node will have two children for binary representation (0 and 1).
4        self.children = [None] * 2
5
6    def insert(self, x):
7        # Insert a number into the Trie.
8        node = self
9        # 30 to 0 because we're considering a 31-bit number representation (ignoring signed bit).
10        for i in range(30, -1, -1):  
11            bit = (x >> i) & 1  # Extract the bit at the ith position from right.
12            # If the corresponding Trie node for this bit does not exist, create it.
13            if node.children[bit] is None:
14                node.children[bit] = Trie()
15            # Move to the corresponding child node to continue insertion.
16            node = node.children[bit]
17
18    def search(self, x):
19        # Search maximum XOR of x with elements inserted in the Trie.
20        node = self
21        max_xor = 0
22        for i in range(30, -1, -1):
23            bit = (x >> i) & 1  # Extract the bit at the ith position from right.
24            toggled_bit = bit ^ 1  # Toggle the bit to find the maximum XOR.
25            if node.children[toggled_bit]:
26                # If the toggled bit is present, it means we can maximize XOR at this position.
27                max_xor |= 1 << i
28                node = node.children[toggled_bit]
29            elif node.children[bit]:
30                # Otherwise, continue with same bit if available.
31                node = node.children[bit]
32            else:
33                # If neither nodes are found, -1 is returned since no number can be XORed.
34                return -1
35        return max_xor
36
37
38class Solution:
39    def maximize_xor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
40        # Initialize Trie data structure.
41        trie = Trie()
42        # Sort nums to handle queries in ascending order of their limit.
43        nums.sort()
44        answers = [-1] * len(queries)  # Initialize answers list with -1 as default value.
45        # Iterate over queries sorted by their limit.
46        for index, (x, limit) in sorted(enumerate(queries), key=lambda query: query[1][1]):
47            # Insert all numbers from nums into Trie that are less than or equal to current query limit.
48            while nums and nums[0] <= limit:
49                trie.insert(nums.pop(0))  # Insert and remove the element from nums to avoid re-insertion.
50            # Store the result of maximize XOR search for the current query.
51            answers[index] = trie.search(x)
52        return answers
53

Java Solution

1// Trie class for efficient insert and search operations.
2class Trie {
3    Trie[] children = new Trie[2]; // Each Trie node can have at most two children: 0 and 1.
4
5    // Inserts an integer into the Trie.
6    public void insert(int number) {
7        Trie node = this;
8        for (int i = 30; i >= 0; --i) {
9            int bitValue = (number >> i) & 1; // Get the i-th bit of the number.
10            if (node.children[bitValue] == null) {
11                node.children[bitValue] = new Trie(); // If the path doesn't exist, create a new Trie node.
12            }
13            node = node.children[bitValue]; // Move to the next node in the path.
14        }
15    }
16
17    // Searches the Trie for the maximum XOR for a given number.
18    public int search(int number) {
19        Trie node = this;
20        int maxXor = 0;
21        for (int i = 30; i >= 0; --i) {
22            int bitValue = (number >> i) & 1; // Get the i-th bit of the number.
23            // Try to find a complement bit for maximizing XOR.
24            if (node.children[bitValue ^ 1] != null) {
25                maxXor |= 1 << i; // Update the result by setting the i-th bit.
26                node = node.children[bitValue ^ 1]; // Move to the node with the opposite bit value.
27            } else if (node.children[bitValue] != null) {
28                node = node.children[bitValue]; // Follow the available bit if complement bit is not available.
29            } else {
30                return -1; // If no path is found, return -1.
31            }
32        }
33        return maxXor;
34    }
35}
36
37// Solution class to solve the problem.
38class Solution {
39    public int[] maximizeXor(int[] nums, int[][] queries) {
40        Trie trie = new Trie(); // Create a new Trie.
41        Arrays.sort(nums); // Sort the input array.
42      
43        int n = queries.length;
44        int[] answers = new int[n];
45        int[][] orderedQueries = new int[n][3]; // Store queries with indices for later retrieval.
46
47        // Prepare and sort queries based on the second element (ai in queries[i][0], mi in queries[i][1]).
48        for (int i = 0; i < n; ++i) {
49            orderedQueries[i] = new int[] {i, queries[i][0], queries[i][1]};
50        }
51        Arrays.sort(orderedQueries, (a, b) -> a[2] - b[2]);
52
53        int index = 0;
54        for (var query : orderedQueries) {
55            int queryIndex = query[0], x = query[1], m = query[2];
56            // Insert into Trie all numbers less than or equal to m.
57            while (index < nums.length && nums[index] <= m) {
58                trie.insert(nums[index++]);
59            }
60            // Perform the query to find the maximum XOR value and store it in the corresponding index.
61            answers[queryIndex] = trie.search(x);
62        }
63
64        return answers; // Return the completed array of maximum XOR values for each query.
65    }
66}
67

C++ Solution

1#include <vector>
2#include <tuple>
3#include <algorithm>
4
5// Definition of the Trie class for storing integers in binary format.
6class Trie {
7public:
8    // Constructor initializes a Trie node with space for two children (binary digits 0 and 1).
9    Trie() : children(2, nullptr) {}
10
11    // Inserts an integer into the Trie, breaking it down into binary representation.
12    void insert(int number) {
13        Trie* node = this;
14        for (int bitIndex = 30; bitIndex >= 0; --bitIndex) {
15            int bitValue = (number >> bitIndex) & 1;
16            if (!node->children[bitValue]) {
17                node->children[bitValue] = new Trie();
18            }
19            node = node->children[bitValue];
20        }
21    }
22
23    // Searches for the binary representation that maximizes the XOR with given number.
24    int search(int number) {
25        int maxXor = 0;
26        Trie* node = this;
27        for (int bitIndex = 30; bitIndex >= 0; --bitIndex) {
28            int bitValue = (number >> bitIndex) & 1;
29            if (node->children[bitValue ^ 1]) {
30                node = node->children[bitValue ^ 1];
31                maxXor |= 1 << bitIndex;
32            } else if (node->children[bitValue]) {
33                node = node->children[bitValue];
34            } else {
35                return -1;  // This signifies that no valid number was found.
36            }
37        }
38        return maxXor;
39    }
40
41private:
42    std::vector<Trie*> children;  // Pointers to child Trie nodes.
43};
44
45class Solution {
46public:
47    // Solves each query by finding the maximum XOR value for each x with a number in nums not exceeding m.
48    std::vector<int> maximizeXor(std::vector<int>& nums, std::vector<std::vector<int>>& queries) {
49        // Sort the input numbers for efficient processing.
50        std::sort(nums.begin(), nums.end());
51      
52        // Prepare to iterate over the queries.
53        int numQueries = queries.size();
54        std::vector<std::tuple<int, int, int>> extendedQueries;
55        for (int i = 0; i < numQueries; ++i) {
56            extendedQueries.emplace_back(queries[i][1], queries[i][0], i);
57        }
58        // Sort the queries by the second element (m).
59        std::sort(extendedQueries.begin(), extendedQueries.end());
60      
61        Trie* trie = new Trie();
62        int numsIndex = 0;
63        std::vector<int> answers(numQueries);
64        // Iterate over the sorted queries.
65        for (const auto& [maxWith, xorWith, originalIndex] : extendedQueries) {
66            // Insert numbers to the Trie that do not exceed the current query's m (maxWith).
67            while (numsIndex < nums.size() && nums[numsIndex] <= maxWith) {
68                trie->insert(nums[numsIndex++]);
69            }
70            // Search for the best XOR match with x (xorWith) and store the result in the answer vector.
71            answers[originalIndex] = trie->search(xorWith);
72        }
73        return answers;
74    }
75};
76

Typescript Solution

1type TreeNode = Trie | null;
2
3class Trie {
4    children: [TreeNode, TreeNode];
5
6    constructor() {
7        // Initialize children with null (for 0 and 1 as they are the only binary digits)
8        this.children = [null, null];
9    }
10
11    // Inserts an integer into the Trie by converting it to binary representation
12    insert(number: number): void {
13        let node: Trie = this;
14        for (let bitIndex = 30; bitIndex >= 0; --bitIndex) {
15            const bitValue = (number >> bitIndex) & 1;
16            if (!node.children[bitValue]) {
17                node.children[bitValue] = new Trie();
18            }
19            node = node.children[bitValue]!;
20        }
21    }
22
23    // Searches for the Trie node that maximizes the XOR for a given number
24    search(number: number): number {
25        let maxXor = 0;
26        let node: Trie | null = this;
27        for (let bitIndex = 30; bitIndex >= 0; --bitIndex) {
28            const bitValue = (number >> bitIndex) & 1;
29            if (node.children[bitValue ^ 1]) {
30                maxXor |= 1 << bitIndex;
31                node = node.children[bitValue ^ 1]!;
32            } else if (node.children[bitValue]) {
33                node = node.children[bitValue]!;
34            } else {
35                // Return -1 if a matching number isn't found
36                return -1;
37            }
38        }
39        return maxXor;
40    }
41}
42
43// Function that solves each query by finding the maximum XOR a number in 'nums' and not exceeding 'm'
44function maximizeXor(nums: number[], queries: number[][]): number[] {
45    // Sort nums for efficient processing
46    nums.sort((a, b) => a - b);
47  
48    // Add index information to query tuples and sort them based on m
49    let extendedQueries = queries.map((query, index) => ({ maxWith: query[1], xorWith: query[0], originalIndex: index }));
50    extendedQueries.sort((a, b) => a.maxWith - b.maxWith);
51
52    let trie = new Trie();
53    let numsIndex = 0;
54    let answers: number[] = new Array(queries.length);
55
56    // Process each query, inserting elements to the Trie as needed
57    for (const { maxWith, xorWith, originalIndex } of extendedQueries) {
58        // Insert into Trie numbers from nums not exceeding the current maxWith value
59        while (numsIndex < nums.length && nums[numsIndex] <= maxWith) {
60            trie.insert(nums[numsIndex++]);
61        }
62        // Search for the best XOR with the given number
63        answers[originalIndex] = trie.search(xorWith);
64    }
65
66    return answers;
67}
68

Time and Space Complexity

Time Complexity

The time complexity of the insert and search functions in the Trie class is O(B) where B is the bit length of the numbers. In this case, B = 31 for a 32-bit integer (range(30, -1, -1)). The sorting of nums is O(N log N) where N is the length of nums.

1. For sorting nums: O(N log N)
2. For the loop to insert in Trie: O(N * B) since we insert N numbers and each insertion takes O(B) time.
3. For the loop over queries: O(Q * B) where Q is the number of queries, as we are potentially searching in the Trie for each query.

Overall, the time complexity is dominated by the insertion and searches, leading to O((N + Q) * B).

Space Complexity

The space complexity of the Trie is O(B * N) in the worst case when all N numbers have different bits, requiring to allocate a full Trie node of 2 children for each bit of every number.

Combined with the space required to store the nums and queries, and the additional ans list, the total space complexity becomes:

• O(N) for nums list
• O(Q) for queries list (ignoring the extra space needed for sorting)
• O(Q) for ans list
• O(B * N) for Trie

Which all adds up to O(B * N + Q) taking into account that B is a constant.

Learn more about how to find time and space complexity quickly.