{x}
blog image

Maximum XOR With an Element From Array

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 <= 105
  • queries[i].length == 2
  • 0 <= nums[j], xi, mi <= 109

Solution Explanation: Maximum XOR With an Element From Array

This problem asks to find the maximum bitwise XOR between a query value and an element from an array, with the constraint that the array element must be less than or equal to a given limit for each query. A naive approach would have a time complexity of O(N*M), where N is the length of nums and M is the length of queries. This is computationally expensive for large inputs. The optimal solution leverages a combination of sorting and a Trie data structure to achieve a significantly better time complexity.

Approach:

  1. Offline Processing and Sorting: The queries are independent; their order doesn't affect the result. We sort the queries based on their upper limits (m_i) in ascending order. This allows us to process queries efficiently by iteratively adding elements from nums to the Trie as we encounter higher limits. We also sort nums in ascending order to optimize the insertion process into the Trie.

  2. Binary Trie: A binary Trie (prefix tree) is used to efficiently store and search for the maximum XOR value. Each node in the Trie represents a bit (0 or 1) in the binary representation of a number. By traversing the Trie, we can find the number that maximizes the XOR with the query value.

  3. Iterative Insertion and Search: We maintain a pointer j to iterate through nums. As we process queries, we add elements from nums to the Trie only if they are less than or equal to the current query's limit (m_i). This ensures that we only consider eligible numbers for each query. After inserting elements up to the current limit, we use the Trie to search for the number that produces the maximum XOR with the query value (x_i).

Time Complexity Analysis:

  • Sorting nums and queries: O(N log N + M log M)
  • Trie insertion: Each number in nums is inserted into the Trie. The insertion time for each number is proportional to the number of bits in the number (typically 32 bits for integers), resulting in O(N * log M) where M is the maximum value in nums.
  • Trie search: For each query, a search is performed in the Trie. The search time is proportional to the number of bits, giving O(M * log M).

Therefore, the overall time complexity is dominated by the sorting and Trie operations, resulting in O(N log N + M log M + N log M). In practice, log M is often a constant (32 bits), simplifying the complexity to O(N log N + M log M).

Space Complexity Analysis:

The space complexity is primarily determined by the size of the Trie. In the worst case, the Trie could store all numbers from nums, with each number using a space proportional to the number of bits (log M). Therefore, the space complexity is O(N log M). Again, log M is often a small constant.

Code Explanations (Python example):

The Python code demonstrates the algorithm. The Trie class implements the Trie data structure with insert and search methods. The Solution class's maximizeXor method handles the sorting, iterative processing, and result aggregation. Other languages will have similar structures.

The key idea is the efficient use of offline query processing and the Trie data structure for fast XOR maximization. This significantly improves the performance compared to a brute-force approach.