Skip to main content
Talentd

Create Components With Same Value - Solution & Explanation

HardArrayMathTreeDepth-First Search21 min readAsked at: Sprinklr
Practice this problem

Problem Statement

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.

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.

This C implementation begins by computing the total sum of the node values. Using an adjacency list (represented with arrays here due to C's static nature), it prepares the tree structure, allowing for DFS traversal.

For each divisor of the total sum, it attempts to split the tree into components whose sum of nodes equals the divisor. The maximum number of deletions observed (which equals the number of unused edges) represents our solution.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * sqrt(sum(nums))) where sum(nums) is the sum of all node values as we potentially check multiple divisors and perform a DFS for each.

Space Complexity: O(n), primarily for the adjacency list and visited status arrays.

Try this approach in the editor →

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.

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.

Code

Python

Python

Complexity

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.

Try this approach in the editor →

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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Depth First Search (DFS) Approach

Time Complexity: O(n * sqrt(sum(nums))) where sum(nums) is the sum of all node values as we potentially check multiple divisors and perform a DFS for each.

Space Complexity: O(n), primarily for the adjacency list and visited status arrays.

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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS with Target Sum EnumerationO(n * d)O(n)General case for trees. Best interview approach for validating equal-sum components.
Union-Find Component AggregationO(n α(n))O(n)Useful when explicitly tracking merged components or experimenting with disjoint-set structures.

Video Solution

Biweekly Contest 89 | 6211. Create Components With Same Value • codingMohan • 1,387 views views

Watch 4 more video solutions →

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.

Ready to solve this problem?

Practice Create Components With Same Value with our built-in code editor and test cases.

Practice on FleetCode
Previous

Equal Tree Partition

Next

Maximum Number of K-Divisible Components