Maximum XOR With an Element From Array — Offline Binary Trie
Sanjeev SharmaAdvertisement
Problem Statement
LeetCode 1707 — Maximum XOR With an Element From Array | Difficulty: Hard
You are given an array nums of non-negative integers and an array queries where queries[i] = [xi, mi].
The answer to the i-th 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 of nums are larger than mi, the answer is -1.
Return an integer array answer where answer[i] is the answer to the i-th query.
Example:
Input: nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
Output: [3, 3, 7]
Query (3,1): elements <= 1 are {0,1}. max(3^0, 3^1) = max(3,2) = 3.
Query (1,3): elements <= 3 are {0,1,2,3}. max(1^0,1^1,1^2,1^3) = max(1,0,3,2) = 3.
Query (5,6): elements <= 6 are all of nums. max(5^0..5^4) = 5^2 = 7.Constraints:
1 <= nums.length, queries.length <= 10^50 <= nums[i], xi, mi <= 10^9
Why This Problem Matters
Maximum XOR With an Element From Array is the canonical "offline + binary XOR trie" interview problem. It is a hard variant of LeetCode 421 (Maximum XOR of Two Numbers) and shows up in Google, Codeforces problem sets, and competitive-style FAANG rounds. The problem layers two of the most powerful trie patterns:
- Binary trie for greedy bit-by-bit XOR maximisation.
- Offline processing (sort queries by their bound
mi, insert elements lazily) to avoid the impossible "trie indexed by value" data structure.
Mastering this problem teaches you both the XOR-trie greedy walk and the offline sweep pattern — primitives that combine to answer entire families of bit-manipulation queries in O((n + q) times log V).
The Core Insight
Two ideas compose:
Binary trie for max XOR. Insert each integer's 32-bit binary representation from the most significant bit. To find the integer that maximises x XOR n, walk the trie greedily: at each bit, prefer the opposite bit from x if it exists (forces a 1 in the XOR result at that position); otherwise take whatever exists. This gives the optimal max-XOR partner in O(32) per query.
Offline sweep for the nums[j] <= mi constraint. A naive trie cannot answer "max XOR among values ≤ mi" — the trie does not store value ranges efficiently. The trick: sort queries by mi ascending, sort nums ascending, and process queries in order. Maintain a pointer j into sorted nums. For each query (x, m), advance j inserting all nums[j] <= m into the trie, then run the standard max-XOR walk.
Because both arrays are sorted, every element gets inserted at most once across all queries → total inserts O(n times 32). Total queries O(q times 32). Final complexity: O((n + q) times 32).
Visual Dry Run
nums = [0,1,2,3,4] sorted; queries = [[3,1],[1,3],[5,6]].
Sort queries by m: [(idx=0,3,1), (idx=1,1,3), (idx=2,5,6)].
Query (idx=0, x=3, m=1):
Insert nums up to <= 1: insert 0, 1. Trie has {0,1}.
Walk x=3 = 011: greedy → flip each bit → result 011 ^ 100 not feasible, settle on 1
→ 3 XOR 0 = 3, 3 XOR 1 = 2 → max = 3.
Query (idx=1, x=1, m=3):
Insert nums up to <= 3: insert 2, 3. Trie has {0,1,2,3}.
Walk x=1 = 001: greedy → 1 XOR 2 = 3 (best).
Query (idx=2, x=5, m=6):
Insert nums up to <= 6: insert 4. Trie has {0,1,2,3,4}.
Walk x=5 = 101: greedy → 5 XOR 2 = 7 (best).Reorder by original index: [3, 3, 7].
The trie at the end of all queries contains every nums element. Each insert happened at most once.
Solution (Optimal) — Offline Sweep + Binary Trie
Python
class Solution:
def maximizeXor(self, nums: list[int], queries: list[list[int]]) -> list[int]:
nums.sort()
# Pair each query with its original index, sort by mi.
sorted_q = sorted(((i, x, m) for i, (x, m) in enumerate(queries)),
key=lambda t: t[2])
BITS = 30 # values <= 10^9 fit in 30 bits
root = {}
def insert(n: int):
node = root
for b in range(BITS, -1, -1):
bit = (n >> b) & 1
if bit not in node:
node[bit] = {}
node = node[bit]
def max_xor(x: int) -> int:
if not root: return -1
node = root
xr = 0
for b in range(BITS, -1, -1):
bit = (x >> b) & 1
want = 1 - bit
if want in node:
xr = (xr << 1) | 1
node = node[want]
else:
xr <<= 1
node = node[bit]
return xr
ans = [0] * len(queries)
j = 0
for orig_idx, x, m in sorted_q:
while j < len(nums) and nums[j] <= m:
insert(nums[j])
j += 1
ans[orig_idx] = max_xor(x) if root else -1
return ansJavaScript
var maximizeXor = function(nums, queries) {
nums.sort((a, b) => a - b);
const sortedQ = queries
.map((q, i) => [i, q[0], q[1]])
.sort((a, b) => a[2] - b[2]);
const BITS = 30;
const root = {};
const insert = (n) => {
let node = root;
for (let b = BITS; b >= 0; b--) {
const bit = (n >> b) & 1;
if (!node[bit]) node[bit] = {};
node = node[bit];
}
};
const maxXor = (x) => {
if (Object.keys(root).length === 0) return -1;
let node = root, xr = 0;
for (let b = BITS; b >= 0; b--) {
const bit = (x >> b) & 1;
const want = 1 - bit;
if (node[want] !== undefined) {
xr = (xr << 1) | 1;
node = node[want];
} else {
xr <<= 1;
node = node[bit];
}
}
return xr;
};
const ans = new Array(queries.length).fill(0);
let j = 0;
for (const [origIdx, x, m] of sortedQ) {
while (j < nums.length && nums[j] <= m) {
insert(nums[j]);
j++;
}
ans[origIdx] = Object.keys(root).length ? maxXor(x) : -1;
}
return ans;
};Complexity
- Time: O((n + q) times 32) — each element inserted once across all queries, each query walks 32 bits.
- Space: O(n times 32) for trie nodes in the worst case.
Common Mistakes
- Inserting all of
numsfirst, then querying — wrong; the trie cannot filter bynums[j] <= miafter the fact. - Forgetting to track original query order — sorted queries return answers in sorted-mi order; you must remap to original indices.
- Iterating bits low-to-high — the greedy max-XOR walk requires high-to-low (most significant bit first).
- Returning
0instead of-1when trie is empty — empty trie means no element ≤ mi, the spec says return-1. - Using too few bits (e.g., 20) — values up to 10^9 need 30 bits; off-by-one here causes wrong answers.
- Re-sorting nums or queries inside the query loop — kills the O((n+q) times 32) guarantee.
Interview Tips
- Begin with the unbounded variant (LeetCode 421): "Without
mi, this is a plain XOR trie; answer in O(32) per query." - Introduce the bound: "The challenge is the
nums[j] <= mifilter. We cannot prune the trie after building it." - Pitch the offline sweep: "Sort queries by
mi, sort nums, sweep the pointer." - State the invariant clearly: "After each query, the trie contains exactly the nums values ≤ current
mi." - Emphasise that each element gets inserted at most once — total inserts O(n times 32).
Follow-up Questions
- Online queries (cannot reorder)? Use a persistent trie indexed by sorted nums, or a wavelet tree.
- Find min XOR instead of max? Same trie; greedy walk picks the same bit at each level instead of the opposite.
- Range query: max XOR with
nums[j]in[lo, hi]? Persistent trie with version per element, query the difference. - Numbers up to 10^18? Increase BITS to 60; algorithm and complexity scale linearly with bit-width.
- What if duplicates in nums? No effect — duplicates may be inserted multiple times harmlessly, or skipped via a seen set.
Key Takeaways
- Max XOR with bounded element = binary trie + offline sort-by-bound sweep.
- Sort queries by
mi, sortnums; advance a pointer inserting elements before answering each query. - Greedy bit-by-bit walk: at each MSB-first step, prefer the opposite bit to maximise the XOR.
- Total complexity O((n + q) times 32); each element inserted at most once.
- Map sorted-query results back to original indices before returning.
- The offline-trie sweep pattern reappears in persistent tries, range XOR queries, and competitive bit-manipulation problems at FAANG and Codeforces.
Advertisement
