LeetCode Solutions Blog

Maximum XOR With an Element From Array

Number: 1826

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an array of non-negative integers, nums, and a list of queries where each query is a pair [x, m], the goal is to find for each query the maximum XOR value of x with any number from nums that is less than or equal to m. If no number in nums meets the condition for a query, return -1 for that query.

Key Insights

Sort the nums array and process queries offline based on the m value.
Use a binary Trie (prefix tree) to efficiently compute maximum XOR for a given x.
Iteratively add elements from nums into the Trie which are valid for each query (i.e., nums[j] <= m).
The optimal bit-wise approach takes advantage of XOR properties by always trying to choose the opposite bit to maximize the result.

Space and Time Complexity

Time Complexity: O((n + q) * L) where L (≈32) is the number of bits, plus the sorting cost O(n log n + q log q).
Space Complexity: O(n * L) for the Trie.

Solution

We first sort the nums array. Next, we attach the original index to each query and sort the queries based on m. As we process each query in increasing order of m, we insert numbers from nums that are <= current m into our Trie. For each query, we then use the Trie to compute the maximum XOR value with x. If the Trie is empty (i.e., no valid number found), we return -1 for that query. This approach guarantees that each number is inserted only once and every query is answered in O(L) time.

Code Solutions

# Define the Trie node class
class TrieNode:
    def __init__(self):
        # Dictionary to hold children for bit 0 and 1
        self.child = {}

# Define the Trie data structure with insertion and maximum XOR query operations
class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    # Insert the binary representation of a number into the Trie
    def insert(self, num):
        node = self.root
        for i in range(31, -1, -1):  # Process bits from MSB to LSB
            bit = (num >> i) & 1  # Extract the i-th bit
            if bit not in node.child:
                node.child[bit] = TrieNode()
            node = node.child[bit]
    
    # Compute the maximum XOR value for a given num with numbers stored in the Trie
    def maxXor(self, num):
        node = self.root
        # If Trie is empty, return -1
        if not node.child:
            return -1
        max_xor = 0
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            toggled_bit = 1 - bit  # We prefer the opposite bit for maximizing XOR
            if toggled_bit in node.child:
                max_xor |= (1 << i)
                node = node.child[toggled_bit]
            elif bit in node.child:
                node = node.child[bit]
            else:
                return -1
        return max_xor

# Main function to process queries and return results
def maximizeXor(nums, queries):
    nums.sort()  # Sort nums for easier processing
    # Attach original indices to queries and sort by the m value
    queries = [(x, m, i) for i, (x, m) in enumerate(queries)]
    queries.sort(key=lambda a: a[1])
    answers = [-1] * len(queries)
    trie = Trie()
    index = 0
    n = len(nums)
    # Process each query: insert eligible numbers into the Trie and query maxXor
    for x, m, q_index in queries:
        while index < n and nums[index] <= m:
            trie.insert(nums[index])
            index += 1
        if trie.root.child:
            answers[q_index] = trie.maxXor(x)
        else:
            answers[q_index] = -1
    return answers

# Example usage:
if __name__ == "__main__":
    nums = [0, 1, 2, 3, 4]
    queries = [[3, 1], [1, 3], [5, 6]]
    result = maximizeXor(nums, queries)
    print(result)  # Expected Output: [3, 3, 7]