Create Components With Same Value solution and explanation
4 more videos on this problem
Biweekly Contest 89 | 6211. Create Components With Same ValuecodingMohan · 17:30 · 1K views
【每日一题】LeetCode 2440. Create Components With Same ValueHuifeng Guan · 27:10 · 818 views
Leetcode BiWeekly contest 89 - Hard - Create Components With Same ValuePrakhar Agrawal · 18:59 · 758 views
2440. Create Components With Same Value (Leetcode Hard)Programming Live with Larry · 56:48 · 441 views
Day 59/75: Problem Name: Create Components With Same Value | Leetcode | #75DaysHardLeetcodeCodeInsanity · 11:20 · 212 views
The problem
There is an undirected tree with n nodes labeled from 0 to n - 1.
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.
You are allowed to delete some edges, splitting the tree into multiple connected components. Let the value of a component be the sum of all nums[i] for which node i is in the component.
Return the maximum number of edges you can delete, such that every connected component in the tree has the same value.
Example 1:
Input: nums = [6,2,2,2,6], edges = [[0,1],[1,2],[1,3],[3,4]] Output: 2 Explanation: The above figure shows how we can delete the edges [0,1] and [3,4]. The created components are nodes [0], [1,2,3] and [4]. The sum of the values in each component equals 6. It can be proven that no better deletion exists, so the answer is 2.
Example 2:
Input: nums = [2], edges = [] Output: 0 Explanation: There are no edges to be deleted.
Constraints:
1 <= n <= 2 * 104nums.length == n1 <= nums[i] <= 50edges.length == n - 1edges[i].length == 20 <= edges[i][0], edges[i][1] <= n - 1edgesrepresents a valid tree.
Approach overview
Problem Overview: You are given a tree where each node has a value. Remove edges so that every connected component has the same total value. The goal is to maximize the number of removed edges while keeping all resulting components with identical sums.
Approach 1: Depth First Search with Target Sum Enumeration (O(n * d) time, O(n) space)
The key observation: if the total sum of all node values is S, every component must sum to a divisor of S. Enumerate possible target sums and verify whether the tree can be split so each component equals that value. For each candidate target, run a Depth‑First Search on the tree to compute subtree sums. When a subtree sum reaches the target, treat it as a completed component and return 0 upward so the parent doesn't double count it. If any subtree exceeds the target, that configuration is invalid. The number of successful target partitions determines how many edges you can remove.
This works because every valid partition must align with subtree boundaries in a tree. DFS naturally aggregates values bottom‑up and lets you detect when a component sum matches the target.
Approach 2: Union-Find Component Aggregation (O(n α(n)) time, O(n) space)
An alternative model treats nodes as components and progressively merges them while tracking component sums using a Union-Find structure. Nodes are joined along edges while ensuring the combined sum does not exceed the chosen target value. When a merged component exactly equals the target sum, it becomes a finalized component and stops merging further. The disjoint-set structure allows efficient union and find operations while maintaining component sums.
This approach is less common for interviews but demonstrates how component constraints can be enforced dynamically with disjoint sets. It works well when you want explicit component tracking rather than recursive subtree accumulation.
Recommended for interviews: The DFS enumeration approach. It directly leverages tree properties and shows strong understanding of subtree aggregation. Start by computing the total sum, enumerate valid target sums, and validate each using DFS. The Union-Find approach is more specialized and rarely expected in interviews.
Approach 1: Depth First Search (DFS) Approach
In this approach, we utilize Depth First Search (DFS) to traverse the tree and calculate the total sum of all node values. Then, we attempt to partition the tree into connected components that have equal value. This involves checking each divisor of the total sum and seeing if it can be used as the target value for each component.
from collections import defaultdict
def dfs(node, nums, tree, visited):
visited[node] = True
subtree_sum = nums[node]
for next_node in tree[node]:
if not visited[next_node]:
subtree_sum += dfs(next_node, nums, tree, visited)
return subtree_sum
def maxDeletions(nums, edges):
n = len(nums)
tree = defaultdict(list)
for u, v in edges:
tree[u].append(v)
tree[v].append(u)
total_sum = sum(nums)
max_deletions = 0
for divisor in range(1, total_sum + 1):
if total_sum % divisor == 0:
visited = [False] * n
valid = True
num_deletions = -1
for i in range(n):
if not visited[i]:
subtree_sum = dfs(i, nums, tree, visited)
if subtree_sum % divisor != 0:
valid = False
break
num_deletions += 1
if valid:
max_deletions = len(edges) - num_deletions
return max_deletions
# Example usage
nums = [6, 2, 2, 2, 6]
edges = [[0, 1], [1, 2], [1, 3], [3, 4]]
print(maxDeletions(nums, edges))import java.util.*;
public class TreeComponents {
public static void main(String[] args) {
int[] nums = {6, 2, 2, 2, 6};
int[][] edges = {{0, 1}, {1, 2}, {1, 3}, {3, 4}};
System.out.println(maxDeletions(nums, edges));
}
public static int maxDeletions(int[] nums, int[][] edges) {
int n = nums.length;
ArrayList<Integer>[] tree = new ArrayList[n];
for (int i = 0; i < n; i++) tree[i] = new ArrayList<>();
for (int[] edge : edges) {
int u = edge[0], v = edge[1];
tree[u].add(v);
tree[v].add(u);
}
int total_sum = Arrays.stream(nums).sum();
int max_deletions = 0;
for (int divisor = 1; divisor <= total_sum; divisor++) {
if (total_sum % divisor == 0) {
boolean[] visited = new boolean[n];
boolean valid = true;
int num_deletions = -1;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
int subtree_sum = dfs(i, nums, tree, visited);
if (subtree_sum % divisor != 0) {
valid = false;
break;
}
num_deletions++;
}
}
if (valid) max_deletions = edges.length - num_deletions;
}
}
return max_deletions;
}
private static int dfs(int node, int[] nums, ArrayList<Integer>[] tree, boolean[] visited) {
visited[node] = true;
int subtree_sum = nums[node];
for (int next : tree[node]) {
if (!visited[next])
subtree_sum += dfs(next, nums, tree, visited);
}
return subtree_sum;
}
}#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
void dfs(int node, int &subtree_sum, vector<int> &nums, vector<vector<int>> &tree, vector<int> &visited) {
visited[node] = 1;
subtree_sum += nums[node];
for (int next_node : tree[node]) {
if (!visited[next_node])
dfs(next_node, subtree_sum, nums, tree, visited);
}
}
int maxDeletions(vector<int> &nums, vector<vector<int>> &edges) {
int n = nums.size();
vector<vector<int>> tree(n);
for (auto &edge : edges) {
int u = edge[0], v = edge[1];
tree[u].push_back(v);
tree[v].push_back(u);
}
int total_sum = accumulate(nums.begin(), nums.end(), 0);
int max_deletions = 0;
for (int divisor = 1; divisor <= total_sum; divisor++) {
if (total_sum % divisor == 0) {
vector<int> visited(n, 0);
int valid = true;
int num_deletions = -1;
for (int i = 0; i < n; ++i) {
if (!visited[i]) {
int subtree_sum = 0;
dfs(i, subtree_sum, nums, tree, visited);
if (subtree_sum % divisor != 0) {
valid = false;
break;
}
num_deletions++;
}
}
if (valid)
max_deletions = edges.size() - num_deletions;
}
}
return max_deletions;
}
int main() {
vector<int> nums = {6, 2, 2, 2, 6};
vector<vector<int>> edges = {{0, 1}, {1, 2}, {1, 3}, {3, 4}};
cout << maxDeletions(nums, edges) << endl;
return 0;
}function dfs(node, nums, tree, visited) {
visited[node] = true;
let subtree_sum = nums[node];
for (let nextNode of tree[node]) {
if (!visited[nextNode]) {
subtree_sum += dfs(nextNode, nums, tree, visited);
}
}
return subtree_sum;
}
function maxDeletions(nums, edges) {
const n = nums.length;
const tree = Array.from({length: n}, () => []);
for (let [u, v] of edges) {
tree[u].push(v);
tree[v].push(u);
}
const totalSum = nums.reduce((acc, val) => acc + val, 0);
let maxDeletions = 0;
for (let divisor = 1; divisor <= totalSum; divisor++) {
if (totalSum % divisor === 0) {
const visited = Array(n).fill(false);
let valid = true;
let numDeletions = -1;
for (let i = 0; i < n; i++) {
if (!visited[i]) {
const subtreeSum = dfs(i, nums, tree, visited);
if (subtreeSum % divisor !== 0) {
valid = false;
break;
}
numDeletions++;
}
}
if (valid) {
maxDeletions = edges.length - numDeletions;
}
}
}
return maxDeletions;
}
// Example usage
const nums = [6, 2, 2, 2, 6];
const edges = [[0, 1], [1, 2], [1, 3], [3, 4]];
console.log(maxDeletions(nums, edges));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 20000
int adj[MAXN][MAXN];
int degree[MAXN];
int nums[MAXN];
int visited[MAXN];
int total_sum;
void dfs(int node, int *subtree_sum) {
visited[node] = 1;
*subtree_sum += nums[node];
for (int i = 0; i < degree[node]; i++) {
int next_node = adj[node][i];
if (!visited[next_node])
dfs(next_node, subtree_sum);
}
}
int maxDeletions(int n, int nums[], int edges[][2], int n_edges) {
memset(degree, 0, sizeof(degree));
memset(visited, 0, sizeof(visited));
total_sum = 0;
// Calculate total sum of all node values
for (int i = 0; i < n; i++)
total_sum += nums[i];
// Build adjacency list
for (int i = 0; i < n_edges; i++) {
int u = edges[i][0];
int v = edges[i][1];
adj[u][degree[u]++] = v;
adj[v][degree[v]++] = u;
}
int max_deletions = 0;
for (int divisor = 1; divisor <= total_sum; divisor++) {
if (total_sum % divisor == 0) {
memset(visited, 0, sizeof(visited));
int valid = 1;
int num_deletions = -1;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
int subtree_sum = 0;
dfs(i, &subtree_sum);
if (subtree_sum % divisor != 0) {
valid = 0;
break;
}
num_deletions++;
}
}
if (valid)
max_deletions = n_edges - num_deletions;
}
}
return max_deletions;
}
int main() {
int nums[] = {6, 2, 2, 2, 6};
int edges[][2] = {{0, 1}, {1, 2}, {1, 3}, {3, 4}};
int n = 5;
int n_edges = 4;
printf("%d\n", maxDeletions(n, nums, edges, n_edges));
return 0;
}using System;
using System.Collections.Generic;
class TreeComponents {
static int dfs(int node, int[] nums, List<int>[] tree, bool[] visited) {
visited[node] = true;
int subtree_sum = nums[node];
foreach (var next in tree[node]) {
if (!visited[next])
subtree_sum += dfs(next, nums, tree, visited);
}
return subtree_sum;
}
public static int MaxDeletions(int[] nums, int[][] edges) {
int n = nums.Length;
var tree = new List<int>[n];
for (int i = 0; i < n; i++) tree[i] = new List<int>();
foreach (var edge in edges) {
int u = edge[0], v = edge[1];
tree[u].Add(v);
tree[v].Add(u);
}
int total_sum = 0;
foreach (var num in nums) total_sum += num;
int max_deletions = 0;
for (int divisor = 1; divisor <= total_sum; divisor++) {
if (total_sum % divisor == 0) {
bool[] visited = new bool[n];
bool valid = true;
int num_deletions = -1;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
int subtree_sum = dfs(i, nums, tree, visited);
if (subtree_sum % divisor != 0) {
valid = false;
break;
}
num_deletions++;
}
}
if (valid) max_deletions = edges.Length - num_deletions;
}
}
return max_deletions;
}
public static void Main() {
int[] nums = {6, 2, 2, 2, 6};
int[][] edges = { new int[]{0, 1}, new int[]{1, 2}, new int[]{1, 3}, new int[]{3, 4} };
Console.WriteLine(MaxDeletions(nums, edges));
}
}This Python implementation uses a defaultdict to build an adjacency list for the tree, making edge-management easier. The function maxDeletions computes the sum of node values first and then evaluates each feasible divisor. For valid divisors, the tree is traversed using DFS to verify and compute potential component sums, maximizing deletions.
Time Complexity: O(n * sqrt(sum(nums))) due to divisor checks and tree traversals.
Space Complexity: O(n) for maintaining visited status and adjacency list.
Approach 2: Union-Find Approach
This approach leverages the Union-Find (also known as Disjoint Set Union, DSU) data structure to effectively manage connected components in the tree dynamically. By maintaining a Union-Find structure, components can be merged or split efficiently. We will essentially attempt to simulate the partitions dynamically based on the total sum and divisors.
from collections import defaultdict
class UnionFind:
def __init__(self, size):
self.parent = list(range(size))
self.rank = [1] * size
def find(self, node):
if self.parent[node] != node:
self.parent[node] = self.find(self.parent[node])
return self.parent[node]
def union(self, node1, node2):
root1 = self.find(node1)
root2 = self.find(node2)
if root1 != root2:
if self.rank[root1] > self.rank[root2]:
self.parent[root2] = root1
elif self.rank[root1] < self.rank[root2]:
self.parent[root1] = root2
else:
self.parent[root2] = root1
self.rank[root1] += 1
return True
return False
def maxDeletions(nums, edges):
n = len(nums)
total_sum = sum(nums)
max_deletions = 0
for divisor in range(1, total_sum + 1):
if total_sum % divisor == 0:
dsu = UnionFind(n)
component_sums = [nums[i] for i in range(n)]
deletions = 0
for u, v in edges:
if dsu.union(u, v):
ru = dsu.find(u)
rv = dsu.find(v)
new_sum = component_sums[ru] + component_sums[rv]
if new_sum % divisor == 0:
deletions += 1
component_sums[ru] = new_sum
component_sums[rv] = component_sums[ru]
if component_sums[dsu.find(0)] % divisor == 0:
max_deletions = max(max_deletions, deletions)
return max_deletions
# Example usage
nums = [6, 2, 2, 2, 6]
edges = [[0, 1], [1, 2], [1, 3], [3, 4]]
print(maxDeletions(nums, edges))This solution in Python uses a Union-Find data structure to efficiently manage tree components. By continuously merging nodes and recalculating sums, the program ensures that each component's sum is validated against a divisor. Optimal deletions are calculated for setups where each resulting component sum equals the divisor's multiples or entire divisor.
Time Complexity: O(n * sqrt(sum(nums)) * α(n)) due to the amortized inverse Ackermann function associated with union-find operations.
Space Complexity: O(n) for maintaining union-find structures and component sums.
Approach 3: Enumeration of Connected Blocks
Assume the number of connected blocks is k, then the number of edges to be deleted is k-1, and the value of each connected block is \frac{s}{k}, where s is the sum of the values of all nodes in nums.
We enumerate k from large to small. If there exists a k such that \frac{s}{k} is an integer, and the value of each connected block obtained is equal, then directly return k-1. The initial value of k is min(n, \frac{s}{mx}), where mx is the maximum value in nums.
The key point is to judge whether for a given \frac{s}{k}, it is possible to divide several subtrees such that the value of each subtree is \frac{s}{k}.
Here we use the dfs function to judge. We recursively traverse from top to bottom to calculate the value of each subtree. If the sum of the subtree values is exactly \frac{s}{k}, it means that the division is successful at this time. We set the value to 0 and return it to the upper level, indicating that this subtree can be disconnected from the parent node. If the sum of the subtree values is greater than \frac{s}{k}, it means that the division fails at this time. We return -1, indicating that it cannot be divided.
The time complexity is O(n times \sqrt{s}), where n and s are the length of nums and the sum of the values of all nodes in nums, respectively.
func componentValue(nums []int, edges [][]int) int {
s, mx := 0, slices.Max(nums)
for _, x := range nums {
s += x
}
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)
}
t := 0
var dfs func(int, int) int
dfs = func(i, fa int) int {
x := nums[i]
for _, j := range g[i] {
if j != fa {
y := dfs(j, i)
if y == -1 {
return -1
}
x += y
}
}
if x > t {
return -1
}
if x < t {
return x
}
return 0
}
for k := min(n, s/mx); k > 1; k-- {
if s%k == 0 {
t = s / k
if dfs(0, -1) == 0 {
return k - 1
}
}
}
return 0
}Complexity comparison
| Approach | Complexity |
|---|---|
| Depth First Search (DFS) Approach | Time Complexity: O(n * sqrt(sum(nums))) due to divisor checks and tree traversals. Space Complexity: O(n) for maintaining visited status and adjacency list. |
| Union-Find Approach | Time Complexity: O(n * sqrt(sum(nums)) * α(n)) due to the amortized inverse Ackermann function associated with union-find operations. Space Complexity: O(n) for maintaining union-find structures and component sums. |
| Enumeration of Connected Blocks | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Target Sum Enumeration | O(n * d) | O(n) | General case for trees. Best interview approach for validating equal-sum components. |
| Union-Find Component Aggregation | O(n α(n)) | O(n) | Useful when explicitly tracking merged components or experimenting with disjoint-set structures. |
Frequently asked questions
Is Create Components With Same Value easy or hard?
Create Components With Same Value is classified as Hard on LeetCode. The difficulty comes from recognizing that valid component sums must divide the total tree sum and designing a DFS that safely cuts components without breaking remaining subtree calculations.
Create Components With Same Value Python/Java solution
Python and Java implementations typically build an adjacency list, compute the total node sum, and run DFS for each candidate component value. During DFS, subtree sums accumulate bottom‑up and reset to zero whenever they match the target component sum.
How to solve Create Components With Same Value in O(n)?
A single DFS pass cannot determine the correct partition without knowing the target component sum. Instead, compute the total sum and test valid divisors. Each test performs one DFS to verify subtree sums. Although each DFS is O(n), the number of valid candidates is limited, keeping the solution efficient in practice.
What is the best approach for Create Components With Same Value?
Depth‑First Search with target sum enumeration is the most common solution. Compute the total sum of all nodes, try divisors of that sum as the component value, and validate each using DFS that aggregates subtree sums. The algorithm runs in roughly O(n * d) time where d is the number of candidate divisors.
Is Create Components With Same Value asked at Google/Amazon/Meta?
Tree partitioning and subtree sum validation problems appear frequently in interviews at companies like Google, Amazon, and Meta. This problem tests DFS traversal, reasoning about tree structure, and handling divisibility constraints across components.
What data structure is used in Create Components With Same Value?
The primary structure is a tree represented with adjacency lists. The optimal solution uses Depth‑First Search to compute subtree sums. Some alternative implementations experiment with Union-Find to track merged components and maintain component sums.
What is the time complexity of Create Components With Same Value?
The typical DFS enumeration solution runs in O(n * d) time and O(n) space. Here n is the number of nodes and d is the number of possible component sums derived from the total tree sum. Each candidate sum requires one DFS traversal of the tree.