Given an array nums of non-negative integers and an array queries where each query is [x, m], find the maximum value of x XOR num such that num comes from nums and num <= m. If no value in nums is less than or equal to m, return -1 for that query.
Example 1
Input: nums = [0, 1, 2, 3, 4], queries = [[3, 1], [1, 3], [5, 6]]
Output: [3, 3, 7]
Explanation:
For query [3, 1], only 0 and 1 are allowed, and the best value is 3 XOR 0 = 3.
For query [1, 3], allowed numbers are 0, 1, 2, 3, and the best value is 1 XOR 2 = 3.
For query [5, 6], all numbers are allowed, and the best value is 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]
Explanation:
For query [12, 4], allowed numbers are 2, 4, 3, and the best value is 12 XOR 3 = 15.
For query [8, 1], no number is allowed, so the answer is -1.
For query [6, 3], allowed numbers are 2, 3, and the best value is 6 XOR 3 = 5.
Brute Force Approach
The first natural thought is very direct. For every query, check every number in nums. If the number is within the limit m, compute its XOR with x and keep the maximum. This idea comes immediately from the problem statement because the question is asking, "among all valid numbers, which one gives the biggest XOR?"
So the most straightforward way is:
test every candidate
ignore invalid numbers
keep the best answer
Algorithm
Create an answer list to store the result for each query.
Process queries one by one because each query has its own
xandm.For the current query, start with
best = -1. This is important because if no valid number is found,-1should remain the final answer.Traverse the full
numsarray and check whether the current number is less than or equal tom. This condition is necessary because the query only allows such numbers.If the number is valid, compute
x XOR num. This is the value the problem wants to maximize.Compare that XOR value with
best, and keep the larger one so the best answer seen so far is never lost.After checking all numbers for that query, store
bestin the answer list.Return the final answer list after all queries are processed.
Dry Run
Maximum Xor with One Element from Array Brute Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Returns the maximum XOR answer for each query by checking every valid number directly. */ vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) { // Store one answer for each query. vector<int> answer; // Process each query one by one. for (const vector<int>& query : queries) { // Extract the query number whose XOR is needed. int x = query[0]; // Extract the largest allowed value from nums for this query. int m = query[1]; // Keep -1 so it stays the answer when no valid number exists. int best = -1; // Check every number because any one of them could be the best valid partner. for (int num : nums) { // Use only numbers that satisfy the query limit. if (num <= m) { // Compute the XOR value made with the current valid number. int currentXor = x ^ num; // Keep the largest XOR value found for this query. if (currentXor > best) { best = currentXor; } } } // Store the final answer for the current query. answer.push_back(best); } return answer; }};// Driver code startsint main() { vector<int> nums = {0, 1, 2, 3, 4}; vector<vector<int>> queries = {{3, 1}, {1, 3}, {5, 6}}; Solution obj; vector<int> answer = obj.maximizeXor(nums, queries); for (int value : answer) { cout << value << " "; } cout << endl; return 0;}Complexity Analysis
Time Complexity: O(N * Q), because each query scans all numbers.
Space Complexity: O(1) extra space apart from the output array.
Optimal Approach
The slow part in brute force is repeating the same work for every query. That immediately raises a useful question: If two queries have similar limits, is it really necessary to scan the full array again and again? This question leads to the main observation. For a query with limit m, only numbers <= m matter.
So if queries are processed in increasing order of m, then once a number becomes valid, it will stay valid for all later queries with larger limits. This is the exact condition that suggests offline processing:
sort
numssort queries by
mkeep adding newly valid numbers as the limit grows
Now another question appears: Once all valid numbers are available, how can the best XOR with x be found quickly?
This is where the binary trie comes in. For XOR, a bit becomes 1 when the two bits are different. Since higher bits matter more than lower bits, the greedy thought is natural:
if the current bit of
xis0, try to find1if the current bit of
xis1, try to find0
That is exactly what a binary trie helps with. It stores numbers bit by bit, so for each query value x, the path can try the opposite bit first at every position.
So the full logic appears naturally from two conditions:
the limit condition suggests sorting queries by
mthe XOR maximization condition suggests a binary trie
Algorithm
Sort
numsin increasing order so valid numbers can be added in one direction only.Create a new list of queries in the form
(m, x, originalIndex). The original index is necessary because queries will be sorted, but the final answers must return in the original order.Sort this new query list by
m. This allows processing from the smallest limit to the largest limit.Create an empty binary trie. It will store only those numbers from
numsthat are currently valid for the query being processed.Keep a pointer
index = 0for thenumsarray. This pointer shows how many numbers have already been inserted into the trie.Process each sorted query one by one.
While
indexis still insidenumsandnums[index] <= m, insert that number into the trie and move the pointer forward. This step is done because those numbers are now valid for the current query and will also remain valid for future queries.Before searching in the trie, check whether any number has been inserted at all. If not, store
-1for that query because there is no valid number.Otherwise, search the trie using
x. At each bit from most significant to least significant, try to move to the opposite bit first because that would make the XOR bit1, which is always better at that position.If the opposite bit path does not exist, move to the same bit path because that is the only available choice.
Build the XOR value while moving through the trie, and store that result at the query's original index.
After all queries are processed, return the answer array.
Key Points
Sorting queries does not change the final output order because each query keeps its original index.
Each number from
numsis inserted into the trie only once.If no number is small enough for a query limit, the answer for that query is
-1.
Dry Run
Maximum Xor with one Element From Array Optimal Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class TrieNode {public: TrieNode* children[2]; // Create an empty trie node with no bit paths yet. TrieNode() { children[0] = nullptr; children[1] = nullptr; }};class BinaryTrie {private: TrieNode* root;public: // Create one empty trie. BinaryTrie() { root = new TrieNode(); } // Insert one number into the trie from bit 30 down to bit 0. void insert(int num) { TrieNode* node = root; for (int bit = 30; bit >= 0; bit--) { // Extract the current bit so the correct trie path can be used. int currentBit = (num >> bit) & 1; // Create the path only when this bit branch does not exist yet. if (node->children[currentBit] == nullptr) { node->children[currentBit] = new TrieNode(); } // Move to the next lower bit. node = node->children[currentBit]; } } // Find the largest XOR value possible with the given number. int getMaxXor(int num) { TrieNode* node = root; // Build the answer bit by bit. int maxXor = 0; for (int bit = 30; bit >= 0; bit--) { // Extract the current bit of the query number. int currentBit = (num >> bit) & 1; // The opposite bit is preferred because it would produce XOR bit 1. int oppositeBit = currentBit ^ 1; // Take the opposite path when it exists to improve the XOR result. if (node->children[oppositeBit] != nullptr) { maxXor |= (1 << bit); node = node->children[oppositeBit]; } else { // If the better path does not exist, continue with the available same-bit path. node = node->children[currentBit]; } } return maxXor; }};class Solution {public: /* Returns the maximum XOR answer for each query using offline sorting and a binary trie. */ vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) { // Sort numbers so valid values can be inserted gradually as limits grow. sort(nums.begin(), nums.end()); // Store answers in original query order. vector<int> answer(queries.size(), -1); // Store each query as {m, x, originalIndex} so sorting by limit becomes easy. vector<array<int, 3>> offlineQueries; for (int i = 0; i < (int)queries.size(); i++) { offlineQueries.push_back({queries[i][1], queries[i][0], i}); } // Process smaller limits first so inserted numbers never need to be removed. sort(offlineQueries.begin(), offlineQueries.end()); BinaryTrie trie; // Point to the next number in nums that has not been inserted yet. int index = 0; for (const auto& query : offlineQueries) { int m = query[0]; int x = query[1]; int originalIndex = query[2]; // Insert every number that becomes valid for the current limit. while (index < (int)nums.size() && nums[index] <= m) { trie.insert(nums[index]); index++; } // If no number has been inserted, this query has no valid answer. if (index == 0) { answer[originalIndex] = -1; } else { // Search only among valid inserted numbers and store the answer at the original position. answer[originalIndex] = trie.getMaxXor(x); } } return answer; }Complexity Analysis
Time Complexity: O(N x log N + Q log Q + (N + Q) x B)
Where N is the number of elements in nums, Q is the number of queries, and B = 31 represents the number of bits processed per integer (from bit 30 down to bit 0). Sorting the array takes O(N x log N), and sorting the offline queries takes O(Q x log Q). Across all queries, each number is inserted into the Trie at most once, taking O(N x B) total insertion time, while each query performs a Trie search taking O(B) time, contributing O(Q x B).
Space Complexity: O(N x B x 2 + Q)
Where N x B is the maximum number of Trie nodes created in the worst case (when no numbers share common binary prefixes), and Q is the space required to store the answer array and offline query structure. Because each TrieNode statically allocates an array of 2 child pointers (children[0] and children[1]) for binary choices, the structural Trie space scales directly as O(N x B x 2).
Interview follow-up Questions
Because the limit m decides which numbers are valid. After sorting queries by m, valid numbers can be inserted only once as the limit grows, instead of rebuilding the valid set again and again.
Be the first to add a comment.