HardNo. 2872
Maximum Number of K-Divisible Components — LeetCode 2872 Python Solution
- Pattern
- Tree Traversal
- Topics
- Tree, Depth-First Search
- Reading time
- 4 min
- Source
- leetcode.com
The problem
There is an undirected tree with n nodes labeled from 0 to n - 1. You are given the integer n and 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.
Example
- Input
- n = 5, edges = [[0,2],[1,2],[1,3],[2,4]], values = [1,8,1,4,4], k = 6
- Output
- 2
- Explanation
- We remove the edge connecting node 1 with 2. The resulting split is valid because:
Python solution
class Solution:
def maxKDivisibleComponents(
self, n: int, edges: List[List[int]], values: List[int], k: int
) -> int:
def dfs(i: int, fa: int) -> int:
s = values[i]
for j in g[i]:
if j != fa:
s += dfs(j, i)
nonlocal ans
ans += s % k == 0
return s
g = [[] for _ in range(n)]
for a, b in edges:
g[a].append(b)
g[b].append(a)
ans = 0
dfs(0, -1)
return ansComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)where n is the number of nodes in the tree
Pattern: Tree Traversal
Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 2872. Maximum Number of K-Divisible Components is filed here because LeetCode tags it Tree, which is the vocabulary this hub collects.
The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0098 | Validate Binary Search Tree | Medium |
| 0099 | Recover Binary Search Tree | Medium |
| 0100 | Same Tree | Easy |
| 0101 | Symmetric Tree | Easy |
| 0104 | Maximum Depth of Binary Tree | Easy |
| 0110 | Balanced Binary Tree | Easy |
Frequently asked questions
- How hard is LeetCode 2872. Maximum Number of K-Divisible Components?
LeetCode 2872. Maximum Number of K-Divisible Components is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2872. Maximum Number of K-Divisible Components?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 2872. Maximum Number of K-Divisible Components?
The Python solution on this page uses O(n), where n is the number of nodes in the tree auxiliary space.
- What topics does LeetCode 2872. Maximum Number of K-Divisible Components cover?
LeetCode 2872. Maximum Number of K-Divisible Components is tagged Tree and Depth-First Search on LeetCode.