LeetCode 1938 - Maximum Genetic Difference Query

LeetCode Problem 1938

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Bit Manipulation, Depth-First Search, Trie

Solution

Problem Understanding

The problem presents a rooted tree where each node is uniquely identified by an integer from 0 to n-1. This integer also represents the genetic value of the node. The tree structure is given by the parents array, where parents[i] indicates the parent of node i, and -1 indicates the root node.

For each query [nodei, vali], the task is to determine the maximum genetic difference between vali and any node value on the path from nodei to the root. The genetic difference is defined using the bitwise XOR operation. In other words, for each query, you traverse the path from the given node up to the root and find the node pi that maximizes vali XOR pi.

The output is an array where each entry corresponds to the maximum genetic difference for each query. The constraints indicate the problem involves large trees (up to 10^5 nodes) and a substantial number of queries (up to 3*10^4). Therefore, a naive approach that examines every path per query will be too slow.

Important edge cases include a tree that is highly skewed (all nodes in a single line), queries at the root node, and vali being 0 or the maximum allowed value.

Approaches

The brute-force approach involves, for each query, walking from the query node up to the root, computing vali XOR pi for each node pi on the path, and returning the maximum value. This is correct but inefficient because each query may take O(n) in the worst case if the tree is skewed, resulting in a total time complexity of O(n * q), which is unacceptable for the input size.

The optimal approach uses a Trie data structure specialized for XOR queries. The key insight is that a Trie can store binary representations of numbers, and by navigating the Trie greedily, we can find the number that maximizes XOR with a given value in O(log C), where C is the maximum value of the numbers. To make this work efficiently, we traverse the tree using DFS and dynamically add/remove node values from the Trie as we enter/exit each node, effectively limiting the Trie to only include ancestors of the current node.

Algorithm Walkthrough

1. Build the tree from the parents array. Create an adjacency list representing children for each node. Identify the root as the node with parent == -1.
2. Group queries by node. For efficient processing, map each node to a list of queries that need to be answered while visiting that node in DFS.
3. Implement a binary Trie with insertion, deletion, and max XOR query operations. Each Trie node keeps track of the count of numbers passing through it to allow dynamic removal during DFS backtracking.
4. DFS traversal of the tree. Start from the root:

• Insert the current node’s value into the Trie.
• Process all queries associated with this node by querying the Trie for the maximum XOR with vali.
• Recur for all children.
• Remove the current node’s value from the Trie before returning to the parent to maintain the invariant that the Trie contains only ancestors of the current node.

5. Collect results in the order of queries.

Why it works: The Trie always contains exactly the node values on the path from the current node to the root. Queries for each node are answered in this context, ensuring the path constraint is maintained. The greedy XOR traversal in the Trie guarantees the maximum XOR for each query.

Python Solution

from typing import List, Dict

class TrieNode:
    def __init__(self):
        self.children = {}
        self.count = 0

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, num: int):
        node = self.root
        for i in reversed(range(18)):  # numbers <= 2*10^5 fit in 18 bits
            bit = (num >> i) & 1
            if bit not in node.children:
                node.children[bit] = TrieNode()
            node = node.children[bit]
            node.count += 1
    
    def remove(self, num: int):
        node = self.root
        for i in reversed(range(18)):
            bit = (num >> i) & 1
            child = node.children[bit]
            child.count -= 1
            if child.count == 0:
                del node.children[bit]
                return
            node = child
    
    def max_xor(self, num: int) -> int:
        node = self.root
        xor_val = 0
        for i in reversed(range(18)):
            bit = (num >> i) & 1
            toggled_bit = 1 - bit
            if toggled_bit in node.children:
                xor_val |= (1 << i)
                node = node.children[toggled_bit]
            else:
                node = node.children.get(bit)
        return xor_val

class Solution:
    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:
        n = len(parents)
        tree = [[] for _ in range(n)]
        root = -1
        for i, p in enumerate(parents):
            if p == -1:
                root = i
            else:
                tree[p].append(i)
        
        node_to_queries: Dict[int, List[tuple]] = {}
        for idx, (node, val) in enumerate(queries):
            node_to_queries.setdefault(node, []).append((idx, val))
        
        ans = [0] * len(queries)
        trie = Trie()
        
        def dfs(node: int):
            trie.insert(node)
            for idx, val in node_to_queries.get(node, []):
                ans[idx] = trie.max_xor(val)
            for child in tree[node]:
                dfs(child)
            trie.remove(node)
        
        dfs(root)
        return ans

The implementation defines a Trie with counts for dynamic insertions and removals. DFS ensures only relevant nodes are in the Trie, and queries are answered efficiently with max_xor.

Go Solution

package main

type TrieNode struct {
	children [2]*TrieNode
	count    int
}

type Trie struct {
	root *TrieNode
}

func NewTrie() *Trie {
	return &Trie{root: &TrieNode{}}
}

func (t *Trie) Insert(num int) {
	node := t.root
	for i := 17; i >= 0; i-- {
		bit := (num >> i) & 1
		if node.children[bit] == nil {
			node.children[bit] = &TrieNode{}
		}
		node = node.children[bit]
		node.count++
	}
}

func (t *Trie) Remove(num int) {
	node := t.root
	for i := 17; i >= 0; i-- {
		bit := (num >> i) & 1
		child := node.children[bit]
		child.count--
		if child.count == 0 {
			node.children[bit] = nil
			return
		}
		node = child
	}
}

func (t *Trie) MaxXOR(num int) int {
	node := t.root
	xorVal := 0
	for i := 17; i >= 0; i-- {
		bit := (num >> i) & 1
		toggled := 1 - bit
		if node.children[toggled] != nil {
			xorVal |= 1 << i
			node = node.children[toggled]
		} else {
			node = node.children[bit]
		}
	}
	return xorVal
}

func maxGeneticDifference(parents []int, queries [][]int) []int {
	n := len(parents)
	tree := make([][]int, n)
	root := -1
	for i, p := range parents {
		if p == -1 {
			root = i
		} else {
			tree[p] = append(tree[p], i)
		}
	}

	nodeToQueries := make(map[int][][2]int)
	for idx, q := range queries {
		nodeToQueries[q[0]] = append(nodeToQueries[q[0]], [2]int{idx, q[1]})
	}

	ans := make([]int, len(queries))
	trie := NewTrie()

	var dfs func(int)
	dfs = func(node int) {
		trie.Insert(node)
		for _, q := range nodeToQueries[node] {
			ans[q[0]] = trie.MaxXOR(q[1])
		}
		for _, child := range tree[node] {
			dfs(child)
		}
		trie.Remove(node)
	}

	dfs(root)
	return ans
}

The Go solution mirrors the Python version. Go requires fixed-size arrays for children in the Trie and explicit slice initialization. The recursion handles dynamic Trie insertion and removal identically.

Worked Examples

Example 1

parents = [-1,0,1,1], queries = [[0,2],[3,2],[2,5]]

• Build tree: 0 is root