Create Components With Same Value

Hard

#2224Time: O(2^(n-1) * n). There are `2^(n-1)` subsets of edges. For each, building the graph and finding components takes O(n + (n-1)) = O(n) time.Space: O(n) to store the adjacency list and visited array for each configuration.1 company

Patterns

Algorithms

Data structures

Companies

Prompt

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 i^th node. You are also given a 2D integer array edges of length n - 1 where edges[i] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i 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 * 10⁴
nums.length == n
1 <= nums[i] <= 50
edges.length == n - 1
edges[i].length == 2
0 <= edges[i][0], edges[i][1] <= n - 1
edges represents a valid tree.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach exhaustively checks every possible way to partition the tree. Since a tree with n nodes has n-1 edges, there are 2^(n-1) possible subsets of edges to delete. For each subset, the algorithm forms the resulting components, calculates their values, and checks if they are all equal. It keeps track of the maximum number of deleted edges that results in a valid partition.

Algorithm

Initialize max_deleted_edges to 0.
Iterate through all 2^(n-1) subsets of edges. Each subset represents a potential set of edges to delete.
For each subset:
- Count the number of edges to be deleted, current_deleted_count.
- Construct a graph using only the edges that are not in the current subset.
- Find all connected components in this new graph using a traversal algorithm like Breadth-First Search (BFS) or Depth-First Search (DFS).
- For each component, calculate the sum of its node values.
- Check if all component sums are identical.
- If they are, update max_deleted_edges = max(max_deleted_edges, current_deleted_count).
After checking all subsets, return max_deleted_edges.

Walkthrough

The core idea is to treat the problem as finding the best subset of edges to delete. We can represent each subset using a bitmask of length n-1. If the i-th bit is set, we delete the i-th edge; otherwise, we keep it.

For each of the 2^(n-1) masks, we perform the following steps:

Build a graph: We create an adjacency list representing the graph formed by the edges we decided to keep.
Find Components and Sums: We traverse the graph to identify all connected components. A visited array helps track nodes that have already been assigned to a component. For each component found, we calculate the sum of its node values.
Validate Partition: We store the sums of all components in a list. If this list is not empty, we check if all its elements are equal to the first element.
Update Maximum: If all component sums are equal, it means we've found a valid partition. We then compare the number of edges we deleted for this partition with the maximum found so far and update it if necessary.

This method is guaranteed to find the correct answer because it explores the entire search space, but its exponential time complexity makes it impractical for anything but very small trees.

1// Conceptual implementation of the brute-force approach.2// This will be too slow for the given constraints (Time Limit Exceeded).3class Solution {4    public int componentValue(int[] nums, int[][] edges) {5        int n = nums.length;6        if (n <= 1) {7            return 0;8        }9        int numEdges = edges.length;10        int maxDeleted = 0;11 12        for (int i = 0; i < (1 << numEdges); i++) {13            List<Integer>[] adj = new ArrayList[n];14            for (int j = 0; j < n; j++) {15                adj[j] = new ArrayList<>();16            }17            int deletedCount = 0;18 19            for (int j = 0; j < numEdges; j++) {20                if (((i >> j) & 1) == 1) { // Edge j is deleted21                    deletedCount++;22                } else { // Edge j is kept23                    adj[edges[j][0]].add(edges[j][1]);24                    adj[edges[j][1]].add(edges[j][0]);25                }26            }27 28            List<Long> componentSums = new ArrayList<>();29            boolean[] visited = new boolean[n];30            for (int j = 0; j < n; j++) {31                if (!visited[j]) {32                    long currentSum = 0;33                    Queue<Integer> q = new LinkedList<>();34                    q.add(j);35                    visited[j] = true;36                    while (!q.isEmpty()) {37                        int u = q.poll();38                        currentSum += nums[u];39                        for (int v : adj[u]) {40                            if (!visited[v]) {41                                visited[v] = true;42                                q.add(v);43                            }44                        }45                    }46                    componentSums.add(currentSum);47                }48            }49 50            boolean allEqual = true;51            if (componentSums.size() > 1) {52                long firstSum = componentSums.get(0);53                for (int j = 1; j < componentSums.size(); j++) {54                    if (componentSums.get(j) != firstSum) {55                        allEqual = false;56                        break;57                    }58                }59            }60 61            if (allEqual) {62                maxDeleted = Math.max(maxDeleted, deletedCount);63            }64        }65        return maxDeleted;66    }67}

Complexity

Time

O(2^(n-1) * n). There are `2^(n-1)` subsets of edges. For each, building the graph and finding components takes O(n + (n-1)) = O(n) time.

Space

O(n) to store the adjacency list and visited array for each configuration.

Trade-offs

Pros

Simple to understand and implement.
Guaranteed to be correct as it checks all possibilities.

Cons

Extremely high time complexity, making it infeasible for the given constraints (n up to 20,000).

This efficient approach is based on a crucial observation: if the tree is split into c components of equal value, then the value of each component must be a divisor of the total sum of all node values. Instead of trying all edge deletions, we can iterate through all possible valid component values. We want to maximize the number of deleted edges, which is equivalent to maximizing the number of components c. Therefore, we can iterate c from n down to 1, find the corresponding target value (totalSum / c), and check if a partition with that target value is possible. This check can be performed efficiently with a single Depth First Search (DFS).

Algorithm

Calculate totalSum, the sum of all elements in nums.
Build an adjacency list for the tree from the edges array.
Iterate through the possible number of components, c, from n down to 2.
For each c, check if totalSum is divisible by c.
- If it is, let target = totalSum / c. This is the required value for each component.
- Call a DFS-based function, check(target), to verify if the tree can be partitioned into components of this value.
The check function uses a post-order traversal (dfs(u, parent)):
- For a node u, it recursively calculates the sum of its subtree, assuming child subtrees that form a valid component have been 'cut'.
- dfs(u, parent) returns the sum of the component containing u.
- If dfs for a subtree returns a sum equal to target, it means a component is formed. This call then returns 0 to its parent, simulating an edge cut.
- If a subtree sum exceeds target, the partition is impossible for this target. The function propagates a failure signal.
- The initial call dfs(0, -1) must return 0 for a successful partition of the entire tree.
If check(target) is successful, we have found the maximum possible c. Return c - 1 as the answer.
If the loop completes without finding a valid partition, it means no edges can be deleted. Return 0.

Walkthrough

The algorithm proceeds as follows:

Calculate Total Sum: First, compute the sum of all node values, totalSum.
Iterate Potential Partitions: We want to maximize the number of components, c. The maximum possible value for c is n, and the minimum is 1. We iterate c from n down to 2. For each c, we check if it can be a valid number of components.
Check Divisibility: For a partition into c components to be possible, totalSum must be perfectly divisible by c. If totalSum % c != 0, we skip to the next value of c.
Verify Partition with DFS: If totalSum is divisible by c, we set target = totalSum / c. We then need to verify if the tree can indeed be partitioned into components of this target value. This is the core of the algorithm, which we solve using a post-order DFS traversal.

The dfs(u, parent) function calculates the sum of the subtree rooted at u and returns one of three things:

The sum of its subtree component if it's less than target.
0 if its subtree sum is exactly target. This signifies that the subtree forms a valid component, and we 'cut' the edge to its parent by not propagating its sum upwards.
A special value (e.g., greater than target) to signal that a partition with this target is impossible because a subtree sum has already exceeded it.

We start the DFS from the root (e.g., node 0). If the final result of dfs(0, -1) is 0, it means the entire tree was successfully partitioned into components of value target. Since we iterate c from largest to smallest, the first c that passes this check gives the maximum number of components. The answer is c - 1.

1class Solution {2    private List<Integer>[] adj;3    private int[] nums;4    private long targetSum;5    private long totalSum; // Use long to be safe, though int is sufficient here6 7    public int componentValue(int[] nums, int[][] edges) {8        int n = nums.length;9        this.nums = nums;10        adj = new ArrayList[n];11        for (int i = 0; i < n; i++) {12            adj[i] = new ArrayList<>();13        }14 15        totalSum = 0;16        for (int num : nums) {17            totalSum += num;18        }19 20        if (n <= 1) {21            return 0;22        }23 24        for (int[] edge : edges) {25            adj[edge[0]].add(edge[1]);26            adj[edge[1]].add(edge[0]);27        }28 29        // Iterate on k = number of components, from n down to 230        for (int k = n; k >= 2; k--) {31            if (totalSum % k == 0) {32                this.targetSum = totalSum / k;33                if (dfs(0, -1) == 0) {34                    return k - 1;35                }36            }37        }38 39        return 0;40    }41 42    private long dfs(int u, int p) {43        long currentSum = nums[u];44        for (int v : adj[u]) {45            if (v == p) continue;46            long childSum = dfs(v, u);47            48            // If a child subtree sum already exceeds target, or if the check failed deeper down,49            // propagate the failure. A value > targetSum indicates failure.50            if (childSum > targetSum) {51                return childSum;52            }53            currentSum += childSum;54        }55 56        if (currentSum == targetSum) {57            // This subtree forms a component, cut the edge to parent by returning 0.58            return 0; 59        }60        61        // If currentSum > targetSum, this partition is not possible.62        // Return a value that signals failure.63        if (currentSum > targetSum) {64            return totalSum + 1; // Any value > targetSum would work.65        }66 67        // Pass the sum up to the parent.68        return currentSum; 69    }70}

Complexity

Time

O(d(totalSum) * n), where `d(totalSum)` is the number of divisors of the total sum. For the given constraints, `totalSum` is at most `2*10^4 * 50 = 10^6`. The number of divisors for numbers up to `10^6` is small (at most 240). Thus, the complexity is effectively near-linear in `n`.

Space

O(n) for building the adjacency list and for the recursion stack depth in the worst-case (a skewed tree).

Trade-offs

Pros

Highly efficient and passes within the time limits.
Reduces the search space from exponential to a small number of divisor checks.

Cons

Relies on a number theory insight (divisibility), which might not be immediately obvious.
The recursive DFS implementation requires careful handling of return values to signal success, failure, or a partial sum.

Solutions

Solution

1class Solution {2private3  List<Integer>[] g;4private5  int[] nums;6private7  int t;8public9  int componentValue(int[] nums, int[][] edges) {10    int n = nums.length;11    g = new List[n];12    this.nums = nums;13    Arrays.setAll(g, k->new ArrayList<>());14    for (var e : edges) {15      int a = e[0], b = e[1];16      g[a].add(b);17      g[b].add(a);18    }19    int s = sum(nums), mx = max(nums);20    for (int k = Math.min(n, s / mx); k > 1; --k) {21      if (s % k == 0) {22        t = s / k;23        if (dfs(0, -1) == 0) {24          return k - 1;25        }26      }27    }28    return 0;29  }30private31  int dfs(int i, int fa) {32    int x = nums[i];33    for (int j : g[i]) {34      if (j != fa) {35        int y = dfs(j, i);36        if (y == -1) {37          return -1;38        }39        x += y;40      }41    }42    if (x > t) {43      return -1;44    }45    return x < t ? x : 0;46  }47private48  int sum(int[] arr) {49    int x = 0;50    for (int v : arr) {51      x += v;52    }53    return x;54  }55private56  int max(int[] arr) {57    int x = arr[0];58    for (int v : arr) {59      x = Math.max(x, v);60    }61    return x;62  }63}

1class Solution {2public:3  int componentValue(vector<int> &nums, vector<vector<int>> &edges) {4    int n = nums.size();5    int s = accumulate(nums.begin(), nums.end(), 0);6    int mx = *max_element(nums.begin(), nums.end());7    int t = 0;8    unordered_map<int, vector<int>> g;9    for (auto &e : edges) {10      int a = e[0], b = e[1];11      g[a].push_back(b);12      g[b].push_back(a);13    }14    function<int(int, int)> dfs = [&](int i, int fa) -> int {15      int x = nums[i];16      for (int j : g[i]) {17        if (j != fa) {18          int y = dfs(j, i);19          if (y == -1)20            return -1;21          x += y;22        }23      }24      if (x > t)25        return -1;26      return x < t ? x : 0;27    };28    for (int k = min(n, s / mx); k > 1; --k) {29      if (s % k == 0) {30        t = s / k;31        if (dfs(0, -1) == 0) {32          return k - 1;33        }34      }35    }36    return 0;37  }38};

1class Solution:2    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int: def dfs(i, fa): x = nums[i] for j in g[i]: if j != fa: y = dfs(j, i) if y == - 1: return - 1 x += y if x > t: return - 1 return x if x < t else 0 n = len(nums) g = defaultdict(list) for a, b in edges: g[a]. append(b) g[b]. append(a) s = sum(nums) mx = max(nums) for k in range(min(n, s // mx), 1, - 1): if s % k == 0: t = s // k if dfs(0, - 1) == 0: return k - 1 return 0

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.

← Previous

Previous problem

Next problem