Watch 10 video solutions for Maximum XOR With an Element From Array, a hard level problem involving Array, Bit Manipulation, Trie. This walkthrough by take U forward has 80,399 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array nums consisting of non-negative integers. You are also given a queries array, where queries[i] = [xi, mi].
The answer to the ith query is the maximum bitwise XOR value of xi and any element of nums that does not exceed mi. In other words, the answer is max(nums[j] XOR xi) for all j such that nums[j] <= mi. If all elements in nums are larger than mi, then the answer is -1.
Return an integer array answer where answer.length == queries.length and answer[i] is the answer to the ith query.
Example 1:
Input: nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]] Output: [3,3,7] Explanation: 1) 0 and 1 are the only two integers not greater than 1. 0 XOR 3 = 3 and 1 XOR 3 = 2. The larger of the two is 3. 2) 1 XOR 2 = 3. 3) 5 XOR 2 = 7.
Example 2:
Input: nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]] Output: [15,-1,5]
Constraints:
1 <= nums.length, queries.length <= 105queries[i].length == 20 <= nums[j], xi, mi <= 109Problem Overview: You are given an integer array nums and queries [xi, mi]. For each query, choose a number from nums that is <= mi and maximize xi XOR num. If no valid number exists, return -1. The challenge is handling many queries efficiently while respecting the upper bound constraint.
Approach 1: Sorting and Binary Search (O(n log n + q log n + kq) time, O(1) extra space)
Start by sorting nums. For each query, use binary search to find the largest index where nums[i] <= mi. This gives the subset of values eligible for that query. Iterate through that prefix and compute xi ^ nums[j] for each candidate while tracking the maximum. The binary search reduces the filtering step from O(n) to O(log n), but the XOR scan can still reach O(n) in the worst case.
This approach is straightforward and works when constraints are small or when you want a quick baseline implementation. However, repeated scans across queries make it inefficient when both nums and queries are large.
Approach 2: Trie Data Structure (O((n + q) * 32) time, O(n * 32) space)
The optimal approach uses a bitwise Trie. Each node represents a bit (0 or 1). Insert numbers from nums bit by bit from the most significant bit (31) down to the least significant bit (0). While querying, greedily move toward the opposite bit to maximize the XOR value.
The constraint num <= mi is handled using an offline processing trick. Sort nums and sort queries by mi. As you process queries in increasing order of mi, insert all numbers from nums that satisfy the limit into the Trie. Then compute the maximum XOR for xi using the current Trie state. Each insertion and query takes about 32 steps because integers are 32-bit.
This technique combines ideas from array preprocessing, bit manipulation, and Trie traversal. The offline sorting ensures each number is inserted exactly once, keeping the algorithm efficient.
Recommended for interviews: The Trie-based solution is the expected answer for hard interview settings. It demonstrates understanding of bitwise optimization and offline query processing. A simpler sorted-array scan can show initial reasoning, but the Trie approach proves you can design scalable solutions under tight constraints.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting + Binary Search with Scan | O(n log n + q log n + nq) | O(1) | Simple baseline approach when constraints are small |
| Offline Queries + Bitwise Trie | O((n + q) * 32 + n log n + q log q) | O(n * 32) | Optimal solution for large inputs and interview scenarios |