You are given an integer array nums and a 2D array queries where each queries[i] = [x_i, m_i]. For each query, you need to find the maximum value of x_i ^ y where y is any element in nums such that y ≤ m_i. If no such y exists for a query, the answer should be -1.
Constraints:
y from nums as long as y ≤ m_i.nums may be large.
The brute-force approach would be, for each query, to check every element in nums that is less than or equal to m_i, compute x_i ^ y, and keep track of the maximum. However, this is inefficient when both nums and queries are large.
To optimize, we need a way to quickly find, for each x_i and m_i, the number in nums not exceeding m_i that maximizes x_i ^ y. Since XOR is bitwise, we can use a Trie (prefix tree) to efficiently find the best candidate for each query.
The key insight is to process queries in order of increasing m_i, and build the Trie incrementally as more nums become eligible for each query.
We use the following steps to solve the problem efficiently:
nums and queries:
nums in ascending order.queries by m_i, keeping track of their original indices so we can return answers in the original order.nums. Each node represents a bit (0 or 1).
nums that are less than or equal to m_i (incrementally, as m_i increases).
[x_i, m_i], if the Trie is empty (no eligible y), answer is -1.
x_i at each level (to maximize XOR).
This approach leverages the Trie for fast bitwise matching, and sorting to ensure we only insert necessary nums for each query.
Example:
nums = [0,1,2,3,4]
queries = [[3,1],[1,3],[5,6]]
Let's walk through each query:
nums: [0,1,2,3,4] (already sorted)queries by m_i: [[3,1],[1,3],[5,6]] (already sorted)
nums: [0,1] (≤1)x=3, try to maximize 3 ^ y:
nums: [0,1,2,3] (≤3)x=1:
nums: [0,1,2,3,4] (≤6)x=5:
Final Output: [3,3,7]
nums (O(N)), so total time is O(QN).nums: O(N log N)queries: O(Q log Q)
The problem asks for the maximum XOR of a given number with an element from an array, subject to a constraint. The naive approach is too slow, so we use a Trie to efficiently find the best candidate for each query. By sorting both nums and queries, and incrementally building the Trie, we ensure that each query only considers eligible numbers. The solution is elegant because it leverages bitwise properties and data structures to reduce time complexity from quadratic to nearly linear.
class TrieNode:
def __init__(self):
self.children = {}
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, num):
node = self.root
for i in range(31, -1, -1):
curr_bit = (num >> i) & 1
if curr_bit not in node.children:
node.children[curr_bit] = TrieNode()
node = node.children[curr_bit]
def getMaxXor(self, num):
node = self.root
if not node.children:
return -1
max_xor = 0
for i in range(31, -1, -1):
curr_bit = (num >> i) & 1
toggled_bit = 1 - curr_bit
if toggled_bit in node.children:
max_xor |= (1 << i)
node = node.children[toggled_bit]
else:
node = node.children.get(curr_bit, node)
return max_xor
class Solution:
def maximizeXor(self, nums, queries):
nums.sort()
queries = sorted([(mi, xi, idx) for idx, (xi, mi) in enumerate(queries)])
res = [0] * len(queries)
trie = Trie()
idx = 0
for mi, xi, q_idx in queries:
while idx < len(nums) and nums[idx] <= mi:
trie.insert(nums[idx])
idx += 1
res[q_idx] = trie.getMaxXor(xi)
return res
struct TrieNode {
TrieNode* children[2];
TrieNode() {
children[0] = children[1] = nullptr;
}
};
class Trie {
public:
TrieNode* root;
Trie() { root = new TrieNode(); }
void insert(int num) {
TrieNode* node = root;
for (int i = 31; i >= 0; --i) {
int bit = (num >> i) & 1;
if (!node->children[bit])
node->children[bit] = new TrieNode();
node = node->children[bit];
}
}
int getMaxXor(int num) {
TrieNode* node = root;
if (!node->children[0] && !node->children[1]) return -1;
int maxXor = 0;
for (int i = 31; i >= 0; --i) {
int bit = (num >> i) & 1;
int toggled = 1 - bit;
if (node->children[toggled]) {
maxXor |= (1 << i);
node = node->children[toggled];
} else if (node->children[bit]) {
node = node->children[bit];
}
}
return maxXor;
}
};
class Solution {
public:
vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
sort(nums.begin(), nums.end());
vector<tuple<int, int, int>> q;
int n = queries.size();
for (int i = 0; i < n; ++i)
q.push_back({queries[i][1], queries[i][0], i});
sort(q.begin(), q.end());
vector<int> res(n);
Trie trie;
int idx = 0;
for (auto& [mi, xi, qi] : q) {
while (idx < nums.size() && nums[idx] <= mi) {
trie.insert(nums[idx]);
++idx;
}
res[qi] = trie.getMaxXor(xi);
}
return res;
}
};
class TrieNode {
TrieNode[] children = new TrieNode[2];
}
class Trie {
TrieNode root = new TrieNode();
void insert(int num) {
TrieNode node = root;
for (int i = 31; i >= 0; --i) {
int bit = (num >> i) & 1;
if (node.children[bit] == null)
node.children[bit] = new TrieNode();
node = node.children[bit];
}
}
int getMaxXor(int num) {
TrieNode node = root;
if (node.children[0] == null && node.children[1] == null) return -1;
int maxXor = 0;
for (int i = 31; i >= 0; --i) {
int bit = (num >> i) & 1;
int toggled = 1 - bit;
if (node.children[toggled] != null) {
maxXor |= (1 << i);
node = node.children[toggled];
} else if (node.children[bit] != null) {
node = node.children[bit];
}
}
return maxXor;
}
}
class Solution {
public int[] maximizeXor(int[] nums, int[][] queries) {
Arrays.sort(nums);
int n = queries.length;
int[][] q = new int[n][3];
for (int i = 0; i < n; ++i) {
q[i][0] = queries[i][1]; // mi
q[i][1] = queries[i][0]; // xi
q[i][2] = i;
}
Arrays.sort(q, (a, b) -> Integer.compare(a[0], b[0]));
int[] res = new int[n];
Trie trie = new Trie();
int idx = 0;
for (int[] query : q) {
int mi = query[0], xi = query[1], qi = query[2];
while (idx < nums.length && nums[idx] <= mi) {
trie.insert(nums[idx]);
++idx;
}
res[qi] = trie.getMaxXor(xi);
}
return res;
}
}
class TrieNode {
constructor() {
this.children = {};
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(num) {
let node = this.root;
for (let i = 31; i >= 0; --i) {
let bit = (num >> i) & 1;
if (!(bit in node.children))
node.children[bit] = new TrieNode();
node = node.children[bit];
}
}
getMaxXor(num) {
let node = this.root;
if (Object.keys(node.children).length === 0) return -1;
let maxXor = 0;
for (let i = 31; i >= 0; --i) {
let bit = (num >> i) & 1;
let toggled = 1 - bit;
if (toggled in node.children) {
maxXor |= (1 << i);
node = node.children[toggled];
} else if (bit in node.children) {
node = node.children[bit];
}
}
return maxXor;
}
}
var maximizeXor = function(nums, queries) {
nums.sort((a, b) => a - b);
let q = queries.map(([xi, mi], idx) => [mi, xi, idx]);
q.sort((a, b) => a[0] - b[0]);
let res = Array(queries.length);
let trie = new Trie();
let idx = 0;
for (let [mi, xi, qi] of q) {
while (idx < nums.length && nums[idx] <= mi) {
trie.insert(nums[idx]);
idx++;
}
res[qi] = trie.getMaxXor(xi);
}
return res;
};