Maximum XOR With an Element — Offline Trie

Problem

Given nums and queries (xi, mi), find max XOR of xi with any nums[j] ≤ mi. Return -1 if no such element.

Approach — Offline Sorting + Binary Trie

Sort queries by mi and nums by value. Process queries in order, adding elements up to mi into trie before answering.

Time: O((n + q) * log(max_val)) | Space: O(n * 32)

Solutions

Python

class Solution:
    def maximizeXor(self, nums: list[int], queries: list[list[int]]) -> list[int]:
        nums.sort()
        sorted_q=sorted(enumerate(queries),key=lambda x:x[1][1])
        root={}
        def insert(n):
            node=root
            for b in range(31,-1,-1):
                bit=(n>>b)&1
                if bit not in node: node[bit]={}
                node=node[bit]
        def query(n):
            node=root; xr=0
            for b in range(31,-1,-1):
                bit=(n>>b)&1; want=1-bit
                if want in node: xr=(xr<<1)|1; node=node[want]
                else: xr<<=1; node=node[bit]
            return xr
        res=[0]*len(queries); j=0
        for idx,(x,m) in sorted_q:
            while j<len(nums) and nums[j]<=m:
                insert(nums[j]); j+=1
            res[idx]=query(x) if root else -1
        return res

Complexity

Time: O((n+q) * 32) | Space: O(n * 32)