2872. Maximum Number of K-Divisible Components

📝 Problem Details

• Title: 2872. Maximum Number of K-Divisible Components
• Link: https://leetcode.com/problems/maximum-number-of-k-divisible-components/
• Difficulty: Hard
• Tags/Categories: Trees DFS

💭What Were My Initial Thoughts?

- construct the tree given n nodes
- separate tree into components by:
	- be greedy
	- DFS
	- go down to the bottom of the tree and recursively go up until we reach a sum of values that is divisible by k, then we increment by one 

🤔What Did I Struggle With?

- got confused on the use of the term graph and struggled to figure out how to construct the tree 
- forgot that a tree is really just a special kind of graph:
	- a conneted, undirected graph with n nodes and n-1 edges
	- it is acyclic and every pair of nodes is connected by exactly one path 

💡 Explanation of Solution

- represent the tree as an adjaceny list
	- the problem doesnt explicitly provide the graph, so create it with a void function and return a 2D vector representing nodes and their edges 

- splitting the tree into components:
	- start DFS from the root (node 0)
	- as you traverse 
		- maintaint he sum of the current subtree
		- if a subtree's sum if divisible by k, cut that component and reset its sum to 0
	- return the sum of the current subtree to the parent 

⌛ Complexity Analysis

Time Complexity: O(n)
- tree construction takes O(n) where n is the number of nodes required for our tree
- DFS traversal is O(n) as each node and edge is visited once

Space Complexity:
- adjacency list O(n + e) where e is the number of edges
- DFS recursion stack O(h) where h is the height of the tree

💻 Implementation of Solution

class Solution {
public:
    int maxKDivisibleComponents(int n, vector<vector<int>> &edges,
                                vector<int> &values, int k) {
        // Step 1: Create adjacency list from edges
        vector<int> adjList[n];
        for (auto edge : edges) {
            int node1 = edge[0];
            int node2 = edge[1];
            adjList[node1].push_back(node2);
            adjList[node2].push_back(node1);
        }
        // Step 2: Initialize component count
        int componentCount = 0;
 
        // Step 3: Start DFS traversal from node 0
        dfs(0, -1, adjList, values, k, componentCount);
 
        // Step 4: Return the total number of components
        return componentCount;
    }
 
private:
    int dfs(int currentNode, int parentNode, vector<int> adjList[],
            vector<int> &nodeValues, int k, int &componentCount) {
        // Step 1: Initialize sum for the current subtree
        int sum = 0;
 
        // Step 2: Traverse all neighbors
        for (auto neighborNode : adjList[currentNode]) {
            if (neighborNode != parentNode) {
                // Recursive call to process the subtree rooted at the neighbor
                sum += dfs(neighborNode, currentNode, adjList, nodeValues, k,
                           componentCount);
                sum %= k;  // Ensure the sum stays within bounds
            }
        }
 
        // Step 3: Add the value of the current node to the sum
        sum += nodeValues[currentNode];
 
        // Step 4: Check if the sum is divisible by k
        sum %= k;
        if (sum == 0) componentCount++;
 
        // Step 5: Return the computed sum for the current subtree
        return sum;
    }
};