What is the main strategy for solving the Maximum XOR With an Element From Array problem?

The primary strategy is to efficiently compute the XOR for each query, using techniques like bitwise operations, Trie, or binary search to optimize the search for valid elements in `nums`.

How can the Trie help in solving this problem?

A Trie helps by allowing efficient prefix-based searches to quickly find the maximum XOR result for a given query, reducing the need to check every element in `nums`.

What is the time complexity for solving this problem with a Trie?

The time complexity for building the Trie is O(N * 32), and each query is handled in O(32) time, where N is the length of `nums`.

What is the space complexity of the Trie-based approach?

The space complexity for the Trie-based approach is O(N * 32), as each number is represented by its 32-bit binary representation in the Trie.

Can I optimize the solution if the array `nums` is already sorted?

Yes, sorting `nums` allows you to use binary search, which can significantly reduce the time complexity of each query to O(log N), making the solution more efficient.

#1707

Hard

auto_awesome数组·结合·位运算·操作

LeetCode 题解工作台

与数组中元素的最大异或值

给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ，其中 queries[i] = [x i , m i ] 。第 i 个查询的答案是 x i 和任何 nums 数组中不超过 m i 的元素按位异或（ XOR ）得到的最大值。换句话说，答案是 max(nums[j] XO…

数组位运算字典树

题目描述

给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ，其中 queries[i] = [x_i, m_i] 。

第 i 个查询的答案是 x_i 和任何 nums 数组中不超过 m_i 的元素按位异或（XOR）得到的最大值。换句话说，答案是 max(nums[j] XOR x_i) ，其中所有 j 均满足 nums[j] <= m_i 。如果 nums 中的所有元素都大于 m_i，最终答案就是 -1 。

返回一个整数数组 answer 作为查询的答案，其中 answer.length == queries.length 且 answer[i] 是第 i 个查询的答案。

示例 1：

输入：nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
输出：[3,3,7]
解释：
1) 0 和 1 是仅有的两个不超过 1 的整数。0 XOR 3 = 3 而 1 XOR 3 = 2 。二者中的更大值是 3 。
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.

示例 2：

输入：nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
输出：[15,-1,5]

提示：

1 <= nums.length, queries.length <= 10⁵
queries[i].length == 2
0 <= nums[j], x_i, m_i <= 10⁹

lightbulb

解题思路

方法一：离线查询 + 0-1 字典树

根据题目描述我们知道，每个查询相互独立，并且查询的结果与 $nums$ 中的元素顺序无关，因此，我们考虑将所有的查询按照 $m_i$ 从小到大排序，并且将 $nums$ 从小到大排序。

接下来，我们使用一个 $0-1$ 字典树来维护 $nums$ 中的元素。我们用一个指针 $j$ 来记录当前字典树中的元素，初始时 $j=0$ 。对于每个查询 $[x_i, m_i]$ ，我们不断地将 $nums$ 中的元素插入到字典树中，直到 $nums[j] > m_i$ ，此时我们就可以在字典树中查询到所有不超过 $m_i$ 的元素，我们将其中与 $x_i$ 异或值最大的元素的异或值作为答案。

时间复杂度 $O(m \times \log m + n \times (\log n + \log M))$ ，空间复杂度 $O(n \times \log M)$ ，其中 $m$ 和 $n$ 分别是数组 $nums$ 和 $queries$ 的长度，而 $M$ 是数组 $nums$ 中的最大值，本题中 $M \le 10^9$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

class Trie:
    __slots__ = ["children"]

    def __init__(self):
        self.children = [None] * 2

    def insert(self, x: int):
        node = self
        for i in range(30, -1, -1):
            v = x >> i & 1
            if node.children[v] is None:
                node.children[v] = Trie()
            node = node.children[v]

    def search(self, x: int) -> int:
        node = self
        ans = 0
        for i in range(30, -1, -1):
            v = x >> i & 1
            if node.children[v ^ 1]:
                ans |= 1 << i
                node = node.children[v ^ 1]
            elif node.children[v]:
                node = node.children[v]
            else:
                return -1
        return ans


class Solution:
    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        trie = Trie()
        nums.sort()
        j, n = 0, len(queries)
        ans = [-1] * n
        for i, (x, m) in sorted(zip(range(n), queries), key=lambda x: x[1][1]):
            while j < len(nums) and nums[j] <= m:
                trie.insert(nums[j])
                j += 1
            ans[i] = trie.search(x)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for the candidate's ability to leverage data structures like Tries or binary search for optimizing time complexity.
question_mark
Assess how well the candidate understands the role of bitwise operations in solving algorithmic problems efficiently.
question_mark
Evaluate the candidate’s approach to handling multiple queries within large input constraints.

warning

常见陷阱

外企场景

error
Overlooking edge cases where no elements of `nums` satisfy the condition, leading to returning an incorrect result.
error
Using brute-force approaches to evaluate all elements for each query without optimization.
error
Failing to properly handle the constraints, especially when `nums` and queries are large, which can result in time limit exceeded errors.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the maximum XOR result with a dynamic range for each query rather than a fixed `mi` value.
arrow_right_alt
Optimize for space by considering alternative data structures to store `nums` more efficiently.
arrow_right_alt
Modify the problem to allow for the XOR result to be maximized across multiple queries simultaneously, such as batch processing.

help

常见问题

外企场景

继续练习

#1803 统计异或值在范围内的数对有多少 #1938 查询最大基因差 #1178 猜字谜