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.

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

python

▶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

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.

06

Complexity

Time

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

Space

O(30n)

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