Maximum Genetic Difference Query
HardPrompt
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 <= 1050 <= parents[i] <= parents.length - 1for every nodeithat is not the root.parents[root] == -11 <= queries.length <= 3 * 1040 <= nodei <= parents.length - 10 <= vali <= 2 * 105
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. For each query, it traverses the tree from the given node up to the root, finds all ancestor nodes, and calculates the XOR value with the query's val, keeping track of the maximum.
Algorithm
- Initialize an answer array
answith the same size as thequeriesarray. - Iterate through each query
[node, val]in thequeriesarray. - For each query, initialize a variable
max_xorto -1. - Start a traversal from the given
nodeup to the root. Let the current node becurr_node. - In a loop, while
curr_nodeis not -1 (the root's parent): a. Calculate the XOR difference:current_xor = val ^ curr_node. b. Updatemax_xor = max(max_xor, current_xor). c. Move to the parent:curr_node = parents[curr_node]. - After the loop finishes (i.e., the root has been processed), store the final
max_xorin theansarray at the corresponding query index. - After iterating through all queries, return the
ansarray.
Walkthrough
The brute-force method is the most straightforward way to solve the problem. It follows the problem statement literally by processing each query independently.
For each query [node, val], we need to find the maximum genetic difference with any ancestor of node. The ancestors can be found by repeatedly following the parents array starting from node until we reach the root (where parent == -1).
We can implement this with a nested loop structure. The outer loop iterates through each query, and the inner loop traverses the path from the query's node to the root. During this traversal, we compute the XOR of val with each node's genetic value (which is its index) and maintain the maximum XOR value found so far.
Here is a Java code snippet illustrating this approach:
class Solution { public int[] maxGeneticDifference(int[] parents, int[][] queries) { int n = parents.length; int[] ans = new int[queries.length]; for (int i = 0; i < queries.length; i++) { int node = queries[i][0]; int val = queries[i][1]; int max_xor = -1; int curr_node = node; // Traverse from the node up to the root while (curr_node != -1) { max_xor = Math.max(max_xor, val ^ curr_node); curr_node = parents[curr_node]; } ans[i] = max_xor; } return ans; }}Complexity
Time
O(Q * N) Let `Q` be the number of queries and `N` be the number of nodes. For each query, we may traverse from a leaf to the root. In the worst-case scenario of a skewed tree (like a linked list), the path length is `O(N)`. Therefore, the total time complexity is `O(Q * N)`.
Space
O(Q) or O(1) The space complexity is `O(Q)` to store the answer array. If the output array is not considered part of the space complexity, the auxiliary space used is `O(1)`.
Trade-offs
Pros
Simple to understand and implement.
Requires minimal extra space, making it memory efficient.
Cons
Extremely inefficient for large inputs, particularly for deep or skewed trees.
The time complexity of
O(Q * N)makes it likely to fail on platforms with strict time limits (Time Limit Exceeded).
This is a highly efficient approach that avoids redundant computations by processing queries offline. It combines a Depth First Search (DFS) traversal of the tree with a Trie (prefix tree). The Trie is used to efficiently find, for a given value val, the number in a set that produces the maximum XOR result. By performing a single DFS, we can answer all queries. At any point during the DFS at node u, the Trie will contain exactly the set of u's ancestors, allowing us to answer queries for u.
Algorithm
- Preprocessing:
a. Build an adjacency list representation of the tree from the
parentsarray for efficient DFS traversal. b. Group queries by theirnode. Use aMap<Integer, List<int[]>>where the key isnodeand the value is a list of[val, original_index]pairs. - Trie Data Structure:
a. Define a
TrieNodeclass withchildren[2](for bits 0 and 1) and acountfield to track how many numbers use that prefix. b. Implementinsert(num),remove(num), andfindMaxXor(num)methods for the Trie. - DFS Traversal:
a. Initialize an empty Trie and an answer array
ans. b. Find the root of the tree (node with parent -1). c. Start a recursive DFS from the root. - DFS Function
dfs(u): a. Insert: Calltrie.insert(u)to add the current node's value to the set of ancestors. b. Query: Check if there are any queries for nodeu. If so, for each query(val, index), computeans[index] = trie.findMaxXor(val). c. Recurse: Calldfs(v)for each childvofu. d. Backtrack: After returning from all children's recursive calls, calltrie.remove(u)to remove the current node's value from the Trie. This ensures it's not considered an ancestor for sibling branches. - Return the
ansarray after the initial DFS call completes.
Walkthrough
The key insight to optimize this problem is to notice that queries for nodes in the same subtree share common ancestors. We can exploit this by processing queries in a structured way rather than one by one. This is a classic 'offline processing' technique.
We perform a single Depth First Search (DFS) from the root of the tree. We use a Trie data structure to keep track of the genetic values of all nodes on the path from the root to the current node in the DFS.
Algorithm Steps:
- Preprocessing: We first convert the
parentsarray into an adjacency list to represent the tree, which is more suitable for DFS. We also group the queries by the node they are associated with, so we can easily access all queries for a nodeuwhen our DFS visitsu. - DFS Traversal: We start a DFS from the root.
- When we enter a node
u, we insert its genetic valueuinto the Trie. At this moment, the Trie contains the values of all ofu's ancestors. - We then process all queries
[u, val]that were originally for this node. For each such query, we use the Trie'sfindMaxXorfunction withvalto find the best matching ancestor. The result is stored in our final answer array. - Next, we recursively call the DFS for all children of
u. - After the recursive calls for all children have returned (i.e., we are about to backtrack from
u), we removeu's value from the Trie. This cleanup step is crucial becauseuis not an ancestor of its siblings or any nodes in other branches of the tree.
- When we enter a node
Trie for Maximum XOR: The Trie is built on the binary representation of the numbers. To find the maximum XOR for a value val, we traverse the Trie from the most significant bit (MSB) to the LSB. At each bit position, if the bit in val is b, we greedily try to find a number in the Trie that has the bit 1-b at this position. This maximizes the resulting XOR bit by bit.
Here is a Java implementation of this approach:
class Solution { private static class TrieNode { TrieNode[] children = new TrieNode[2]; int count = 0; } private static final int MAX_BIT = 17; // 2*10^5 < 2^18 private void insert(TrieNode root, int num) { TrieNode curr = root; for (int i = MAX_BIT; i >= 0; i--) { int bit = (num >> i) & 1; if (curr.children[bit] == null) { curr.children[bit] = new TrieNode(); } curr = curr.children[bit]; curr.count++; } } private void remove(TrieNode root, int num) { TrieNode curr = root; for (int i = MAX_BIT; i >= 0; i--) { int bit = (num >> i) & 1; curr = curr.children[bit]; curr.count--; } } private int findMaxXor(TrieNode root, int num) { TrieNode curr = root; int maxXor = 0; for (int i = MAX_BIT; i >= 0; i--) { int bit = (num >> i) & 1; int targetBit = 1 - bit; if (curr.children[targetBit] != null && curr.children[targetBit].count > 0) { maxXor |= (1 << i); curr = curr.children[targetBit]; } else { curr = curr.children[bit]; } } return maxXor; } private void dfs(int u, List<List<Integer>> adj, TrieNode trieRoot, Map<Integer, List<int[]>> queriesByNode, int[] ans) { insert(trieRoot, u); if (queriesByNode.containsKey(u)) { for (int[] query : queriesByNode.get(u)) { ans[query[1]] = findMaxXor(trieRoot, query[0]); } } for (int v : adj.get(u)) { dfs(v, adj, trieRoot, queriesByNode, ans); } remove(trieRoot, u); } public int[] maxGeneticDifference(int[] parents, int[][] queries) { int n = parents.length; List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) adj.add(new ArrayList<>()); int rootNode = -1; for (int i = 0; i < n; i++) { if (parents[i] == -1) rootNode = i; else adj.get(parents[i]).add(i); } Map<Integer, List<int[]>> queriesByNode = new HashMap<>(); for (int i = 0; i < queries.length; i++) { queriesByNode.computeIfAbsent(queries[i][0], k -> new ArrayList<>()).add(new int[]{queries[i][1], i}); } int[] ans = new int[queries.length]; TrieNode trieRoot = new TrieNode(); dfs(rootNode, adj, trieRoot, queriesByNode, ans); return ans; }}Complexity
Time
O((N + Q) * L) - `N` is the number of nodes, `Q` is the number of queries, and `L` is the number of bits in the values (a constant, e.g., 18). - Building the adjacency list and query map takes `O(N + Q)`. - The DFS visits each node once. At each node, we perform one `insert` and one `remove` operation on the Trie, each taking `O(L)` time. Total for all nodes: `O(N * L)`. - Each of the `Q` queries is processed once with a `findMaxXor` call, which takes `O(L)`. Total for all queries: `O(Q * L)`. - The combined time complexity is `O(N + Q + N*L + Q*L)`, which simplifies to `O((N + Q) * L)`.
Space
O(N * L + Q) - The Trie can store up to `N` numbers. In the worst case, the number of nodes in the Trie is `O(N * L)`, where `L` is the number of bits. - The adjacency list requires `O(N)` space. - The map for queries requires `O(Q)` space. - The recursion stack for DFS can go up to `O(N)` in depth. - The total space is dominated by the Trie, making it `O(N * L + Q)`.
Trade-offs
Pros
Highly efficient with a time complexity that handles large constraints.
A generalizable technique for many types of path queries on trees.
Cons
Significantly more complex to implement compared to the brute-force approach.
Requires more memory due to the Trie data structure, adjacency list, and recursion stack.
Solutions
Solution
class Solution { static final int MAXD = 17;public int[] maxGeneticDifference(int[] parents, int[][] queries) { int n = parents.length; List<List<Integer>> edges = new ArrayList<List<Integer>>(); for (int i = 0; i < n; i++) edges.add(new ArrayList<Integer>()); int rootIndex = -1; for (int i = 0; i < n; i++) { if (parents[i] == -1) rootIndex = i; else edges.get(parents[i]).add(i); } List<List<int[]>> stored = new ArrayList<List<int[]>>(); for (int i = 0; i < n; i++) stored.add(new ArrayList<int[]>()); int queriesCount = queries.length; int[] ans = new int[queriesCount]; for (int i = 0; i < queriesCount; i++) stored.get(queries[i][0]).add(new int[]{i, queries[i][1]}); TrieNode root = new TrieNode(); depthFirstSearch(ans, root, rootIndex, edges, stored); return ans; }public void insert(TrieNode root, int x) { TrieNode curr = root; for (int i = MAXD; i >= 0; i--) { if ((x & (1 << i)) != 0) { if (curr.children[1] == null) curr.children[1] = new TrieNode(); curr = curr.children[1]; } else { if (curr.children[0] == null) curr.children[0] = new TrieNode(); curr = curr.children[0]; } curr.count++; } }public int query(TrieNode root, int x) { int queryMax = 0; TrieNode curr = root; for (int i = MAXD; i >= 0; i--) { if ((x & (1 << i)) != 0) { if (curr.children[0] != null && curr.children[0].count > 0) { queryMax |= 1 << i; curr = curr.children[0]; } else curr = curr.children[1]; } else { if (curr.children[1] != null && curr.children[1].count > 0) { queryMax |= 1 << i; curr = curr.children[1]; } else curr = curr.children[0]; } } return queryMax; }public void erase(TrieNode root, int x) { TrieNode curr = root; for (int i = MAXD; i >= 0; i--) { if ((x & (1 << i)) != 0) curr = curr.children[1]; else curr = curr.children[0]; curr.count--; } }public void depthFirstSearch(int[] ans, TrieNode root, int node, List<List<Integer>> edges, List<List<int[]>> stored) { insert(root, node); List<int[]> list = stored.get(node); for (int[] pair : list) { int index = pair[0], num = pair[1]; ans[index] = query(root, num); } List<Integer> nextNodes = edges.get(node); for (int nextNode : nextNodes) depthFirstSearch(ans, root, nextNode, edges, stored); erase(root, node); }} class TrieNode { int count; TrieNode[] children;public TrieNode() { children = new TrieNode[2]; count = 0; }}// OJ: https://leetcode.com/problems/maximum-genetic-difference-query/ // Time: O(P + Q) // Space: O(P) struct TrieNode { TrieNode * next [ 2 ] = {}; int cnt = 0 ; }; class Solution { public: vector < int > maxGeneticDifference ( vector < int >& P , vector < vector < int >>& Q ) { int N = P . size (), M = Q . size (), rootIndex ; vector < vector < int >> G ( N ); for ( int i = 0 ; i < N ; ++ i ) { if ( P [ i ] != - 1 ) G [ P [ i ]]. push_back ( i ); else rootIndex = i ; } unordered_map < int , vector < int >> m ; for ( int i = 0 ; i < M ; ++ i ) m [ Q [ i ][ 0 ]]. push_back ( i ); TrieNode root ; auto getAnswer = [ & ]( TrieNode * node , int q ) { int ans = 0 ; for ( int i = 31 ; i >= 0 ; -- i ) { int b = q >> i & 1 ; if ( node -> next [ 1 - b ] && node -> next [ 1 - b ] -> cnt ) { node = node -> next [ 1 - b ]; ans |= 1 << i ; } else node = node -> next [ b ]; } return ans ; }; vector < int > ans ( M ); function < void ( int ) > dfs = [ & ]( int u ) { auto node = & root ; for ( int i = 31 ; i >= 0 ; -- i ) { int b = u >> i & 1 ; if ( ! node -> next [ b ]) node -> next [ b ] = new TrieNode (); node = node -> next [ b ]; node -> cnt ++ ; } if ( m . count ( u )) { for ( int index : m [ u ]) ans [ index ] = getAnswer ( & root , Q [ index ][ 1 ]); } for ( int v : G [ u ]) dfs ( v ); node = & root ; for ( int i = 31 ; i >= 0 ; -- i ) { int b = u >> i & 1 ; node = node -> next [ b ]; node -> cnt -- ; } }; dfs ( rootIndex ); return ans ; } };Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.