Maximum XOR With an Element From Array
Maximum Xor Of Two Numbers In An Array: each query (x, m) asks: max x XOR a over array elements a ≤ m (or −1 if none). Answer all queries fast.
- 1 <= nums.length, queries.length <= 10⁵
- queries[i].length == 2
- 0 <= nums[j], xi, mi <= 10⁹
Intuition
Maximum xor with an element from array answers queries of the form (x, m): the largest x XOR a over array elements a ≤ m, or −1 if none qualify. Without the m ceiling this is the standard bit-trie problem — the ceiling is what makes it Hard.
Recall the unconstrained version. Insert every number into a binary trie keyed by bits from the most significant down. To maximise x XOR a, walk the trie preferring at each level the branch holding the opposite bit to x's, since a differing bit contributes to the XOR and higher bits dominate. Greedy works because a single high bit outweighs every lower bit combined.
The ceiling breaks that directly: a trie holding all elements would happily return one exceeding m. Rebuilding a filtered trie per query is O(n) each and far too slow.
The fix is to process the queries offline — answer them in an order of your choosing rather than the order given:
- Sort the array ascending, sort the queries by their limit m, then sweep, inserting elements while they remain ≤ the current m.
Because both are sorted, the trie only ever grows. Every element eligible for an earlier query is eligible for a later one, so nothing is ever removed. When a query is processed, the trie contains exactly its permitted elements, and the ordinary greedy walk applies unchanged.
Remember to restore the original query order before returning, since the answers were computed out of sequence.
Offline processing: sort the queries by their limit and the array by value, then a single pointer admits elements into the trie as the limit grows. Each element is inserted once across all queries. Reordering queries when they arrive in an inconvenient order is the general technique.
Approach
Before reading on: price up what the brute force costs here, then ask what the shared prefixes let you avoid storing twice. Aim for O((n + q) log(n+q) + 30(n + q)) time and O(30n) space.
Recall the unconstrained bit-trie
Insert each number as a path of bits from most significant to least. To maximise the XOR with x, prefer the opposite bit at every level. A higher differing bit beats every lower bit combined, which is why the greedy choice is optimal.
See why the ceiling blocks reuse
A trie built over all elements can return a value above m, and filtering per query would cost O(n) rebuilds. The constraint changes per query, so no single static structure answers them all directly.
Sort both arrays to process offline
Sort nums ascending and sort the queries by m, keeping each query's original index. Answering queries out of order is allowed as long as the results are reordered at the end — that freedom is what makes the sweep possible.
Insert with a moving pointer
Before answering a query, advance a pointer inserting nums[ptr] while nums[ptr] <= m. Since m only increases across queries, the trie only ever grows and nothing is ever deleted — the constraint dissolves into insertion order.
Run the greedy walk per query
Walk 30 bits from the top, taking the opposite-bit branch when it exists and the same-bit branch otherwise. If the trie is still empty, no element is at or below m, so the answer is −1.
Restore the original order
Write each answer into the result array at the query's original index. Returning them in sorted-by-m order is the easy mistake, and it produces correct values attached to the wrong queries.
Cost of the offline sweep
Sorting is O(n log n + q log q); each element is inserted once and each query walks 30 levels, giving O((n + q) · 30) for the trie work. Space is O(n · 30) for the trie nodes.
Solution & live demo
Common pitfalls
Rebuilding the trie per query
for m, x, i in queries:
trie = build([v for v in nums if v <= m])while ptr < len(nums) and nums[ptr] <= m:
# insert into the shared trieThat's O(q · n · bits). Because the sorted limits only increase, the set of eligible elements only grows — so one shared trie and a monotone pointer insert each element exactly once.
Losing the original query order
return [answer for each sorted query]
qs = sorted([(m, x, i) for i, (x, m) in enumerate(queries)]) ... ans[i] = val
The output must line up with the input order, but processing happens in limit order. Carrying the original index through the sort and writing to ans[i] restores it.
Not handling an empty trie
node, val = root, 0 for b in range(29, -1, -1):
if not root: continue
When no element is at or below the limit, the answer is −1. Walking an empty trie dereferences missing children and either throws or returns a fabricated 0.
Edge cases
Nothing inserted yet — answer −1.
Insert both; identical paths are harmless.
Carry each query's original index through the sort.