Grokking 195

class Solution {

  Map<Integer, List<Integer>> managerAndSub;
  int[] manager;
  int[] informTime;

  public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
    // represents manager and subordinates relationships
    this.managerAndSub = new HashMap<Integer, List<Integer>>();
    this.manager = manager;
    this.informTime = informTime;

    for (int i = 0; i < n; i++) {
      List<Integer> subordinates = managerAndSub.getOrDefault(manager[i], new ArrayList<Integer>());

      subordinates.add(i);

      managerAndSub.put(manager[i], subordinates);
    }

    return getTime(headID);
  }

  private int getTime(int managerID) {
    // if manager has no subordinates, return 0
    if (!managerAndSub.containsKey(managerID)) {
      return 0;
    }

    List<Integer> subordinates = managerAndSub.get(managerID);

    int maxInformTime = 0;
    for (int subordinateID : subordinates) {
      maxInformTime = Math.max(maxInformTime, getTime(subordinateID));
    }

    return maxInformTime + informTime[managerID];
  }
}