LeetCode Solutions Blog

Maximum Genetic Difference Query

Difficulty: Hard

Problem Description

Given a rooted tree consisting of n nodes where each node's number denotes its unique genetic value, you need to find the maximum genetic difference defined as the bitwise-XOR of the genetic value of any node on the path from a given node to the root and a specified value for multiple queries.

Key Insights

The genetic difference is calculated using the bitwise-XOR operation.
Each node's value corresponds to its index in the parents array.
Queries require traversing from the specified node to the root to gather all genetic values.
Efficiently finding the maximum XOR can be achieved using data structures like a Trie.

Space and Time Complexity

Time Complexity: O(n + q * log(n)) where n is the number of nodes and q is the number of queries.
Space Complexity: O(n) for storing the tree structure and additional space for the Trie if used.

Solution

To solve this problem, we can follow these steps:

Build the tree using the parents array to determine the child-parent relationships.
For each query, traverse the path from the specified node to the root, collecting the genetic values.
Use a Trie data structure to efficiently calculate the maximum XOR for the collected values and the given value from the query.

Here’s how the Trie is constructed:

Insert all genetic values from the path into the Trie.
For each query, traverse the Trie to find the value that maximizes the XOR with the given value.

Code Solutions

class TrieNode:
    def __init__(self):
        self.children = {}
        
class Trie:
    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, num):
        node = self.root
        for i in range(31, -1, -1):  # Assuming 32-bit integers
            bit = (num >> i) & 1
            if bit not in node.children:
                node.children[bit] = TrieNode()
            node = node.children[bit]
            
    def find_max_xor(self, num):
        node = self.root
        max_xor = 0
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            # Try to take the opposite bit to maximize XOR
            toggled_bit = 1 - bit
            if toggled_bit in node.children:
                max_xor |= (1 << i)
                node = node.children[toggled_bit]
            else:
                node = node.children[bit]
        return max_xor

def max_genetic_difference(parents, queries):
    from collections import defaultdict
    
    n = len(parents)
    tree = defaultdict(list)
    for child, parent in enumerate(parents):
        if parent != -1:
            tree[parent].append(child)
    
    # To store the results for the queries
    results = []
    
    for node, val in queries:
        # Collect all genetic values on the path from node to root
        path_values = []
        current = node
        while current != -1:
            path_values.append(current)
            current = parents[current]
        
        # Insert all path values into the Trie
        trie = Trie()
        for value in path_values:
            trie.insert(value)
        
        # Find the maximum XOR for the current query
        max_xor = trie.find_max_xor(val)
        results.append(max_xor)
    
    return results