LeetCode | Maximum Number of K Divisible Components | C++ | Golang | Rust

LeetCode 2872 – Maximum Number of K-Divisible Components (Daily Challenge Solution)

In this video, I break down one of the smartest and most intuitive DFS-based problems: Maximum Number of K-Divisible Components.
I start by forming a key claim about subtree sums and demonstrate why it works using a clean test-case proof.

Then I visually explain the cut-edge logic — whenever a subtree sum becomes divisible by k, we conceptually cut that edge and treat that subtree as a separate component. This idea naturally leads to a DFS that accumulates subtree sums and resets them when needed.

After the full intuition, I show complete implementations in
✅ C++ (recursive lambda)
✅ Golang (anonymous function recursion)
✅ Rust (DFS with references)

This makes the solution easy to understand and reproduce in any language.

If you enjoy graph/DFS problems or want strong intuition for tree-DP style questions, this walkthrough will help you master the pattern.

⏱ Timestamps

00:00 – Problem Statement
02:39 – Strategy and Claim
09:08 – Cutting Edge Logic
12:34 – Dry run of Algorithm
16:28 – C++ Implementation
23:49 – Golang Implementation
27:53 – Rust Implementation


What you’ll learn in this video

🔹 Why the subtree-sum % k == 0 claim is correct
🔹 How “cutting off” subtrees increases component count
🔹 Why DFS returns 0 after cutting
🔹 How to implement recursive lambda DFS in C++, Go, and Rust
🔹 Clean and optimal O(n) tree traversal technique

Code Covered in the Video (C++ / Go / Rust)

Lambda-based DFS (C++)

Anonymous recursion trick (Go)

Rust DFS with mutable borrows

Building tree adjacency lists

Returning subtree sums bottom-up

If this helped, consider liking and subscribing!

I upload LeetCode Daily, algorithm intuition videos, and multi-language solutions in C++ / Golang / Rust — all explained from scratch with visuals.