Maximum Number of K-Divisible Components

Hard
Watch on YouTube ↗

Solution

class Solution {

    HashMap<Integer, List<Integer>> hmap;
    HashSet<Integer> visited;
    int count;
    public int maxKDivisibleComponents(int n, int[][] edges, int[] values, int k) {
        hmap = new HashMap<>(); // O(n)
        visited = new HashSet<>();
        for(int i=0; i<n; i++) {
            hmap.put(i, new ArrayList<>());
        }

        // adding edges
        for(int edge[] : edges) {
            // O(n)
            int src = edge[0];
            int dest = edge[1];
            hmap.get(src).add(dest);
            hmap.get(dest).add(src);
        }

        count = 0; // count of components 

        helper(0, values, k); // DFS function
        return count;

    }

    int helper(int src, int values[], int k) {
        // O(n)
        if(visited.contains(src)) {
            return 0;
        }
        visited.add(src);
        int sum = values[src];
        List<Integer> list = hmap.get(src);
        for(int curr : list) {
            sum += helper(curr, values, k);
        }

        if(sum%k==0)
            count++;
        return sum%k;
    }
}