Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Maximum Genetic Difference Query solution and explanation

HardArrayBit ManipulationDepth-First SearchHash Table8 min read48.6% acceptanceUpdated 24 Mar 2026
Asked atMedianet
Practise Maximum Genetic Difference Query
33:45
LeetCode 1938. Maximum Genetic Difference QueryHappy Coding · 33:45 · 1K viewsWatch on YouTube
3 more videos on this problem
  1. LeetCode 1938. Maximum Genetic Difference QueryHappy Coding · 33:45 · 1K views
  2. 【每日一题】1938. Maximum Genetic Difference Query, 7/24/2021Huifeng Guan · 45:49 · 535 views
  3. 1938. Maximum Genetic Difference Query (Leetcode Hard)Programming Live with Larry · 46:34 · 501 views
  4. LeetCode 1938: Maximum Genetic Difference QueryAlitaCode · 36:06 · 16 views

The problem

There is a rooted tree consisting of n nodes numbered 0 to n - 1. Each node's number denotes its unique genetic value (i.e. the genetic value of node x is x). The genetic difference between two genetic values is defined as the bitwise-XOR of their values. You are given the integer array parents, where parents[i] is the parent for node i. If node x is the root of the tree, then parents[x] == -1.

You are also given the array queries where queries[i] = [nodei, vali]. For each query i, find the maximum genetic difference between vali and pi, where pi is the genetic value of any node that is on the path between nodei and the root (including nodei and the root). More formally, you want to maximize vali XOR pi.

Return an array ans where ans[i] is the answer to the ith query.

Example 1:

Input: parents = [-1,0,1,1], queries = [[0,2],[3,2],[2,5]]
Output: [2,3,7]
Explanation: The queries are processed as follows:
- [0,2]: The node with the maximum genetic difference is 0, with a difference of 2 XOR 0 = 2.
- [3,2]: The node with the maximum genetic difference is 1, with a difference of 2 XOR 1 = 3.
- [2,5]: The node with the maximum genetic difference is 2, with a difference of 5 XOR 2 = 7.

Example 2:

Input: parents = [3,7,-1,2,0,7,0,2], queries = [[4,6],[1,15],[0,5]]
Output: [6,14,7]
Explanation: The queries are processed as follows:
- [4,6]: The node with the maximum genetic difference is 0, with a difference of 6 XOR 0 = 6.
- [1,15]: The node with the maximum genetic difference is 1, with a difference of 15 XOR 1 = 14.
- [0,5]: The node with the maximum genetic difference is 2, with a difference of 5 XOR 2 = 7.

Constraints:

  • 2 <= parents.length <= 105
  • 0 <= parents[i] <= parents.length - 1 for every node i that is not the root.
  • parents[root] == -1
  • 1 <= queries.length <= 3 * 104
  • 0 <= nodei <= parents.length - 1
  • 0 <= vali <= 2 * 105

Approach overview

Problem Overview: You are given a rooted tree where each node represents a genetic value equal to its index. For every query [node, val], compute the maximum val XOR x where x is any ancestor of node (including the node itself). The challenge is answering many XOR queries efficiently while traversing the tree.

Approach 1: DFS with Trie (Time: O((n + q) * logV), Space: O(n * logV))

This approach performs a depth-first search over the tree while maintaining a binary Trie of the values on the current root-to-node path. When DFS enters a node, insert the node's value into the Trie. For every query attached to that node, compute the maximum XOR with val by greedily choosing the opposite bit at each level of the Trie (a classic bit manipulation trick). After processing children, remove the node value when backtracking so the Trie always reflects the active ancestor path.

The key insight: at any moment during DFS, the Trie contains exactly the ancestors of the current node. That means each query becomes a standard "maximum XOR with set" operation. Since values are bounded by node indices, the Trie depth is about 18–20 bits, making each insert, delete, and query very fast.

Approach 2: Preprocessing with Persistent Trie (Time: O((n + q) * logV), Space: O(n * logV))

This approach builds a persistent binary Trie for each node representing the set of values from the root to that node. Instead of modifying a single Trie during DFS, every insertion creates a new version that shares most of its structure with the previous one. The version for a node is derived from its parent's version with the node value inserted.

Each query simply uses the persistent Trie version corresponding to the queried node and performs the same maximum XOR lookup. Because nodes share structure between versions, memory growth stays manageable while avoiding insert/remove operations during traversal.

The persistent structure is especially useful when queries are independent of traversal order or when you want immutable versions of the ancestor sets. The lookup process is identical to a standard maximum XOR search in a binary Trie.

Recommended for interviews: DFS with Trie is the approach most interviewers expect. It demonstrates understanding of tree traversal, dynamic data structures, and XOR optimization. The persistent Trie version shows deeper knowledge of functional data structures and is more common in competitive programming or advanced system design discussions.

Approach 1: Approach 1: DFS with Trie

This approach uses a depth-first search (DFS) combined with a Trie data structure. The Trie is used to exploit the properties of XOR operations in order to efficiently find the maximum genetic difference for each query.

By traversing from the root to the queries' nodes, we can introduce the nodes into the trie as we traverse the DFS path. At each node where a query is made, we use the trie to efficiently get the maximum XOR with the given value by traversing the trie, looking for bits that will maximize the XOR value.

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

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, num):
        node = self.root
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            if bit not in node.children:
                node.children[bit] = TrieNode()
            node = node.children[bit]
            node.count += 1

    def erase(self, num):
        node = self.root
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            node = node.children[bit]
            node.count -= 1

    def getMaxXOR(self, num):
        node = self.root
        maxXOR = 0
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            oppositeBit = 1 - bit
            if oppositeBit in node.children and node.children[oppositeBit].count > 0:
                maxXOR |= (1 << i)
                node = node.children[oppositeBit]
            else:
                node = node.children[bit]
        return maxXOR


def maxGeneticDifference(parents, queries):
    from collections import defaultdict

    n = len(parents)
    tree = defaultdict(list)
    root = None
    for i in range(n):
        if parents[i] == -1:
            root = i
        else:
            tree[parents[i]].append(i)

    trie = Trie()
    queryMap = defaultdict(list)
    for i, (node, val) in enumerate(queries):
        queryMap[node].append((i, val))

    results = [0] * len(queries)

    def dfs(node):
        trie.insert(node)
        if node in queryMap:
            for idx, val in queryMap[node]:
                results[idx] = trie.getMaxXOR(val)
        for child in tree[node]:
            dfs(child)
        trie.erase(node)

    dfs(root)
    return results

# Example usage
parents = [-1, 0, 1, 1]
queries = [[0, 2], [3, 2], [2, 5]]
print(maxGeneticDifference(parents, queries))
import java.util.*;

class TrieNode {
    TrieNode[] children = new TrieNode[2];
    int count = 0;
}

class Trie {
    TrieNode root = new TrieNode();

    void insert(int num) {
        TrieNode node = root;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (node.children[bit] == null) {
                node.children[bit] = new TrieNode();
            }
            node = node.children[bit];
            node.count++;
        }
    }

    void erase(int num) {
        TrieNode node = root;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            node = node.children[bit];
            node.count--;
        }
    }

    int getMaxXOR(int num) {
        TrieNode node = root;
        int maxXOR = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int oppositeBit = 1 - bit;
            if (node.children[oppositeBit] != null && node.children[oppositeBit].count > 0) {
                maxXOR |= (1 << i);
                node = node.children[oppositeBit];
            } else {
                node = node.children[bit];
            }
        }
        return maxXOR;
    }
}

public class MaximumGeneticDifference {
    public static int[] maxGeneticDifference(int[] parents, int[][] queries) {
        int n = parents.length;
        List<List<Integer>> tree = new ArrayList<>();
        for (int i = 0; i < n; i++) tree.add(new ArrayList<>());
        int root = -1;
        for (int i = 0; i < n; i++) {
            if (parents[i] == -1) root = i;
            else tree.get(parents[i]).add(i);
        }

        Trie trie = new Trie();

        Map<Integer, List<int[]>> queryMap = new HashMap<>();
        for (int i = 0; i < queries.length; i++) {
            int node = queries[i][0];
            int val = queries[i][1];
            queryMap.computeIfAbsent(node, k -> new ArrayList<>()).add(new int[]{i, val});
        }

        int[] results = new int[queries.length];
        dfs(root, trie, tree, queryMap, results);

        return results;
    }

    private static void dfs(int node, Trie trie, List<List<Integer>> tree, Map<Integer, List<int[]>> queryMap, int[] results) {
        trie.insert(node);

        if (queryMap.containsKey(node)) {
            for (int[] q : queryMap.get(node)) {
                int idx = q[0];
                int val = q[1];
                results[idx] = trie.getMaxXOR(val);
            }
        }

        for (int child : tree.get(node)) {
            dfs(child, trie, tree, queryMap, results);
        }

        trie.erase(node);
    }

    public static void main(String[] args) {
        int[] parents = {-1, 0, 1, 1};
        int[][] queries = {{0, 2}, {3, 2}, {2, 5}};
        int[] results = maxGeneticDifference(parents, queries);
        for (int result : results) {
            System.out.print(result + " ");
        }
    }
}
#include <iostream>
#include <vector>
#include <limits>
using namespace std;

struct TrieNode {
    TrieNode* children[2] = {};
    int count = 0;
};

class Trie {
public:
    TrieNode* root = new TrieNode();

    void insert(int num) {
        TrieNode* node = root;
        for (int i = 31; i >= 0; --i) {
            int bit = (num >> i) & 1;
            if (!node->children[bit])
                node->children[bit] = new TrieNode();
            node = node->children[bit];
            node->count++;
        }
    }

    void erase(int num) {
        TrieNode* node = root;
        for (int i = 31; i >= 0; --i) {
            int bit = (num >> i) & 1;
            node = node->children[bit];
            --node->count;
        }
    }

    int getMaxXOR(int num) {
        TrieNode* node = root;
        int xorSum = 0;
        for (int i = 31; i >= 0; --i) {
            int bit = (num >> i) & 1;
            int oppositeBit = 1 - bit;
            if (node->children[oppositeBit] && node->children[oppositeBit]->count > 0) {
                xorSum |= (1 << i);
                node = node->children[oppositeBit];
            } else {
                node = node->children[bit];
            }
        }
        return xorSum;
    }
};

vector<int> dfs(int node, vector<vector<int>>& tree, vector<vector<pair<int, int>>>& queries, Trie& trie, vector<int>& parents, vector<int>& results) {
    trie.insert(node);
    for (auto& [queryIndex, val] : queries[node]) {
        results[queryIndex] = trie.getMaxXOR(val);
    }
    for (int child : tree[node]) {
        dfs(child, tree, queries, trie, parents, results);
    }
    trie.erase(node);
    return results;
}

vector<int> maxGeneticDifference(vector<int>& parents, vector<vector<int>>& queriesVec) {
    int n = parents.size();
    vector<vector<int>> tree(n);
    int root;
    for (int i = 0; i < n; ++i) {
        if (parents[i] == -1) root = i;
        else tree[parents[i]].push_back(i);
    }
    Trie trie;
    vector<vector<pair<int, int>>> queries(n);
    for (int i = 0; i < queriesVec.size(); ++i) {
        auto& q = queriesVec[i];
        queries[q[0]].push_back({i, q[1]});
    }
    vector<int> results(queriesVec.size());
    dfs(root, tree, queries, trie, parents, results);
    return results;
}

int main() {
    vector<int> parents = {-1, 0, 1, 1};
    vector<vector<int>> queries = {{0, 2}, {3, 2}, {2, 5}};
    vector<int> result = maxGeneticDifference(parents, queries);
    for (int res : result) {
        cout << res << " ";
    }
}
class TrieNode {
    constructor() {
        this.children = {};
        this.count = 0;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(num) {
        let node = this.root;
        for (let i = 31; i >= 0; i--) {
            let bit = (num >> i) & 1;
            if (!(bit in node.children)) {
                node.children[bit] = new TrieNode();
            }
            node = node.children[bit];
            node.count += 1;
        }
    }

    erase(num) {
        let node = this.root;
        for (let i = 31; i >= 0; i--) {
            let bit = (num >> i) & 1;
            node = node.children[bit];
            node.count -= 1;
        }
    }

    getMaxXOR(num) {
        let node = this.root;
        let maxXOR = 0;
        for (let i = 31; i >= 0; i--) {
            let bit = (num >> i) & 1;
            let oppositeBit = 1 - bit;
            if (oppositeBit in node.children && node.children[oppositeBit].count > 0) {
                maxXOR |= (1 << i);
                node = node.children[oppositeBit];
            } else {
                node = node.children[bit];
            }
        }
        return maxXOR;
    }
}

function maxGeneticDifference(parents, queries) {
    const n = parents.length;
    const tree = Array.from({ length: n }, () => []);
    let root;
    for (let i = 0; i < n; i++) {
        if (parents[i] === -1) root = i;
        else tree[parents[i]].push(i);
    }

    const trie = new Trie();
    const queryMap = new Map();
    queries.forEach(([node, val], index) => {
        if (!queryMap.has(node)) queryMap.set(node, []);
        queryMap.get(node).push([index, val]);
    });

    const results = Array(queries.length).fill(0);

    function dfs(node) {
        trie.insert(node);

        if (queryMap.has(node)) {
            queryMap.get(node).forEach(([index, val]) => {
                results[index] = trie.getMaxXOR(val);
            });
        }

        tree[node].forEach(dfs);
        trie.erase(node);
    }

    dfs(root);
    return results;
}

// Example Usage:
const parents = [-1, 0, 1, 1];
const queries = [[0, 2], [3, 2], [2, 5]];
console.log(maxGeneticDifference(parents, queries)); // [2, 3, 7]
using System;
using System.Collections.Generic;

class TrieNode {
    public TrieNode[] Children = new TrieNode[2];
    public int Count = 0;
}

class Trie {
    public TrieNode Root = new TrieNode();

    public void Insert(int num) {
        TrieNode node = Root;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (node.Children[bit] == null) {
                node.Children[bit] = new TrieNode();
            }
            node = node.Children[bit];
            node.Count++;
        }
    }

    public void Erase(int num) {
        TrieNode node = Root;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            node = node.Children[bit];
            node.Count--;
        }
    }

    public int GetMaxXOR(int num) {
        TrieNode node = Root;
        int maxXOR = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int oppositeBit = 1 - bit;
            if (node.Children[oppositeBit] != null && node.Children[oppositeBit].Count > 0) {
                maxXOR |= (1 << i);
                node = node.Children[oppositeBit];
            } else {
                node = node.Children[bit];
            }
        }
        return maxXOR;
    }
}

public class MaxGeneticDiff {
    public static int[] MaxGeneticDifference(int[] parents, int[][] queries) {
        int n = parents.Length;
        List<int>[] tree = new List<int>[n];
        for (int i = 0; i < n; i++) tree[i] = new List<int>();
        int root = -1;
        for (int i = 0; i < n; i++) {
            if (parents[i] == -1) root = i;
            else tree[parents[i]].Add(i);
        }

        Trie trie = new Trie();
        Dictionary<int, List<(int, int)>> queryMap = new Dictionary<int, List<(int, int)>>();
        for (int i = 0; i < queries.Length; i++) {
            int node = queries[i][0];
            int val = queries[i][1];
            if (!queryMap.ContainsKey(node)) queryMap[node] = new List<(int, int)>();
            queryMap[node].Add((i, val));
        }

        int[] results = new int[queries.Length];
        DFS(root, trie, tree, queryMap, results);

        return results;
    }

    private static void DFS(int node, Trie trie, List<int>[] tree, Dictionary<int, List<(int, int)>> queryMap, int[] results) {
        trie.Insert(node);

        if (queryMap.ContainsKey(node)) {
            foreach (var query in queryMap[node]) {
                int idx = query.Item1;
                int val = query.Item2;
                results[idx] = trie.GetMaxXOR(val);
            }
        }

        foreach (int child in tree[node]) {
            DFS(child, trie, tree, queryMap, results);
        }

        trie.Erase(node);
    }

    public static void Main(string[] args) {
        int[] parents = { -1, 0, 1, 1 };
        int[][] queries = { new int[] { 0, 2 }, new int[] { 3, 2 }, new int[] { 2, 5 } };
        int[] result = MaxGeneticDifference(parents, queries);
        Console.WriteLine(string.Join(" ", result));
    }
}

The Python solution mirrors the C++ and Java approaches with a DFS using a trie. It processes queries for each node by looking up the maximum XOR using the trie. Nodes are inserted and erased from the trie according to their DFS traversal status to ensure query accuracy.

Complexity

Time Complexity: O(N * 32 + Q * 32) ~ O(N + Q), controlled by the maximum bit operations in the Trie and the number of nodes and queries.

Space Complexity: O(32 * N), based on the Trie management during the DFS.

Try this approach in the editor

Approach 2: Approach 2: Preprocessing with Persistent Trie

This approach involves using a persistent Trie to support efficient query processing by maintaining versions of the Trie for each node in the tree. It leverages the persistence to avoid repeated computations in individual DFS traversals.

By maintaining versions of the Trie, we can avoid the need to insert and remove nodes dynamically within a single traversal, aiming to optimize the retrieval process of the maximum XOR value for varied inputs.

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

class PersistentTrie:
    def __init__(self):
        self.versions = [PersistentTrieNode()]

    def insert(self, node, num, depth=31):
        if node is None:
            node = PersistentTrieNode()
        if depth == -1:
            node.count += 1
            return node
        bit = (num >> depth) & 1
        node.children[bit] = self.insert(node.children.get(bit), num, depth - 1)
        node.count = (node.children.get(0, PersistentTrieNode()).count + node.children.get(1, PersistentTrieNode()).count)
        return node

    def build_version(self, num):
        self.versions.append(self.insert(self.versions[-1], num))

    def get_max_xor(self, node, num):
        xor_sum = 0
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            opposite_bit = 1 - bit
            if opposite_bit in node.children and node.children[opposite_bit].count > 0:
                xor_sum |= (1 << i)
                node = node.children[opposite_bit]
            else:
                node = node.children.get(bit, PersistentTrieNode())
        return xor_sum


def max_genetic_difference(parents, queries):
    from collections import defaultdict

    n = len(parents)
    tree = defaultdict(list)
    root = None
    for i in range(n):
        if parents[i] == -1:
            root = i
        else:
            tree[parents[i]].append(i)

    trie = PersistentTrie()
    query_map = defaultdict(list)
    for i, (node, val) in enumerate(queries):
        query_map[node].append((i, val))

    results = [0] * len(queries)

    def dfs(node, parent_trie):
        current_trie = trie.insert(parent_trie, node)
        if node in query_map:
            for idx, val in query_map[node]:
                results[idx] = trie.get_max_xor(current_trie, val)
        for child in tree[node]:
            dfs(child, current_trie)

    dfs(root, trie.versions[0])
    return results

# Example usage
parents = [-1, 0, 1, 1]
queries = [[0, 2], [3, 2], [2, 5]]
print(max_genetic_difference(parents, queries))
import java.util.*;

class PersistentTrieNode {
    PersistentTrieNode[] children = new PersistentTrieNode[2];
    int count = 0;
}

class PersistentTrie {
    List<PersistentTrieNode> versions = new ArrayList<>();

    public PersistentTrie() {
        versions.add(new PersistentTrieNode());
    }

    public PersistentTrieNode insert(PersistentTrieNode node, int num, int depth) {
        if (node == null) node = new PersistentTrieNode();
        if (depth == -1) {
            node.count++;
            return node;
        }
        int bit = (num >> depth) & 1;
        node.children[bit] = insert(node.children[bit], num, depth - 1);
        node.count = (node.children[0] != null ? node.children[0].count : 0) +
                (node.children[1] != null ? node.children[1].count : 0);
        return node;
    }

    public void buildVersion(int num) {
        versions.add(insert(versions.get(versions.size() - 1), num, 31));
    }

    public int getMaxXOR(PersistentTrieNode node, int num) {
        int xorSum = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int oppositeBit = 1 - bit;
            if (node.children[oppositeBit] != null && node.children[oppositeBit].count > 0) {
                xorSum |= (1 << i);
                node = node.children[oppositeBit];
            } else {
                node = node.children[bit];
            }
        }
        return xorSum;
    }
}

public class MaxGeneticDifferencePersistent {
    public static int[] maxGeneticDifference(int[] parents, int[][] queries) {
        int n = parents.length;
        List<List<Integer>> tree = new ArrayList<>();
        for (int i = 0; i < n; i++) tree.add(new ArrayList<>());
        int root = -1;
        for (int i = 0; i < n; i++) {
            if (parents[i] == -1) root = i;
            else tree.get(parents[i]).add(i);
        }

        PersistentTrie trie = new PersistentTrie();
        Map<Integer, List<int[]>> queryMap = new HashMap<>();
        for (int i = 0; i < queries.length; i++) {
            int node = queries[i][0];
            int val = queries[i][1];
            queryMap.computeIfAbsent(node, k -> new ArrayList<>()).add(new int[]{i, val});
        }

        int[] results = new int[queries.length];
        dfs(root, trie, tree, queryMap, results, trie.versions.get(0));

        return results;
    }

    private static void dfs(int node, PersistentTrie trie, List<List<Integer>> tree, Map<Integer, List<int[]>> queryMap, int[] results, PersistentTrieNode parentTrie) {
        PersistentTrieNode currentTrie = trie.insert(parentTrie, node, 31);

        if (queryMap.containsKey(node)) {
            for (int[] q : queryMap.get(node)) {
                int idx = q[0];
                int val = q[1];
                results[idx] = trie.getMaxXOR(currentTrie, val);
            }
        }

        for (int child : tree.get(node)) {
            dfs(child, trie, tree, queryMap, results, currentTrie);
        }
    }

    public static void main(String[] args) {
        int[] parents = {-1, 0, 1, 1};
        int[][] queries = {{0, 2}, {3, 2}, {2, 5}};
        int[] results = maxGeneticDifference(parents, queries);
        for (int result : results) {
            System.out.print(result + " ");
        }
    }
}
#include <iostream>
#include <vector>
using namespace std;

struct TrieNode {
    TrieNode* children[2] = {};
    int count = 0;
};

class Trie {
public:
    vector<TrieNode*> versions;

    Trie() {
        // Add the initial empty root.
        versions.push_back(new TrieNode());
    }

    TrieNode* insert(TrieNode* node, int num, int depth = 31) {
        if (!node) node = new TrieNode();
        if (depth == -1) {
            node->count++;
            return node;
        }
        int bit = (num >> depth) & 1;
        node->children[bit] = insert(node->children[bit], num, depth - 1);
        node->count = (node->children[0] ? node->children[0]->count : 0) +
                     (node->children[1] ? node->children[1]->count : 0);
        return node;
    }

    void buildVersion(int num) {
        versions.push_back(insert(versions.back(), num));
    }

    int getMaxXOR(TrieNode* node, int num, int depth = 31) {
        int xorSum = 0;
        for (int i = depth; i >= 0; --i) {
            int bit = (num >> i) & 1;
            int oppositeBit = 1 - bit;
            if (node->children[oppositeBit] && node->children[oppositeBit]->count > 0) {
                xorSum |= (1 << i);
                node = node->children[oppositeBit];
            } else {
                node = node->children[bit];
            }
        }
        return xorSum;
    }
};

void dfs(int node, const vector<vector<int>>& tree, Trie& trie, vector<int>& results, const vector<vector<pair<int, int>>>& queries, TrieNode* parentTrie) {
    TrieNode* currentTrie = trie.insert(parentTrie, node);
    for (auto& [queryIndex, val] : queries[node]) {
        results[queryIndex] = trie.getMaxXOR(currentTrie, val);
    }
    for (int child : tree[node]) {
        dfs(child, tree, trie, results, queries, currentTrie);
    }
}

vector<int> maxGeneticDifference(vector<int>& parents, vector<vector<int>>& queriesVec) {
    int n = parents.size();
    vector<vector<int>> tree(n);
    int root;
    for (int i = 0; i < n; ++i) {
        if (parents[i] == -1) root = i;
        else tree[parents[i]].push_back(i);
    }
    Trie trie;
    vector<vector<pair<int, int>>> queries(n);
    for (int i = 0; i < queriesVec.size(); ++i) {
        auto& q = queriesVec[i];
        queries[q[0]].push_back({i, q[1]});
    }
    vector<int> results(queriesVec.size());
    dfs(root, tree, trie, results, queries, trie.versions[0]);
    return results;
}

int main() {
    vector<int> parents = {-1, 0, 1, 1};
    vector<vector<int>> queries = {{0, 2}, {3, 2}, {2, 5}};
    vector<int> result = maxGeneticDifference(parents, queries);
    for (int res : result) {
        cout << res << " ";
    }
}
class PersistentTrieNode {
    constructor() {
        this.children = {};
        this.count = 0;
    }
}

class PersistentTrie {
    constructor() {
        this.versions = [new PersistentTrieNode()];
    }

    insert(node, num, depth = 31) {
        if (node === null) node = new PersistentTrieNode();
        if (depth === -1) {
            node.count++;
            return node;
        }
        let bit = (num >> depth) & 1;
        node.children[bit] = this.insert(node.children[bit], num, depth - 1);
        node.count = (node.children[0] ? node.children[0].count : 0) + (node.children[1] ? node.children[1].count : 0);
        return node;
    }

    buildVersion(num) {
        this.versions.push(this.insert(this.versions[this.versions.length - 1], num));
    }

    getMaxXOR(node, num) {
        let xorSum = 0;
        for (let i = 31; i >= 0; i--) {
            let bit = (num >> i) & 1;
            let oppositeBit = 1 - bit;
            if (node.children[oppositeBit] && node.children[oppositeBit].count > 0) {
                xorSum |= (1 << i);
                node = node.children[oppositeBit];
            } else {
                node = node.children[bit];
            }
        }
        return xorSum;
    }
}

function maxGeneticDifference(parents, queries) {
    const n = parents.length;
    const tree = Array.from({ length: n }, () => []);
    let root;
    for (let i = 0; i < n; i++) {
        if (parents[i] === -1) root = i;
        else tree[parents[i]].push(i);
    }

    const trie = new PersistentTrie();
    const queryMap = new Map();
    queries.forEach(([node, val], index) => {
        if (!queryMap.has(node)) queryMap.set(node, []);
        queryMap.get(node).push([index, val]);
    });

    const results = Array(queries.length).fill(0);

    function dfs(node, parentTrie) {
        const currentTrie = trie.insert(parentTrie, node);

        if (queryMap.has(node)) {
            queryMap.get(node).forEach(([index, val]) => {
                results[index] = trie.getMaxXOR(currentTrie, val);
            });
        }

        tree[node].forEach(child => dfs(child, currentTrie));
    }

    dfs(root, trie.versions[0]);
    return results;
}

// Example Usage:
const parents = [-1, 0, 1, 1];
const queries = [[0, 2], [3, 2], [2, 5]];
console.log(maxGeneticDifference(parents, queries));
using System;
using System.Collections.Generic;

class PersistentTrieNode {
    public PersistentTrieNode[] Children = new PersistentTrieNode[2];
    public int Count = 0;
}

class PersistentTrie {
    public List<PersistentTrieNode> Versions = new List<PersistentTrieNode>();

    public PersistentTrie() {
        Versions.Add(new PersistentTrieNode());
    }

    public PersistentTrieNode Insert(PersistentTrieNode node, int num, int depth = 31) {
        if (node == null) node = new PersistentTrieNode();
        if (depth == -1) {
            node.Count++;
            return node;
        }
        int bit = (num >> depth) & 1;
        node.Children[bit] = Insert(node.Children[bit], num, depth - 1);
        node.Count = (node.Children[0]?.Count ?? 0) + (node.Children[1]?.Count ?? 0);
        return node;
    }

    public void BuildVersion(int num) {
        Versions.Add(Insert(Versions[Versions.Count - 1], num));
    }

    public int GetMaxXOR(PersistentTrieNode node, int num) {
        int xorSum = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int oppositeBit = 1 - bit;
            if ((node.Children[oppositeBit]?.Count ?? 0) > 0) {
                xorSum |= (1 << i);
                node = node.Children[oppositeBit];
            } else {
                node = node.Children[bit];
            }
        }
        return xorSum;
    }
}

public class MaxGeneticDifferencePersistent {
    public static int[] MaxGeneticDifference(int[] parents, int[][] queries) {
        int n = parents.Length;
        List<int>[] tree = new List<int>[n];
        for (int i = 0; i < n; i++) tree[i] = new List<int>();
        int root = -1;
        for (int i = 0; i < n; i++) {
            if (parents[i] == -1) root = i;
            else tree[parents[i]].Add(i);
        }

        PersistentTrie trie = new PersistentTrie();
        Dictionary<int, List<(int, int)>> queryMap = new Dictionary<int, List<(int, int)>>();
        for (int i = 0; i < queries.Length; i++) {
            int node = queries[i][0];
            int val = queries[i][1];
            if (!queryMap.ContainsKey(node)) queryMap[node] = new List<(int, int)>();
            queryMap[node].Add((i, val));
        }

        int[] results = new int[queries.Length];
        DFS(root, trie, tree, queryMap, results, trie.Versions[0]);

        return results;
    }

    private static void DFS(int node, PersistentTrie trie, List<int>[] tree, Dictionary<int, List<(int, int)>> queryMap, int[] results, PersistentTrieNode parentTrie) {
        PersistentTrieNode currentTrie = trie.Insert(parentTrie, node);
        if (queryMap.ContainsKey(node)) {
            foreach (var query in queryMap[node]) {
                int idx = query.Item1;
                int val = query.Item2;
                results[idx] = trie.GetMaxXOR(currentTrie, val);
            }
        }
        foreach (var child in tree[node]) DFS(child, trie, tree, queryMap, results, currentTrie);
    }

    public static void Main(string[] args) {
        int[] parents = { -1, 0, 1, 1 };
        int[][] queries = { new int[] { 0, 2 }, new int[] { 3, 2 }, new int[] { 2, 5 } };
        int[] result = MaxGeneticDifference(parents, queries);
        Console.WriteLine(string.Join(" ", result));
    }
}

The Python solution achieves efficient query handling by utilizing the persistent Trie structure similar to the Java and C++ implementations. Each node operation generates a new trie version that resembles the state of the trie after the node addition, and this persists throughout the traversal, simplifying XOR evaluations.

Complexity

Time Complexity: O(N * 32 + Q * 32) ~ O(N + Q), with Trie handling of bitwise operations adding to complexity.

Space Complexity: Tries need more space relative to node operations, allowing reuse where possible.

Try this approach in the editor

Complexity comparison

ApproachComplexity
Approach 1: DFS with Trie

Time Complexity: O(N * 32 + Q * 32) ~ O(N + Q), controlled by the maximum bit operations in the Trie and the number of nodes and queries.

Space Complexity: O(32 * N), based on the Trie management during the DFS.

Approach 2: Preprocessing with Persistent Trie

Time Complexity: O(N * 32 + Q * 32) ~ O(N + Q), with Trie handling of bitwise operations adding to complexity.

Space Complexity: Tries need more space relative to node operations, allowing reuse where possible.

Complexity analysis

ApproachTimeSpaceWhen to Use
DFS with TrieO((n + q) * logV)O(n * logV)Best general solution. Efficient when queries are processed during DFS traversal.
Preprocessing with Persistent TrieO((n + q) * logV)O(n * logV)Useful when immutable versions of ancestor sets are needed or queries are processed independently.

Frequently asked questions

Is Maximum Genetic Difference Query easy or hard?

Maximum Genetic Difference Query is classified as Hard. The difficulty comes from combining tree traversal, bit manipulation, and a Trie-based maximum XOR structure while efficiently handling multiple queries.

How to solve Maximum Genetic Difference Query in O(n)?

A pure O(n) solution is not typical because each query requires checking bit levels in a Trie. The closest optimal complexity is O((n + q) * logV) using DFS with a binary Trie or a persistent Trie, where logV corresponds to the bit length of node values.

What is the best approach for Maximum Genetic Difference Query?

DFS with a binary Trie is the most practical approach. While traversing the tree, maintain a Trie containing the current node's ancestors. Each query performs a maximum XOR lookup in O(logV) time, leading to an overall complexity of O((n + q) * logV).

Is Maximum Genetic Difference Query asked at Google/Amazon/Meta?

Tree + Trie XOR problems frequently appear in interviews at companies like Google, Meta, and Amazon. Variations involving maximum XOR, ancestor queries, and bitwise tries are common in senior-level coding rounds.

What data structure is used in Maximum Genetic Difference Query?

The main data structure is a binary Trie used for fast maximum XOR queries. The algorithm also relies on depth-first search (DFS) to traverse the tree and maintain the active set of ancestor values.

What is the time complexity of Maximum Genetic Difference Query?

The optimal solutions run in O((n + q) * logV) time, where n is the number of nodes, q is the number of queries, and V is the maximum node value. Trie operations such as insert and XOR query take about logV (≈20) steps because values fit within a small number of bits.

Maximum Genetic Difference Query Python or Java solution approach?

Most Python and Java implementations build the tree from the parent array, group queries by node, then run DFS while inserting and removing values from a binary Trie. Each query performs a greedy XOR search from the highest bit to the lowest.

Comments

Next problem · similarMaximum XOR With an Element From ArrayHard
Now write it yourselfClose this page and solve Maximum Genetic Difference Query in the editor, without looking.
Practise Maximum Genetic Difference Query