Time Needed to Inform All Employees solution and explanation

def numOfMinutes(n, headID, manager, informTime):
    from collections import defaultdict

    subordinate_map = defaultdict(list)
    for emp, man in enumerate(manager):
        subordinate_map[man].append(emp)

    def dfs(emp_id):
        max_time = 0
        for sub in subordinate_map[emp_id]:
            max_time = max(max_time, dfs(sub))
        return informTime[emp_id] + max_time

    return dfs(headID)

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        List<List<Integer>> subordinateMap = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            subordinateMap.add(new ArrayList<>());
        }
        for (int emp = 0; emp < n; emp++) {
            if (manager[emp] != -1) {
                subordinateMap.get(manager[emp]).add(emp);
            }
        }

        return dfs(headID, informTime, subordinateMap);
    }

    private int dfs(int empId, int[] informTime, List<List<Integer>> subordinateMap) {
        int max = 0;
        for (int subId : subordinateMap.get(empId)) {
            max = Math.max(max, dfs(subId, informTime, subordinateMap));
        }
        return informTime[empId] + max;
    }
}

function numOfMinutes(n, headID, manager, informTime) {
    const subordinateMap = Array.from({ length: n }, () => []);

    for (let i = 0; i < n; i++) {
        if (manager[i] !== -1) {
            subordinateMap[manager[i]].push(i);
        }
    }

    const queue = [[headID, 0]];
    let maxTime = 0;

    while (queue.length > 0) {
        const [current, time] = queue.shift();
        maxTime = Math.max(maxTime, time);

        for (const sub of subordinateMap[current]) {
            queue.push([sub, time + informTime[current]]);
        }
    }
    return maxTime;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int NumOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        Dictionary<int, List<int>> subordinateMap = new Dictionary<int, List<int>>();
        for (int i = 0; i < n; i++) {
            if (!subordinateMap.ContainsKey(manager[i])) {
                subordinateMap[manager[i]] = new List<int>();
            }
            subordinateMap[manager[i]].Add(i);
        }

        Queue<(int, int)> queue = new Queue<(int, int)>();
        queue.Enqueue((headID, 0));
        int maxTime = 0;

        while (queue.Count > 0) {
            var (current, time) = queue.Dequeue();
            maxTime = Math.Max(maxTime, time);

            if (subordinateMap.ContainsKey(current)) {
                foreach (var sub in subordinateMap[current]) {
                    queue.Enqueue((sub, time + informTime[current]));
                }
            }
        }
        return maxTime;
    }
}

class Solution {
public:
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        vector<vector<int>> g(n);
        for (int i = 0; i < n; ++i) {
            if (manager[i] >= 0) {
                g[manager[i]].push_back(i);
            }
        }
        function<int(int)> dfs = [&](int i) -> int {
            int ans = 0;
            for (int j : g[i]) {
                ans = max(ans, dfs(j) + informTime[i]);
            }
            return ans;
        };
        return dfs(headID);
    }
};

function numOfMinutes(n: number, headID: number, manager: number[], informTime: number[]): number {
    const g: number[][] = new Array(n).fill(0).map(() => []);
    for (let i = 0; i < n; ++i) {
        if (manager[i] !== -1) {
            g[manager[i]].push(i);
        }
    }
    const dfs = (i: number): number => {
        let ans = 0;
        for (const j of g[i]) {
            ans = Math.max(ans, dfs(j) + informTime[i]);
        }
        return ans;
    };
    return dfs(headID);
}

func numOfMinutes(n int, headID int, manager []int, informTime []int) int {
	g := make([][]int, n)
	for i, x := range manager {
		if x != -1 {
			g[x] = append(g[x], i)
		}
	}
	var dfs func(int) int
	dfs = func(i int) (ans int) {
		for _, j := range g[i] {
			ans = max(ans, dfs(j)+informTime[i])
		}
		return
	}
	return dfs(headID)
}