2440. Create Components With Same Value LeetCode Solution

In this guide, you will get 2440. Create Components With Same Value LeetCode Solution with the best time and space complexity. The solution to Create Components With Same Value problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Create Components With Same Value solution in C++
Create Components With Same Value solution in Java
Create Components With Same Value solution in Python
Additional Resources

2440. Create Components With Same Value LeetCode Solution image

Problem Statement of Create Components With Same Value

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.

Complexity Analysis

Time Complexity: O(|\sqrt{\Sigma\texttt{nums[i]}}| \cdot n)
Space Complexity: O(n)

2440. Create Components With Same Value LeetCode Solution in C++

class Solution {
 public:
  int componentValue(vector<int>& nums, vector<vector<int>>& edges) {
    const int n = nums.size();
    const int sum = accumulate(nums.begin(), nums.end(), 0);
    vector<vector<int>> tree(n);

    for (const vector<int>& edge : edges) {
      const int u = edge[0];
      const int v = edge[1];
      tree[u].push_back(v);
      tree[v].push_back(u);
    }

    for (int i = n; i > 1; --i)
      // Split the tree into i parts, i.e. delete (i - 1) edges.
      if (sum % i == 0 && dfs(nums, tree, 0, sum / i, vector<bool>(n)) == 0)
        return i - 1;

    return 0;
  }

 private:
  static constexpr int kMax = 1'000'000'000;

  // Returns the sum of the subtree rooted at u substracting the sum of the
  // deleted subtrees.
  int dfs(const vector<int>& nums, const vector<vector<int>>& tree, int u,
          int target, vector<bool>&& seen) {
    int sum = nums[u];
    seen[u] = true;

    for (const int v : tree[u]) {
      if (seen[v])
        continue;
      sum += dfs(nums, tree, v, target, std::move(seen));
      if (sum > target)
        return kMax;
    }

    // Delete the tree that has sum == target.
    if (sum == target)
      return 0;
    return sum;
  }
};
/* code provided by PROGIEZ */

2440. Create Components With Same Value LeetCode Solution in Java

class Solution {
  public int componentValue(int[] nums, int[][] edges) {
    final int n = nums.length;
    final int sum = Arrays.stream(nums).sum();
    List<Integer>[] tree = new List[n];

    for (int i = 0; i < tree.length; ++i)
      tree[i] = new ArrayList<>();

    for (int[] edge : edges) {
      final int u = edge[0];
      final int v = edge[1];
      tree[u].add(v);
      tree[v].add(u);
    }

    for (int i = n; i > 1; --i)
      // Split the tree into i parts, i.e. delete (i - 1) edges.
      if (sum % i == 0 && dfs(nums, tree, 0, sum / i, new boolean[n]) == 0)
        return i - 1;

    return 0;
  }

  private static final int kMax = 1_000_000_000;

  // Returns the sum of the subtree rooted at u substracting the sum of the deleted subtrees.
  private int dfs(int[] nums, List<Integer>[] tree, int u, int target, boolean[] seen) {
    int sum = nums[u];
    seen[u] = true;

    for (final int v : tree[u]) {
      if (seen[v])
        continue;
      sum += dfs(nums, tree, v, target, seen);
      if (sum > target)
        return kMax;
    }

    // Delete the tree that has sum == target.
    if (sum == target)
      return 0;
    return sum;
  }
}
// code provided by PROGIEZ

2440. Create Components With Same Value LeetCode Solution in Python

class Solution:
  def componentValue(self, nums: list[int], edges: list[list[int]]) -> int:
    kMax = 1_000_000_000
    n = len(nums)
    summ = sum(nums)
    tree = [[] for _ in range(n)]

    for u, v in edges:
      tree[u].append(v)
      tree[v].append(u)

    def dfs(u: int, target: int, seen: set[bool]) -> int:
      """
      Returns the sum of the subtree rooted at u substracting the sum of the
      deleted subtrees.
      """
      summ = nums[u]
      seen.add(u)

      for v in tree[u]:
        if v in seen:
          continue
        summ += dfs(v, target, seen)
        if summ > target:
          return kMax

      # Delete the tree that has sum == target.
      if summ == target:
        return 0
      return summ

    for i in range(n, 1, -1):
      # Split the tree into i parts, i.e. delete (i - 1) edges.
      if summ % i == 0 and dfs(0, summ // i, set()) == 0:
        return i - 1

    return 0
 # code by PROGIEZ