2322. Minimum Score After Removals on a Tree LeetCode Solution
In this guide, you will get 2322. Minimum Score After Removals on a Tree LeetCode Solution with the best time and space complexity. The solution to Minimum Score After Removals on a Tree 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.
Table of Contents
- Problem Statement
- Complexity Analysis
- Minimum Score After Removals on a Tree solution in C++
- Minimum Score After Removals on a Tree solution in Java
- Minimum Score After Removals on a Tree solution in Python
- Additional Resources
Problem Statement of Minimum Score After Removals on a Tree
There is an undirected connected tree with n nodes labeled from 0 to n – 1 and n – 1 edges.
You are given a 0-indexed integer array nums of length n where nums[i] represents the value of the ith node. You are also given a 2D integer array edges of length n – 1 where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
Remove two distinct edges of the tree to form three connected components. For a pair of removed edges, the following steps are defined:
Get the XOR of all the values of the nodes for each of the three components respectively.
The difference between the largest XOR value and the smallest XOR value is the score of the pair.
For example, say the three components have the node values: [4,5,7], [1,9], and [3,3,3]. The three XOR values are 4 ^ 5 ^ 7 = 6, 1 ^ 9 = 8, and 3 ^ 3 ^ 3 = 3. The largest XOR value is 8 and the smallest XOR value is 3. The score is then 8 – 3 = 5.
Return the minimum score of any possible pair of edge removals on the given tree.
Example 1:
Input: nums = [1,5,5,4,11], edges = [[0,1],[1,2],[1,3],[3,4]]
Output: 9
Explanation: The diagram above shows a way to make a pair of removals.
– The 1st component has nodes [1,3,4] with values [5,4,11]. Its XOR value is 5 ^ 4 ^ 11 = 10.
– The 2nd component has node [0] with value [1]. Its XOR value is 1 = 1.
– The 3rd component has node [2] with value [5]. Its XOR value is 5 = 5.
The score is the difference between the largest and smallest XOR value which is 10 – 1 = 9.
It can be shown that no other pair of removals will obtain a smaller score than 9.
Example 2:
Input: nums = [5,5,2,4,4,2], edges = [[0,1],[1,2],[5,2],[4,3],[1,3]]
Output: 0
Explanation: The diagram above shows a way to make a pair of removals.
– The 1st component has nodes [3,4] with values [4,4]. Its XOR value is 4 ^ 4 = 0.
– The 2nd component has nodes [1,0] with values [5,5]. Its XOR value is 5 ^ 5 = 0.
– The 3rd component has nodes [2,5] with values [2,2]. Its XOR value is 2 ^ 2 = 0.
The score is the difference between the largest and smallest XOR value which is 0 – 0 = 0.
We cannot obtain a smaller score than 0.
Constraints:
n == nums.length
3 <= n <= 1000
1 <= nums[i] <= 108
edges.length == n – 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
edges represents a valid tree.
Complexity Analysis
- Time Complexity: O(n^2)
- Space Complexity: O(n^2)
2322. Minimum Score After Removals on a Tree LeetCode Solution in C++
class Solution {
public:
int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {
const int n = nums.size();
const int xors = reduce(nums.begin(), nums.end(), 0, bit_xor());
vector<int> subXors(nums);
vector<vector<int>> tree(n);
vector<unordered_set<int>> children(n);
for (int i = 0; i < n; ++i)
children[i].insert(i);
for (const vector<int>& edge : edges) {
const int u = edge[0];
const int v = edge[1];
tree[u].push_back(v);
tree[v].push_back(u);
}
dfs(tree, 0, -1, subXors, children);
int ans = INT_MAX;
for (int i = 0; i < edges.size(); ++i) {
int a = edges[i][0];
int b = edges[i][1];
if (children[a].contains(b))
swap(a, b);
for (int j = 0; j < i; ++j) {
int c = edges[j][0];
int d = edges[j][1];
if (children[c].contains(d))
swap(c, d);
vector<int> cands;
if (a != c && children[a].contains(c))
cands = {subXors[c], subXors[a] ^ subXors[c], xors ^ subXors[a]};
else if (a != c && children[c].contains(a))
cands = {subXors[a], subXors[c] ^ subXors[a], xors ^ subXors[c]};
else
cands = {subXors[a], subXors[c], xors ^ subXors[a] ^ subXors[c]};
ans = min(ans, ranges::max(cands) - ranges::min(cands));
}
}
return ans;
}
private:
pair<int, unordered_set<int>> dfs(const vector<vector<int>>& tree, int u,
int prev, vector<int>& subXors,
vector<unordered_set<int>>& children) {
for (const int v : tree[u]) {
if (v == prev)
continue;
const auto& [vXor, vChildren] = dfs(tree, v, u, subXors, children);
subXors[u] ^= vXor;
children[u].insert(vChildren.begin(), vChildren.end());
}
return {subXors[u], children[u]};
}
};
/* code provided by PROGIEZ */2322. Minimum Score After Removals on a Tree LeetCode Solution in Java
class Solution {
public int minimumScore(int[] nums, int[][] edges) {
final int n = nums.length;
final int xors = getXors(nums);
int[] subXors = nums.clone();
List<Integer>[] tree = new List[n];
Set<Integer>[] children = new Set[n];
for (int i = 0; i < n; ++i)
tree[i] = new ArrayList<>();
for (int i = 0; i < n; ++i)
children[i] = new HashSet<>(Arrays.asList(i));
for (int[] edge : edges) {
final int u = edge[0];
final int v = edge[1];
tree[u].add(v);
tree[v].add(u);
}
dfs(tree, 0, -1, subXors, children);
int ans = Integer.MAX_VALUE;
for (int i = 0; i < edges.length; ++i) {
int a = edges[i][0];
int b = edges[i][1];
if (children[a].contains(b)) {
final int temp = a;
a = b;
b = a;
}
for (int j = 0; j < i; ++j) {
int c = edges[j][0];
int d = edges[j][1];
if (children[c].contains(d)) {
final int temp = c;
c = d;
d = temp;
}
int[] cands;
if (a != c && children[a].contains(c))
cands = new int[] {subXors[c], subXors[a] ^ subXors[c], xors ^ subXors[a]};
else if (a != c && children[c].contains(a))
cands = new int[] {subXors[a], subXors[c] ^ subXors[a], xors ^ subXors[c]};
else
cands = new int[] {subXors[a], subXors[c], xors ^ subXors[a] ^ subXors[c]};
ans = Math.min(ans, Arrays.stream(cands).max().getAsInt() -
Arrays.stream(cands).min().getAsInt());
}
}
return ans;
}
private Pair<Integer, Set<Integer>> dfs(List<Integer>[] tree, int u, int prev, int[] subXors,
Set<Integer>[] children) {
for (final int v : tree[u]) {
if (v == prev)
continue;
final Pair<Integer, Set<Integer>> pair = dfs(tree, v, u, subXors, children);
final int vXor = pair.getKey();
final Set<Integer> vChildren = pair.getValue();
subXors[u] ^= vXor;
for (final int child : vChildren)
children[u].add(child);
}
return new Pair<>(subXors[u], children[u]);
}
private int getXors(int[] nums) {
int xors = 0;
for (final int num : nums)
xors ^= num;
return xors;
}
}
// code provided by PROGIEZ2322. Minimum Score After Removals on a Tree LeetCode Solution in Python
class Solution:
def minimumScore(self, nums: list[int], edges: list[list[int]]) -> int:
n = len(nums)
xors = functools.reduce(operator.xor, nums)
subXors = nums[:]
tree = [[] for _ in range(n)]
children = [{i} for i in range(n)]
for u, v in edges:
tree[u].append(v)
tree[v].append(u)
def dfs(u: int, prev: int) -> tuple[int, set[int]]:
for v in tree[u]:
if v == prev:
continue
vXor, vChildren = dfs(v, u)
subXors[u] ^= vXor
children[u] |= vChildren
return subXors[u], children[u]
dfs(0, -1)
ans = math.inf
for i in range(len(edges)):
a, b = edges[i]
if b in children[a]:
a, b = b, a
for j in range(i):
c, d = edges[j]
if d in children[c]:
c, d = d, c
if c in children[a] and a != c:
cands = [subXors[c], subXors[a] ^ subXors[c], xors ^ subXors[a]]
elif a in children[c] and a != c:
cands = [subXors[a], subXors[c] ^ subXors[a], xors ^ subXors[c]]
else:
cands = [subXors[a], subXors[c], xors ^ subXors[a] ^ subXors[c]]
ans = min(ans, max(cands) - min(cands))
return ans
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.