Minimum Score After Removals on a Tree solution and explanation
Google
9 more videos on this problem
Minimum Score After Removals on a Tree | Detailed Explanation | Leetcode 2322 | codestorywithMIKcodestorywithMIK · 53:10 · 10K views
Weekly Contest 299 | 2322. Minimum Score After Removals on a TreecodingMohan · 24:30 · 3K views
2322. Minimum Score After Removals on a Tree | Hard DFS | Leetcode Daily ChallengeEye on AI and DSA · 29:12 · 3K views
Minimum Score After Removals on a Tree | 2322 LeetCode | Graphs | Dp | Leetcode Weekly Contest 299CodeWithSunny · 23:42 · 2K views
Minimum Score After Removals on a Tree | Leetcode 2322 | DFSTechdose · 33:58 · 1K views
2322. Minimum Score After Removals on a Tree (Leetcode Hard)Programming Live with Larry · 33:19 · 1K views
2322. Minimum Score After Removals on a Tree | Leetcode Daily - PythonLeetcode Daily · 7:08 · 1K views
【每日一题】LeetCode 2322. Minimum Score After Removals on a TreeHuifeng Guan · 31:43 · 770 views
Leetcode 2322. Minimum Score After Removals on a TreeExpertFunda · 24:26 · 441 views
Minimum Score After Removals on a Tree | LeetCode 2322 - Pythonimpoldev · 21:19 · 436 views
The problem
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 are4 ^ 5 ^ 7 = 6,1 ^ 9 = 8, and3 ^ 3 ^ 3 = 3. The largest XOR value is8and the smallest XOR value is3. The score is then8 - 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.length3 <= n <= 10001 <= nums[i] <= 108edges.length == n - 1edges[i].length == 20 <= ai, bi < nai != biedgesrepresents a valid tree.
Approach overview
Problem Overview: You are given a tree where each node has a value. Remove two edges to split the tree into three components. For each component compute the XOR of node values, then minimize the difference between the maximum and minimum XOR values.
Approach 1: Brute Force with Optimizations (O(n^3) time, O(n) space)
The direct idea is to try every pair of edges to remove. Removing two edges splits the tree into three components, so you compute the XOR of each component and track the score max(x1, x2, x3) - min(x1, x2, x3). A DFS can compute XOR values for a component after temporarily removing edges. Since there are O(n^2) edge pairs and each component computation can take O(n), the total complexity becomes O(n^3). Some implementations reduce repeated work by caching subtree results or precomputing node values, but the approach is still expensive for large trees.
Approach 2: DFS with Subtree XOR Caching (O(n^2) time, O(n) space)
The optimized solution precomputes the XOR of every subtree using a single DFS. While traversing the tree, store each node's subtree XOR and maintain entry/exit times to determine ancestor relationships. The key observation: removing an edge corresponds to isolating a subtree. If you know subtree XOR values, you can derive the XOR of the remaining parts using simple XOR arithmetic.
For every pair of nodes representing removed edges, determine how their subtrees interact. There are three cases: one subtree inside another, the reverse nesting, or completely disjoint subtrees. Using ancestor checks from DFS timestamps, compute the three component XOR values in constant time. This reduces each pair evaluation to O(1), making the total runtime O(n^2) after a single DFS preprocessing step.
This approach relies heavily on Depth-First Search traversal and XOR properties from Bit Manipulation. Precomputing subtree information transforms repeated graph traversals into constant-time calculations.
Recommended for interviews: Interviewers expect the DFS + subtree XOR caching approach. The brute force method shows you understand the problem structure and component splitting. The optimized solution demonstrates stronger tree reasoning: precomputing subtree data, using ancestor checks, and applying XOR algebra to compute component values efficiently.
Approach 1: DFS with Subtree XOR Caching
The key idea is to perform a depth-first search (DFS) to compute the XOR for each subtree rooted at each node. By caching these values, we can efficiently determine the XOR of components after removing two edges.
We can use these cached values to compute the possible component XOR values after removing each pair of edges, and calculate the score of each pair.
def minScore(nums, edges):
from collections import defaultdict
tree = defaultdict(list)
for a, b in edges:
tree[a].append(b)
tree[b].append(a)
# DFS to calculate the XOR from root 0
def dfs(node, parent):
xor_value = nums[node]
for neighbor in tree[node]:
if neighbor != parent:
xor_value ^= dfs(neighbor, node)
subtree_xor[node] = xor_value
return xor_value
n = len(nums)
subtree_xor = [0] * n
total_xor = dfs(0, -1)
# Try to remove two different edges and calculate minimum possible score
min_score = float('inf')
for i in range(n):
for neighbor in tree[i]:
if neighbor > i: # Ensure each edge is considered once
for j in range(n):
for second_neighbor in tree[j]:
if second_neighbor > j and (j, second_neighbor) != (i, neighbor):
# We remove edges (i, neighbor) and (j, second_neighbor)
x = subtree_xor[neighbor] if parent == i else total_xor ^ subtree_xor[i]
y = subtree_xor[second_neighbor] if parent == j else total_xor ^ subtree_xor[j]
z = total_xor ^ x ^ y
max_xor = max(x, y, z)
min_xor = min(x, y, z)
min_score = min(min_score, max_xor - min_xor)
return min_scorefunction minScore(nums, edges) {
const adj = Array.from({ length: nums.length }, () => []);
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u);
}
const subtreeXor = new Array(nums.length).fill(0);
function dfs(node, parent) {
let xorValue = nums[node];
for (let neighbor of adj[node]) {
if (neighbor !== parent) {
xorValue ^= dfs(neighbor, node);
}
}
subtreeXor[node] = xorValue;
return xorValue;
}
const totalXor = dfs(0, -1);
let minScore = Number.POSITIVE_INFINITY;
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
let x, y;
if (subtreeXor[i] < subtreeXor[j]) {
x = subtreeXor[i];
y = subtreeXor[j] ^ subtreeXor[i];
} else {
x = subtreeXor[j];
y = subtreeXor[i] ^ subtreeXor[j];
}
const z = totalXor ^ (x ^ y);
minScore = Math.min(minScore, Math.max(x, y, z) - Math.min(x, y, z));
}
}
return minScore;
}This Python solution first builds an adjacency list from the given edges. It then uses DFS from an arbitrary root (node 0) to compute the XOR of every subtree rooted at each node. It utilizes this subtree data to compute possible XOR values when two edges are removed, and tracks the minimum score obtained.
The use of sets and filtering ensures efficient edge selection to deeply examine the implied subtrees created by removing distinct pairs of edges.
Time Complexity: O(n^2), where n is the number of nodes, due to the nested loops for examining edge pairs.
Space Complexity: O(n), mainly consumed by the adjacency list and XOR storage.
Approach 2: Brute Force with Optimizations
This approach leverages a brute-force analysis, with optimizations such as subtree XOR precomputation and efficient edge double-exclusion considerations.
The key is to evaluate every pair of distinct edges, ensuring each removal leads to valid and distinct subcomponent calculations.
import java.util.ArrayList;
import java.util.List;
public class MinScoreTree {
public int minScore(int[] nums, int[][] edges) {
int n = nums.length;
List<Integer>[] adj = new ArrayList[n];
for (int i = 0; i < n; i++) {
adj[i] = new ArrayList<>();
}
for (int[] edge : edges) {
adj[edge[0]].add(edge[1]);
adj[edge[1]].add(edge[0]);
}
int[] subtreeXor = new int[n];
int totalXor = dfs(0, -1, nums, adj, subtreeXor);
int minScore = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
for (int neighbor : adj[i]) {
if (neighbor > i) { // To avoid duplicated edge checking
int x = subtreeXor[neighbor];
int y = totalXor ^ subtreeXor[i];
for (int j = 0; j < n; j++) {
if (j != i && j != neighbor) {
int z = totalXor ^ x ^ y;
int maxVal = Math.max(Math.max(x, y), z);
int minVal = Math.min(Math.min(x, y), z);
minScore = Math.min(minScore, maxVal - minVal);
}
}
}
}
}
return minScore;
}
private int dfs(int node, int parent, int[] nums, List<Integer>[] adj, int[] subtreeXor) {
int xorValue = nums[node];
for (int neighbor : adj[node]) {
if (neighbor != parent) {
xorValue ^= dfs(neighbor, node, nums, adj, subtreeXor);
}
}
subtreeXor[node] = xorValue;
return xorValue;
}
}#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
vector<vector<int>> adj;
vector<int> subtreeXor;
int dfs(int node, int parent, const vector<int>& nums) {
int xorValue = nums[node];
for (int neighbor : adj[node]) {
if (neighbor != parent) {
xorValue ^= dfs(neighbor, node, nums);
}
}
subtreeXor[node] = xorValue;
return xorValue;
}
int minScore(vector<int>& nums, vector<vector<int>>& edges) {
int n = nums.size();
adj.resize(n);
for (auto& edge : edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
subtreeXor.resize(n);
int totalXor = dfs(0, -1, nums);
int minScore = INT_MAX;
for (int i = 0; i < n; ++i) {
for (int neighbor : adj[i]) {
for (int j = i + 1; j < n; ++j) {
for (int secondNeighbor : adj[j]) {
if ((i != j || neighbor != secondNeighbor) && j != neighbor) { // Ensure edges are distinct
int x = subtreeXor[neighbor];
int y = subtreeXor[secondNeighbor];
int z = totalXor ^ x ^ y;
int maxVal = max({x, y, z});
int minVal = min({x, y, z});
minScore = min(minScore, maxVal - minVal);
}
}
}
}
}
return minScore;
}This Java solution follows the brute-force approach with optimizations to limit unnecessary recalculations after the initial DFS subtree XOR computation. It checks every edge pairing systematically for viable subtree structural possibilities.
Java collections and array management handle adjacency construction and XOR data efficiently.
Time Complexity: O(n^3) due to iterative edge set evaluation.
Space Complexity: O(n), consumed by adjacency listings and subtree XOR arrays.
Approach 3: DFS + Subtree XOR Sum
We denote the XOR sum of the tree as s, i.e., s = nums[0] \oplus nums[1] \oplus ldots \oplus nums[n-1].
Next, we enumerate each node i in [0..n) as the root of the tree, and treat the edge connecting the root node to some child node j as the first edge to be removed. This gives us two connected components. We denote the XOR sum of the connected component containing root node i as s_1, then we perform DFS on the connected component containing root node i to calculate the XOR sum of each subtree, denoting each XOR sum calculated by DFS as s_2. The XOR sums of the three connected components are s \oplus s_1, s_2, and s_1 \oplus s_2. We need to calculate the maximum and minimum values of these three XOR sums, denoted as mx and mn. For each enumerated case, the score is mx - mn. We find the minimum value among all cases as the answer.
The XOR sum of each subtree can be calculated through DFS. We define a function dfs(i, fa), which represents starting DFS from node i, where fa is the parent node of node i. The function returns the XOR sum of the subtree rooted at node i.
The time complexity is O(n^2), and the space complexity is O(n), where n is the number of nodes in the tree.
function minimumScore(nums: number[], edges: number[][]): number {
const n = nums.length;
const g: number[][] = Array.from({ length: n }, () => []);
for (const [a, b] of edges) {
g[a].push(b);
g[b].push(a);
}
const s = nums.reduce((a, b) => a ^ b, 0);
let s1 = 0;
let ans = Number.MAX_SAFE_INTEGER;
function dfs(i: number, fa: number): number {
let res = nums[i];
for (const j of g[i]) {
if (j !== fa) {
res ^= dfs(j, i);
}
}
return res;
}
function dfs2(i: number, fa: number): number {
let res = nums[i];
for (const j of g[i]) {
if (j !== fa) {
const s2 = dfs2(j, i);
res ^= s2;
const mx = Math.max(s ^ s1, s2, s1 ^ s2);
const mn = Math.min(s ^ s1, s2, s1 ^ s2);
ans = Math.min(ans, mx - mn);
}
}
return res;
}
for (let i = 0; i < n; ++i) {
for (const j of g[i]) {
s1 = dfs(i, j);
dfs2(i, j);
}
}
return ans;
}public class Solution {
public int MinimumScore(int[] nums, int[][] edges) {
int n = nums.Length;
List<int>[] g = new List<int>[n];
for (int i = 0; i < n; i++) {
g[i] = new List<int>();
}
foreach (var e in edges) {
int a = e[0], b = e[1];
g[a].Add(b);
g[b].Add(a);
}
int s = 0;
foreach (int x in nums) {
s ^= x;
}
int ans = int.MaxValue;
int s1 = 0;
int Dfs(int i, int fa) {
int res = nums[i];
foreach (int j in g[i]) {
if (j != fa) {
res ^= Dfs(j, i);
}
}
return res;
}
int Dfs2(int i, int fa) {
int res = nums[i];
foreach (int j in g[i]) {
if (j != fa) {
int s2 = Dfs2(j, i);
res ^= s2;
int mx = Math.Max(Math.Max(s ^ s1, s2), s1 ^ s2);
int mn = Math.Min(Math.Min(s ^ s1, s2), s1 ^ s2);
ans = Math.Min(ans, mx - mn);
}
}
return res;
}
for (int i = 0; i < n; ++i) {
foreach (int j in g[i]) {
s1 = Dfs(i, j);
Dfs2(i, j);
}
}
return ans;
}
}func minimumScore(nums []int, edges [][]int) int {
n := len(nums)
g := make([][]int, n)
for _, e := range edges {
a, b := e[0], e[1]
g[a] = append(g[a], b)
g[b] = append(g[b], a)
}
s, s1 := 0, 0
ans := math.MaxInt32
for _, x := range nums {
s ^= x
}
var dfs func(i, fa int) int
dfs = func(i, fa int) int {
res := nums[i]
for _, j := range g[i] {
if j != fa {
res ^= dfs(j, i)
}
}
return res
}
var dfs2 func(i, fa int) int
dfs2 = func(i, fa int) int {
res := nums[i]
for _, j := range g[i] {
if j != fa {
s2 := dfs2(j, i)
res ^= s2
mx := max(s^s1, s2, s1^s2)
mn := min(s^s1, s2, s1^s2)
ans = min(ans, mx-mn)
}
}
return res
}
for i := 0; i < n; i++ {
for _, j := range g[i] {
s1 = dfs(i, j)
dfs2(i, j)
}
}
return ans
}impl Solution {
pub fn minimum_score(nums: Vec<i32>, edges: Vec<Vec<i32>>) -> i32 {
let n = nums.len();
let mut g = vec![vec![]; n];
for e in edges.iter() {
let a = e[0] as usize;
let b = e[1] as usize;
g[a].push(b);
g[b].push(a);
}
let mut s1 = 0;
let mut ans = i32::MAX;
let s = nums.iter().fold(0, |acc, &x| acc ^ x);
fn dfs(i: usize, fa: usize, g: &Vec<Vec<usize>>, nums: &Vec<i32>) -> i32 {
let mut res = nums[i];
for &j in &g[i] {
if j != fa {
res ^= dfs(j, i, g, nums);
}
}
res
}
fn dfs2(
i: usize,
fa: usize,
g: &Vec<Vec<usize>>,
nums: &Vec<i32>,
s: i32,
s1: i32,
ans: &mut i32
) -> i32 {
let mut res = nums[i];
for &j in &g[i] {
if j != fa {
let s2 = dfs2(j, i, g, nums, s, s1, ans);
res ^= s2;
let mx = (s ^ s1).max(s2).max(s1 ^ s2);
let mn = (s ^ s1).min(s2).min(s1 ^ s2);
*ans = (*ans).min(mx - mn);
}
}
res
}
for i in 0..n {
for &j in &g[i] {
s1 = dfs(i, j, &g, &nums);
dfs2(i, j, &g, &nums, s, s1, &mut ans);
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| DFS with Subtree XOR Caching | Time Complexity: O(n^2), where n is the number of nodes, due to the nested loops for examining edge pairs. Space Complexity: O(n), mainly consumed by the adjacency list and XOR storage. |
| Brute Force with Optimizations | Time Complexity: O(n^3) due to iterative edge set evaluation. Space Complexity: O(n), consumed by adjacency listings and subtree XOR arrays. |
| DFS + Subtree XOR Sum | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Component DFS | O(n^3) | O(n) | Conceptual baseline or when constraints are very small |
| Brute Force with Cached Subtree XOR | O(n^2) | O(n) | When subtree XOR values are precomputed to avoid repeated DFS |
| DFS with Subtree XOR + Ancestor Checks | O(n^2) | O(n) | Optimal interview solution for tree splitting problems |
Frequently asked questions
Is Minimum Score After Removals on a Tree easy or hard?
Minimum Score After Removals on a Tree is classified as a Hard problem. It combines tree traversal, XOR properties, and careful case handling when two removed edges create nested or disjoint subtrees.
Minimum Score After Removals on a Tree Python/Java solution
Python and Java implementations typically build an adjacency list, run DFS to compute subtree XOR values, and store traversal timestamps. After preprocessing, nested loops iterate through node pairs representing removed edges and calculate the three component XOR values using constant-time formulas.
How to solve Minimum Score After Removals on a Tree in O(n^2)?
Run a DFS to compute the XOR of each node's subtree and record entry/exit times for ancestor checks. For every pair of candidate edges, determine whether one subtree contains the other or if they are disjoint. Using subtree XOR values, compute the three component XORs in O(1) time and update the minimum score.
What is the best approach for Minimum Score After Removals on a Tree?
The best approach uses DFS to compute subtree XOR values and timestamps for ancestor checks. After preprocessing the tree, iterate over every pair of removable edges and compute the resulting component XOR values using cached subtree results. Each pair is evaluated in constant time, giving an overall time complexity of O(n^2) with O(n) space.
Is Minimum Score After Removals on a Tree asked at Google/Amazon/Meta?
Tree XOR and subtree decomposition problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that involve subtree values, edge removal, and DFS preprocessing are common in senior-level algorithm interviews.
What data structure is used in Minimum Score After Removals on a Tree?
The solution primarily uses an adjacency list to represent the tree and Depth-First Search for traversal. Additional arrays store subtree XOR values and DFS entry/exit times. Bitwise XOR operations are used to efficiently derive component values.
What is the time complexity of Minimum Score After Removals on a Tree?
The optimized solution runs in O(n^2) time. A single DFS computes subtree XOR values and traversal timestamps in O(n). Then every pair of edges is evaluated in constant time, leading to O(n^2) total complexity with O(n) extra space.