Hard

Maximum XOR With an Element From Array

LAB

For each query [x,m], return the maximum x xor nums[i] where nums[i] <= m, or -1 if no value qualifies.

EXAMPLES

Example 1

Input
{
  "nums": [
    0,
    1,
    2,
    3,
    4
  ],
  "queries": [
    [
      3,
      1
    ],
    [
      1,
      3
    ],
    [
      5,
      6
    ]
  ]
}

Output
[
  3,
  3,
  7
]

FUNCTION SHAPE

nums: intArrayqueries: intMatrix→intArray

SOLUTION NOTE

This requires a trick where BECAUSE we have the queries all at once (ie, not ONLINE) we can sort them and answer them in an order most advantageous for us. We can sort the queries based on the limit value, and only add numbers in the array up to that limit to satisfy the requirement in the XOR_TRIE. Now, we just simply use the xor_trie, and re-wire the indices of the query into its original place.

Reveal reference solution +

pythonREFERENCE

class Trie:
    def __init__(self):
        self.children = {}

    def insert(self, num: int) -> None:
        node = self
        for i in range(31, -1, -1):
            c = (num >> i) & 1
            if c not in node.children: node.children[c] = Trie()
            node = node.children[c]

    def query(self, num: int) -> int:
        if not self.children: return -1  # NEED THIS IN CASE 0 INSERT() were called... ie. trie is empty

        node = self
        res = 0
        for i in range(31, -1, -1):
            c = (num >> i) & 1
            if 1 - c in node.children:  # going here will max the XOR
                node = node.children[1-c]
                res |= (1 << i)
            else:  # if there is at least one num in the trie, we are guaranteed either 1-c or c is in the children
                node = node.children[c]
        return res

class Solution:
    # sort both nums,queries. then two ptrs.
    # O(nlogn + mlogm)
    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        xor_trie = Trie()
        nums.sort()
        j = 0
        n = len(nums)

        queries = sorted(enumerate(queries), key=lambda x: x[1][1])
        res = [-1] * len(queries)

        for i, (x, m) in queries:
            while j < n and nums[j] <= m:
                xor_trie.insert(nums[j])
                j += 1
            if j > 0:  # need some value in the trie... if all nums[j] > m, answer is -1.
                res[i] = xor_trie.query(x)

        return res

TimeO(n log n + m log m)

SpaceO(n)

Open on LeetCode ↗