2440. Create Components With Same Value


Problem Description

In this problem, we are given an undirected tree consisting of n nodes, where each node is labeled from 0 to n - 1. Each node has an associated integer value given in an array nums[]. Alongside, we are provided a list of edges edges[], which represent the links between the trees' nodes.

Our objective is to figure out the maximum number of edges we can remove from this tree in such a way that the resultant connected components all have the same value. The value of a component is defined as the sum of the values of nodes within that component.

To summarize the problem: With a given set of nodes and their connections, we must strategically delete edges so as to partition the tree into equal-valued components, and we want to maximize the number of deletions we can make.

Intuition

To solve this problem, we need to determine if the tree can be partitioned into k equal-valued components. If the sum of all node values is s, then each component's total value must be t = s / k. It is only possible to have components of equal value if s is divisible by k.

The solution approach uses the following insights:

  1. We iterate over potential component sizes by checking whether the sum of all node values s is divisible by k.
  2. For a given k, we compute the target sum t that each component should have (s/k) and then use depth-first search (DFS) to compute the sum of values in each component, starting from the root node.
  3. During DFS, if we encounter a subtree whose sum is exactly t, we consider this subtree as a potential component. The edge connecting this subtree to the rest of the tree can be one of the deletable edges.
  4. If a subtree's sum exceeds t or if after considering a subtree as component we end up with a partial sum exceeding t, then this partitioning is not possible, and we continue to check the next possible value of k.
  5. If the dfs function returns 0 for a given k, it means we have successfully partitioned the tree into k components of equal sum t, and thus can delete k-1 edges to create these k components.
  6. We try dividing s from the smallest k possible (s divided by the maximum value in nums, which is the theoretically highest possible k that makes t larger than any single node value) to 2, and return k-1 for the first successful partitioning.

This approach ensures that we test the maximum number of partitions first, which inherently means we would be removing the maximum number of edges possible to achieve equal-valued components.

Learn more about Tree, Depth-First Search and Math patterns.

Solution Approach

To implement the approach described above, the solution script defines a dfs function and iteratively seeks the right k that can divide the total sum of all node values s into equal parts. Here's how the implementation unfolds:

  • First, we prepare a graph g in the form of an adjacency list with the help of a defaultdict of lists. This graph g represents the tree structure defined by the edges array. Each edge connects two nodes, and for every edge [a, b], we add b to the list of adjacent nodes of a, and vice versa.

  • The variable s is the sum of all node values and represents the total value that we seek to divide into equal parts.

  • The dfs function performs a Depth-First Search starting from the root node (which is node 0) of the tree. It calculates the sum of values of each subtree. The critical points are:

    • If the subtree's value sum equals the target value t (meaning this subtree can constitute a standalone component), the dfs returns 0, indicating the potential edge to cut.
    • If the subtree's sum exceeds the target value t, or if collecting this subtree's sum would exceed t for any component, dfs returns -1, which indicates that this partitioning configuration is invalid.
  • The main part of the solution involves the loop for k in range(min(n, s // mx), 1, -1):. This loop seeks a k that is a divisor of s. It attempts to partition the tree into k components with equal values starting from the largest possible k to 2. The reason behind this is that we wish to maximize the number of edges we can delete (which corresponds to k - 1). The maximum possible value of k is dictated by the total sum s and the maximum node value mx, as s divided by mx gives an upper bound on k.

  • Every iteration checks if s is divisible by k by checking if s % k == 0:. If the condition holds, it sets the target value t to s // k.

  • Then, it calls dfs(0, -1). If dfs traverses the entire tree and still returns 0, meaning it successfully identified components with value equal to t, then we found a successful partition count k.

  • The solution returns k - 1 because if we can partition the tree into k equal components, then there are k - 1 edges that we can remove to separate each component.

  • If no value for k results in a successful partition, the solution returns 0.

The algorithm effectively balances between the depth-first traversal to calculate subcomponent sums and the strategy of checking from the highest possible partition count. By combining these two, it successfully finds the maximum number of deletable edges to ensure all connected components of the tree have the same value.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How many ways can you arrange the three letters A, B and C?

Example Walkthrough

Let's illustrate the solution approach using a small example:

Suppose we have n = 4 nodes with values nums = [1, 2, 2, 1] and edges edges = [[0, 1], [1, 2], [1, 3]]. The tree can be visualized as follows:

1    0(1)
2     |
3    1(2)
4   /   \
52(2)  3(1)

The values in parentheses represent the nums values for each node.

We are looking to maximize the number of removable edges while ensuring that each resulting connected component has the same sum of values.

Step 1 (Initialize the graph):

We construct an adjacency list from the edges:

1g: {
2  0: [1],
3  1: [0, 2, 3],
4  2: [1],
5  3: [1]
6}

Step 2 (Calculate the total sum s of all nodes and determine possible k):

Total s is 1 + 2 + 2 + 1 = 6. We can partition the tree into components with equal sums only if s is divisible by k. So we could try k=2 or k=3, since 6 is not divisible by 4.

Step 3 (Depth-First Search to find possible partitions):

We start with the maximum possible k, which is s divided by the maximum value in nums. Since s = 6 and the maximum value is 2, we initially try for k = 3.

We set our target sum t = s / k, which is 6 / 3 = 2. We'd need to find three components where the sum is 2 in each, but since our individual subtree sums are either 1 or greater than 2, this isn't possible. We move onto k = 2.

With k = 2, the target sum t becomes 6 / 2 = 3. We perform DFS to find sum of subtrees:

  • Starting from root (0), we have a value 1.
  • We move to node 1 with value 2, the running sum is now 3.
    • Check child node 2, which would add 2, making the running sum 5.
    • Check child node 3, which would add 1, making the running sum 4.

In both cases for node 1, the running sum exceeds t=3, thus we cannot form a component from this subtree that equals exactly t. However, if we consider the subtree rooted at node 1 as a separate part, its sum is 2 + 2 + 1 = 5. The remaining component (node 0) has a sum of 1. This does not satisfy our conditions, so this partition attempt fails.

Since no value of k yielded a successful partition in this example, the answer is 0: we cannot remove any edges that would result in equal-sum components.

In a case where we would find a subtree that matches our target t, the DFS would effectively "cut" the edge connecting that subtree to the larger tree and return a count that enabled us to determine if that "cut" was valid. With a valid cut, and a subsequent valid partition scheme, we would report the number of edges we can remove to fulfill the problem's conditions.

Solution Implementation

1from collections import defaultdict
2
3class Solution:
4    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:
5        # Recursive depth-first search function to check if a component can have the desired sum 'target_sum'.
6        def dfs(node, parent):
7            sub_tree_sum = nums[node]
8            for neighbor in graph[node]:
9                if neighbor != parent:
10                    sub_component_sum = dfs(neighbor, node)
11                    # If any subcomponent sum is -1, the partition isn't possible.
12                    if sub_component_sum == -1:
13                        return -1
14                    sub_tree_sum += sub_component_sum
15            # If the sub_tree_sum is greater than the desired target_sum,
16            # the partition isn't possible.
17            if sub_tree_sum > target_sum:
18                return -1
19            # If sub_tree_sum equals target_sum, we can form a component,
20            # and we return 0 to signify this.
21            return sub_tree_sum if sub_tree_sum < target_sum else 0
22
23        # The number of nodes in the tree.
24        num_nodes = len(nums)
25        # Creating a graph representation of the tree from edge list.
26        graph = defaultdict(list)
27        for a, b in edges:
28            graph[a].append(b)
29            graph[b].append(a)
30      
31        # The sum of all node values.
32        total_sum = sum(nums)
33        # The maximum value among all node values.
34        max_num = max(nums)
35
36        # Trying to find the max number of components possible, greater components will have smaller values.
37        for num_components in range(min(num_nodes, total_sum // max_num), 1, -1):
38            # If total_sum is divisible by num_components, we calculate the target_sum 
39            # value a component must sum up to.
40            if total_sum % num_components == 0:
41                target_sum = total_sum // num_components
42                # Run DFS to check if we can form a component with the target_sum.
43                # If yes, then we found the maximum number of components possible
44                # and return 'num_components - 1' as the answer.
45                if dfs(0, -1) == 0:
46                    return num_components - 1
47        # Return 0 if no valid partitioning is found.
48        return 0
49
1class Solution {
2    private List<Integer>[] graph; // Graph representation using adjacency lists
3    private int[] nodeValues;      // Stores the values at each node
4    private int targetValue;       // The target value for each component
5
6    // Main method to calculate maximum component value after removing edges
7    public int componentValue(int[] nums, int[][] edges) {
8        int n = nums.length;
9        graph = new List[n];
10        this.nodeValues = nums;
11        Arrays.setAll(graph, k -> new ArrayList<>());
12        // Building the undirected graph
13        for (int[] edge : edges) {
14            int from = edge[0], to = edge[1];
15            graph[from].add(to);
16            graph[to].add(from);
17        }
18      
19        // Calculate the total sum of values and the maximum value in array
20        int sum = sum(nodeValues), max = max(nodeValues);
21
22        // Iterate from the highest potential component value down to 2
23        for (int k = Math.min(n, sum / max); k > 1; --k) {
24            if (sum % k == 0) { // Check if it's possible to divide into k components
25                targetValue = sum / k; // Set the target value for a single component
26                // DFS to check if we can form a component with the target value
27                if (dfs(0, -1) == 0) {
28                    return k - 1; // Return the number of edges to remove
29                }
30            }
31        }
32        // If no partition is found, return 0
33        return 0;
34    }
35
36    // DFS function to explore graph and validate components
37    private int dfs(int currentNode, int parent) {
38        int currentValue = nodeValues[currentNode];
39        for (int neighbor : graph[currentNode]) {
40            if (neighbor != parent) {
41                int subtreeValueSum = dfs(neighbor, currentNode);
42                // If a subtree cannot form a component, propagate -1 up
43                if (subtreeValueSum == -1) {
44                    return -1;
45                }
46                currentValue += subtreeValueSum;
47            }
48        }
49        // If the current sum exceeds target, return -1 indicating failure
50        if (currentValue > targetValue) {
51            return -1;
52        }
53        // If the current sum equals target, we can form a component (return 0)
54        // Otherwise, return the current sum for further evaluation in the parent node
55        return currentValue == targetValue ? 0 : currentValue;
56    }
57
58    // Utility method to calculate the sum of an array
59    private int sum(int[] arr) {
60        int totalSum = 0;
61        for (int value : arr) {
62            totalSum += value;
63        }
64        return totalSum;
65    }
66
67    // Utility method to find the maximum value in an array
68    private int max(int[] arr) {
69        int maxValue = arr[0];
70        for (int value : arr) {
71            maxValue = Math.max(maxValue, value);
72        }
73        return maxValue;
74    }
75}
76
1#include <vector>
2#include <numeric>
3#include <algorithm>
4#include <unordered_map>
5#include <functional>
6
7class Solution {
8public:
9    int componentValue(std::vector<int>& nums, std::vector<std::vector<int>>& edges) {
10        int numNodes = nums.size();
11        int sumValues = std::accumulate(nums.begin(), nums.end(), 0);
12        int maxValue = *std::max_element(nums.begin(), nums.end());
13        int targetValue = 0;
14        std::unordered_map<int, std::vector<int>> graph;
15      
16        // Building the adjacency list for the graph
17        for (auto& edge : edges) {
18            int from = edge[0], to = edge[1];
19            graph[from].push_back(to);
20            graph[to].push_back(from);
21        }
22      
23        // Depth-first search to check whether we can divide the graph into components
24        // with the sum of values equal to 'targetValue'
25        std::function<int(int, int)> dfs = [&](int node, int parent) -> int {
26            int sum = nums[node];
27            for (int neighbor : graph[node]) {
28                if (neighbor != parent) {
29                    int subtreeSum = dfs(neighbor, node);
30                    if (subtreeSum == -1) return -1;
31                    sum += subtreeSum;
32                }
33            }
34            // If the sum exceeds the targetValue or is just right,
35            // we either return -1 or reset the sum for this subtree
36            if (sum > targetValue) return -1;
37            return sum < targetValue ? sum : 0;
38        };
39      
40        // Iterating from the minimum possible number of components to 2
41        // We cannot have more components than the number of nodes
42        for (int numComponents = std::min(numNodes, sumValues / maxValue); numComponents > 1; --numComponents) {
43            if (sumValues % numComponents == 0) {
44                targetValue = sumValues / numComponents;
45                // If the DFS traversal returns 0, it means we can partition
46                // the graph into 'numComponents' components, thus we return 'numComponents - 1'
47                if (dfs(0, -1) == 0) {
48                    return numComponents - 1;
49                }
50            }
51        }
52      
53        // If no partition is possible, return 0
54        return 0;
55    }
56};
57
1// Importing necessary utilities from external libraries
2// Note that in TypeScript/JavaScript, you don't need to import these, they are part of the standard library.
3
4// Data structure representing a graph
5const graph: Record<number, number[]> = {};
6
7// The DFS function that will be used to determine if the graph can be split into components
8// with a sum of 'targetValue'
9function dfs(node: number, parent: number): number {
10    let sum = nums[node];
11    for (let neighbor of graph[node] || []) {
12        if (neighbor !== parent) {
13            let subtreeSum = dfs(neighbor, node);
14            if (subtreeSum === -1) return -1;
15            sum += subtreeSum;
16        }
17    }
18    // If the sum is greater than 'targetValue', return -1,
19    // if it's exactly 'targetValue', return 0 to reset the sum
20    if (sum > targetValue) return -1;
21    return sum < targetValue ? sum : 0;
22}
23
24// Main function that calculates the component value of the graph
25function componentValue(nums: number[], edges: number[][]): number {
26    let numNodes = nums.length;
27    let sumValues = nums.reduce((a, b) => a + b, 0);
28    let maxValue = Math.max(...nums);
29    let targetValue = 0;
30
31    // Build the adjacency list representation of the graph from edges
32    for (let edge of edges) {
33        let from = edge[0], to = edge[1];
34        if (!graph[from]) graph[from] = [];
35        if (!graph[to]) graph[to] = [];
36        graph[from].push(to);
37        graph[to].push(from);
38    }
39  
40    // Iterate from the minimum possible number of components to 2
41    // If it's not possible to form components, return 0
42    for (let numComponents = Math.min(numNodes, Math.floor(sumValues / maxValue)); numComponents > 1; --numComponents) {
43        if (sumValues % numComponents === 0) {
44            targetValue = sumValues / numComponents;
45            // If the DFS traversal returns 0, we can partition the graph
46            // into 'numComponents' components, thus we return 'numComponents - 1'
47            if (dfs(0, -1) === 0) {
48                return numComponents - 1;
49            }
50        }
51    }
52  
53    // If no partition is possible, return 0
54    return 0;
55}
56

Time and Space Complexity

Time Complexity

The time complexity of the given code can be broken down into two main parts: the construction of the graph and the depth-first search (DFS) operation.

  • Graph Construction: The loop over the list of edges which constructs the adjacency list representation of the graph runs in O(E), where E is the number of edges. Since we're working with a tree (as implied by the nature of the problem), the number of edges is E = N - 1, where N is the number of nodes. Hence, constructing the graph takes O(N) time.

  • Depth-First Search (DFS): The main for-loop runs from s // mx down to 1. In the worst case, this would be O(N). The DFS function is called once for each node in the worst case, and in each call, it iterates over all the adjacent nodes. Because it's a tree, there are no repeated edges for each node, so total iterations of all DFS calls amount to O(N) as well. Therefore, the DFS complexity is O(N^2) in the worst case.

Overall, the loop that iterates from s // mx to 1 combines with the DFS to form a nested loop, so the total time complexity is O(N^2).

Space Complexity

The space complexity of the code is dominated by the recursion stack from the DFS and the storage of graph g.

  • Graph Storage: The graph g is stored as an adjacency list, which takes O(V + E) space where V is the number of vertices and E is the number of edges. For a tree, since E = V - 1, the space required for the graph is O(N).

  • DFS Recursion Stack: In the worst case, DFS could go as deep as the height of the tree, which in the case of a skewed tree (worst case) is O(N). Thus, the worst-case space complexity due to the recursion stack is also O(N).

Combining these factors, the total space complexity of the algorithm is O(N).

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄