1938. Maximum Genetic Difference Query LeetCode Solution
In this guide, you will get 1938. Maximum Genetic Difference Query LeetCode Solution with the best time and space complexity. The solution to Maximum Genetic Difference Query problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Genetic Difference Query
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.
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
Complexity Analysis
Time Complexity: O(n + q)
Space Complexity: O(n + q)
1938. Maximum Genetic Difference Query LeetCode Solution in C++
struct TrieNode {
vector<shared_ptr<TrieNode>> children;
int count = 0;
TrieNode() : children(2) {}
};
class Trie {
public:
void update(int num, int val) {
shared_ptr<TrieNode> node = root;
for (int i = kHeight; i >= 0; --i) {
const int bit = (num >> i) & 1;
if (node->children[bit] == nullptr)
node->children[bit] = make_shared<TrieNode>();
node = node->children[bit];
node->count += val;
}
}
int query(int num) {
int ans = 0;
shared_ptr<TrieNode> node = root;
for (int i = kHeight; i >= 0; --i) {
const int bit = (num >> i) & 1;
const int targetBit = bit ^ 1;
if (node->children[targetBit] && node->children[targetBit]->count) {
ans += 1 << i;
node = node->children[targetBit];
} else {
node = node->children[targetBit ^ 1];
}
}
return ans;
}
private:
static constexpr int kHeight = 17;
shared_ptr<TrieNode> root = make_shared<TrieNode>();
};
class Solution {
public:
vector<int> maxGeneticDifference(vector<int>& parents,
vector<vector<int>>& queries) {
const int n = parents.size();
vector<int> ans(queries.size());
int rootVal = -1;
vector<vector<int>> tree(n);
// {node: (index, val)}
unordered_map<int, vector<pair<int, int>>> nodeToQueries;
Trie trie;
for (int i = 0; i < parents.size(); ++i)
if (parents[i] == -1)
rootVal = i;
else
tree[parents[i]].push_back(i);
for (int i = 0; i < queries.size(); ++i) {
const int node = queries[i][0];
const int val = queries[i][1];
nodeToQueries[node].emplace_back(i, val);
}
dfs(rootVal, trie, tree, nodeToQueries, ans);
return ans;
}
private:
void dfs(int node, Trie& trie, const vector<vector<int>>& tree,
const unordered_map<int, vector<pair<int, int>>>& nodeToQueries,
vector<int>& ans) {
trie.update(node, 1);
if (const auto it = nodeToQueries.find(node); it != nodeToQueries.cend())
for (const auto& [i, val] : it->second)
ans[i] = trie.query(val);
for (const int child : tree[node])
dfs(child, trie, tree, nodeToQueries, ans);
trie.update(node, -1);
}
}; /* code provided by PROGIEZ */
1938. Maximum Genetic Difference Query LeetCode Solution in Java
class TrieNode {
public TrieNode[] children = new TrieNode[2];
public int count = 0;
}
class Trie {
public void update(int num, int val) {
TrieNode node = root;
for (int i = kHeight; i >= 0; --i) {
final int bit = (num >> i) & 1;
if (node.children[bit] == null)
node.children[bit] = new TrieNode();
node = node.children[bit];
node.count += val;
}
}
public int query(int num) {
int ans = 0;
TrieNode node = root;
for (int i = kHeight; i >= 0; --i) {
final int bit = (num >> i) & 1;
final int targetBit = bit ^ 1;
if (node.children[targetBit] != null && node.children[targetBit].count > 0) {
ans += 1 << i;
node = node.children[targetBit];
} else {
node = node.children[targetBit ^ 1];
}
}
return ans;
}
private static final int kHeight = 17;
TrieNode root = new TrieNode();
}
class Solution {
public int[] maxGeneticDifference(int[] parents, int[][] queries) {
final int n = parents.length;
int[] ans = new int[queries.length];
int rootVal = -1;
List<Integer>[] tree = new List[n];
for (int i = 0; i < n; ++i)
tree[i] = new ArrayList<>();
// {node: (index, val)}
Map<Integer, List<Pair<Integer, Integer>>> nodeToQueries = new HashMap<>();
Trie trie = new Trie();
for (int i = 0; i < parents.length; ++i)
if (parents[i] == -1)
rootVal = i;
else
tree[parents[i]].add(i);
for (int i = 0; i < queries.length; ++i) {
final int node = queries[i][0];
final int val = queries[i][1];
nodeToQueries.putIfAbsent(node, new ArrayList<>());
nodeToQueries.get(node).add(new Pair<>(i, val));
}
dfs(rootVal, trie, tree, nodeToQueries, ans);
return ans;
}
private void dfs(int node, Trie trie, List<Integer>[] tree,
Map<Integer, List<Pair<Integer, Integer>>> nodeToQueries, int[] ans) {
trie.update(node, 1);
if (nodeToQueries.containsKey(node))
for (Pair<Integer, Integer> query : nodeToQueries.get(node)) {
final int i = query.getKey();
final int val = query.getValue();
ans[i] = trie.query(val);
}
for (final int child : tree[node])
dfs(child, trie, tree, nodeToQueries, ans);
trie.update(node, -1);
}
} // code provided by PROGIEZ
1938. Maximum Genetic Difference Query LeetCode Solution in Python
class TrieNode:
def __init__(self):
self.children: list[TrieNode] = [None] * 2
self.count = 0
class Trie:
def __init__(self):
self.root = TrieNode()
self.kHeight = 17
def update(self, num: int, val: int) -> None:
node = self.root
for i in range(self.kHeight, -1, -1):
bit = (num >> i) & 1
if not node.children[bit]:
node.children[bit] = TrieNode()
node = node.children[bit]
node.count += val
def query(self, num: int) -> int:
ans = 0
node = self.root
for i in range(self.kHeight, -1, -1):
bit = (num >> i) & 1
targetBit = bit ^ 1
if node.children[targetBit] and node.children[targetBit].count > 0:
ans += 1 << i
node = node.children[targetBit]
else:
node = node.children[targetBit ^ 1]
return ans
class Solution:
def maxGeneticDifference(
self,
parents: list[int],
queries: list[list[int]],
) -> list[int]:
n = len(parents)
ans = [0] * len(queries)
rootVal = -1
tree = [[] for _ in range(n)]
nodeToQueries = collections.defaultdict(list) # {node: (index, val)}
trie = Trie()
for i, parent in enumerate(parents):
if parent == -1:
rootVal = i
else:
tree[parent].append(i)
for i, (node, val) in enumerate(queries):
nodeToQueries[node].append((i, val))
def dfs(node: int) -> None:
trie.update(node, 1)
# Answer queries for node
for i, val in nodeToQueries[node]:
ans[i] = trie.query(val)
for child in tree[node]:
dfs(child)
trie.update(node, -1)
dfs(rootVal)
return ans # code by PROGIEZ
