LeetCode #1707 Hard

Maximum XOR With an Element From Array

Each query (x, m) asks: max x XOR a over array elements a ≤ m (or −1 if none). Answer all queries fast.

triebit-manipulationoffline-queriessorting

02

Intuition

This is problem 421 with a ceiling. Handle it offline: sort the array, and sort queries by their limit m. Sweep queries in increasing m, inserting array elements into the bit-trie only while they are ≤ m. Each query then greedily walks a trie that contains exactly its allowed elements — the constraint dissolves into insertion order.

How to spot this pattern

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.

03

Approach

1

Constraint blocks direct reuse

The 421 trie answers 'max XOR with anything'. The a ≤ m filter differs per query, so a static trie over-answers. Rebuilding per query is O(n) each — too slow.

2

Offline sweep

Sort nums ascending; sort queries by m (remembering original indices). A pointer inserts nums[ptr] while nums[ptr] ≤ m. Trie contents = exactly the eligible elements — no removal ever needed.

3

Greedy query as before

Walk 30 bits top-down preferring the opposite bit. Empty trie (m below the minimum element) → −1.

04

Solution & live demo

▶1class Solution:
▶2    def maximizeXor(self, nums, queries):
▶3        nums.sort()
▶4        qs = sorted([(m, x, i) for i, (x, m) in enumerate(queries)])
▶5        root, ans, ptr = {}, [-1] * len(queries), 0
▶6        for m, x, i in qs:
▶7            while ptr < len(nums) and nums[ptr] <= m:   # admit eligible elements
▶8                node = root
▶9                for b in range(29, -1, -1):
▶10                    node = node.setdefault((nums[ptr] >> b) & 1, {})
▶11                ptr += 1
▶12            if not root: continue                        # no element <= m
▶13            node, val = root, 0
▶14            for b in range(29, -1, -1):
▶15                bit = (x >> b) & 1
▶16                if 1 - bit in node:
▶17                    val |= (1 << b); node = node[1 - bit]
▶18                else:
▶19                    node = node[bit]
▶20            ans[i] = val
▶21        return ans

05

Common pitfalls

Rebuilding the trie per query

✗ Wrong

for m, x, i in queries:
    trie = build([v for v in nums if v <= m])

✓ Right

while ptr < len(nums) and nums[ptr] <= m:
    # insert into the shared trie

That'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

✗ Wrong

return [answer for each sorted query]

✓ Right

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

✗ Wrong

node, val = root, 0
for b in range(29, -1, -1):

✓ Right

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.

06

Edge cases

m smaller than every element

Nothing inserted yet — answer −1.

Duplicate elements

Insert both; identical paths are harmless.

Answers must return in input order

Carry each query's original index through the sort.

07

Complexity

Time

O((n + q) log(n+q) + 30(n + q))

Space

O(30n)

Sorts plus one trie insert/walk per element/query.