Scale Engineer

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
MathEnumeration
Algorithms
Depth-First Search
Data structures
ArrayTree
Companies
Sprinklr

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 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 * 104
  • 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:

  1. Build a graph: We create an adjacency list representing the graph formed by the edges we decided to keep.
  2. 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.
  3. 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.
  4. 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.

// Conceptual implementation of the brute-force approach.// This will be too slow for the given constraints (Time Limit Exceeded).class Solution {    public int componentValue(int[] nums, int[][] edges) {        int n = nums.length;        if (n <= 1) {            return 0;        }        int numEdges = edges.length;        int maxDeleted = 0;         for (int i = 0; i < (1 << numEdges); i++) {            List<Integer>[] adj = new ArrayList[n];            for (int j = 0; j < n; j++) {                adj[j] = new ArrayList<>();            }            int deletedCount = 0;             for (int j = 0; j < numEdges; j++) {                if (((i >> j) & 1) == 1) { // Edge j is deleted                    deletedCount++;                } else { // Edge j is kept                    adj[edges[j][0]].add(edges[j][1]);                    adj[edges[j][1]].add(edges[j][0]);                }            }             List<Long> componentSums = new ArrayList<>();            boolean[] visited = new boolean[n];            for (int j = 0; j < n; j++) {                if (!visited[j]) {                    long currentSum = 0;                    Queue<Integer> q = new LinkedList<>();                    q.add(j);                    visited[j] = true;                    while (!q.isEmpty()) {                        int u = q.poll();                        currentSum += nums[u];                        for (int v : adj[u]) {                            if (!visited[v]) {                                visited[v] = true;                                q.add(v);                            }                        }                    }                    componentSums.add(currentSum);                }            }             boolean allEqual = true;            if (componentSums.size() > 1) {                long firstSum = componentSums.get(0);                for (int j = 1; j < componentSums.size(); j++) {                    if (componentSums.get(j) != firstSum) {                        allEqual = false;                        break;                    }                }            }             if (allEqual) {                maxDeleted = Math.max(maxDeleted, deletedCount);            }        }        return maxDeleted;    }}

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).

Solutions

class Solution {private  List<Integer>[] g;private  int[] nums;private  int t;public  int componentValue(int[] nums, int[][] edges) {    int n = nums.length;    g = new List[n];    this.nums = nums;    Arrays.setAll(g, k->new ArrayList<>());    for (var e : edges) {      int a = e[0], b = e[1];      g[a].add(b);      g[b].add(a);    }    int s = sum(nums), mx = max(nums);    for (int k = Math.min(n, s / mx); k > 1; --k) {      if (s % k == 0) {        t = s / k;        if (dfs(0, -1) == 0) {          return k - 1;        }      }    }    return 0;  }private  int dfs(int i, int fa) {    int x = nums[i];    for (int j : g[i]) {      if (j != fa) {        int y = dfs(j, i);        if (y == -1) {          return -1;        }        x += y;      }    }    if (x > t) {      return -1;    }    return x < t ? x : 0;  }private  int sum(int[] arr) {    int x = 0;    for (int v : arr) {      x += v;    }    return x;  }private  int max(int[] arr) {    int x = arr[0];    for (int v : arr) {      x = Math.max(x, v);    }    return x;  }}

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 →

Next problem