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.
Sort the array and for each query, use binary search to find the largest element <= m. Then compute the XOR for eligible numbers and find the maximum result.
This code first sorts the nums array and then performs a binary search to find the largest valid index for each query. The maximum XOR is calculated by iterating over valid elements only.
Time Complexity: O(n log n + q log n), where n is the number of elements in nums and q is the number of queries.
Space Complexity: O(1) excluding the space required for the output.
Build a Trie data structure to efficiently find the number that gives the maximum XOR with a given number. This is useful for queries constrained by a maximum value since it supports parts of operations in logarithmic time.
This code constructs a Trie to store the binary representation of numbers. For each query, it traverses the Trie to maximize the XOR. The query checks if adding a set bit (1) keeps the result below the xor threshold.
C
Time Complexity: O(n * MAX_BIT + q * MAX_BIT), where n is the array size, and q is the number of queries, MAX_BIT is the number of bits in the numbers.
Space Complexity: O(n * MAX_BIT), needed for Trie structure.
From the problem description, we know that each query is independent and the result of the query is irrelevant to the order of elements in nums. Therefore, we consider sorting all queries in ascending order of m_i, and also sorting nums in ascending order.
Next, we use a binary trie to maintain the elements in nums. We use a pointer j to record the current elements in the trie, initially j=0. For each query [x_i, m_i], we continuously insert elements from nums into the trie until nums[j] > m_i. At this point, we can query all elements not exceeding m_i in the trie, and we take the XOR value of the element with the maximum XOR value with x_i as the answer.
The time complexity is O(m times log m + n times (log n + log M)), and the space complexity is O(n times log M). Where m and n are the lengths of the arrays nums and queries respectively, and M is the maximum value in the array nums. In this problem, M \le 10^9.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Sorting and Binary Search | Time Complexity: O(n log n + q log n), where n is the number of elements in Space Complexity: O(1) excluding the space required for the output. |
| Approach 2: Trie Data Structure | Time Complexity: O(n * MAX_BIT + q * MAX_BIT), where n is the array size, and q is the number of queries, MAX_BIT is the number of bits in the numbers. Space Complexity: O(n * MAX_BIT), needed for Trie structure. |
| Offline Query + Binary Trie | — |
| 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 |
L7. Maximum XOR With an Element From Array | Queries | C++ | Java • take U forward • 80,399 views views
Watch 9 more video solutions →Practice Maximum XOR With an Element From Array with our built-in code editor and test cases.
Practice on FleetCode