Maximum XOR With an Element From Array: Offline Queries with a Trie

LeetCode Maximum XOR With an Element From Array (Problem 1707) gives you an array nums and a list of queries where each query is [xi, mi]. For each query, you need to find the maximum XOR of xi with any element in nums that does not exceed mi. If no such element exists, return -1 for that query.

For example, given nums = [0, 1, 2, 3, 5] and queries = [[3, 2], [1, 3], [5, 6]], the answers are [3, 3, 7]. The constraint on mi is what makes this harder than basic XOR maximization. You cannot simply consider every number in the array.

Why a trie?

XOR maximization maps naturally to a binary trie. You insert each number as a path of bits from the most significant bit (MSB) down to the least significant bit (LSB). To maximize the XOR with some query value x, you walk the trie greedily: at each level, try to follow the bit opposite to the current bit of x. Going opposite sets that bit to 1 in the XOR result, which is always better than setting it to 0.

This greedy approach works because higher bits contribute more to the final value. If you can set bit 29 in the result, that is worth more than setting all bits from 28 down to 0 combined. So you always prioritize the highest bit you can get.

Without the limit constraint, you would just build the trie from all elements and query it for each xi. But the limit mi means you can only use elements <= mi, which is where the offline trick comes in.

Handling the limit constraint

The key insight is to process queries offline, sorted by their limit mi. You also sort nums in ascending order. Then you iterate through the sorted queries. For each query, you insert all elements from nums that are <= mi into the trie (and you never remove them, since later queries have equal or larger limits). After inserting, you query the trie with xi to get the maximum XOR.

This works because sorting queries by mi ensures that every element you inserted for a previous query is still valid for the current one. The trie only grows, never shrinks. You track a pointer into the sorted nums array so each element is inserted exactly once across all queries.

If the trie is empty when you process a query (meaning no element in nums is <= mi), the answer for that query is -1.

Solution

def maximize_xor(nums: list[int], queries: list[list[int]]) -> list[int]:
    nums.sort()
    indexed_queries = sorted(enumerate(queries), key=lambda x: x[1][1])
    ans = [-1] * len(queries)
    trie = {}
    j = 0

    for idx, (xi, mi) in indexed_queries:
        while j < len(nums) and nums[j] <= mi:
            node = trie
            for bit in range(29, -1, -1):
                b = (nums[j] >> bit) & 1
                if b not in node:
                    node[b] = {}
                node = node[b]
            j += 1

        if not trie:
            continue

        node = trie
        curr_xor = 0
        for bit in range(29, -1, -1):
            b = (xi >> bit) & 1
            opposite = 1 - b
            if opposite in node:
                curr_xor |= 1 << bit
                node = node[opposite]
            else:
                node = node[b]
        ans[idx] = curr_xor

    return ans

Visual walkthrough

The walkthrough shows how queries processed in order of increasing mi let you reuse the same trie. Each query only adds elements, never removes them. The answer array is filled at each query's original index, so the final output matches the original query order.

Complexity analysis

Sorting nums takes O(n log n) and sorting queries takes O(q log q). Each element is inserted into the trie once, taking O(L) per element. Each query traversal also takes O(L). Since L is a constant (30 for values up to 10^9), the dominant terms are O(n log n + q log q + (n + q) * 30), which simplifies to O((n + q) * L). The trie uses at most O(n * L) nodes.

Building blocks

1. Binary trie for XOR maximization

The core technique is building a trie where each level represents a bit position. To maximize XOR with a query value, you greedily follow the opposite bit at each level. This same structure appears in Maximum XOR of Two Numbers in an Array and any problem where you need to find the element that maximizes XOR with a given number.

def query_trie(trie, x, num_bits=30):
    node = trie
    result = 0
    for bit in range(num_bits - 1, -1, -1):
        b = (x >> bit) & 1
        opposite = 1 - b
        if opposite in node:
            result |= 1 << bit
            node = node[opposite]
        else:
            node = node[b]
    return result

2. Offline query processing (sort by constraint)

When queries have varying constraints on which elements are eligible, sorting the queries by that constraint and processing them in order lets you build a data structure incrementally. You insert elements as they become eligible and never need to remove them. This pattern appears in problems like edge-length-limited paths, where you sort queries by the weight limit and add edges incrementally using a union-find structure.

indexed_queries = sorted(enumerate(queries), key=lambda x: x[1][1])
j = 0
for idx, (xi, mi) in indexed_queries:
    while j < len(nums) and nums[j] <= mi:
        insert_into_trie(trie, nums[j])
        j += 1
    ans[idx] = query_trie(trie, xi)

Edge cases

• No valid element: when all values in nums exceed mi, the trie is empty and you return -1 for that query
• Single element: the trie has exactly one path, so the XOR is xi ^ nums[0] (assuming nums[0] <= mi)
• All same numbers: every query against the same number yields XOR = xi ^ that_number
• mi equals zero: only nums elements equal to 0 are eligible, and xi ^ 0 = xi

From understanding to recall

This problem combines two patterns that show up independently in many interviews: binary trie traversal and offline query processing. Understanding each piece is not enough. You need to be able to wire them together under time pressure, remembering to sort queries by the limit, maintain the insertion pointer, and map answers back to original indices.

Spaced repetition drills this wiring. You write the solution from scratch today, revisit it in a few days, and again a week later. Each repetition reinforces the connection between "XOR with a constraint" and "offline trie." After a few reps, the pattern clicks instantly when you see a new variant.

Related posts

• Maximum XOR of Two Numbers in an Array - foundational binary trie XOR problem
• Implement Trie - trie data structure fundamentals
• Counting Bits - bit manipulation patterns