LeetCode 1270: All People Report to the Given Manager
Problem Description
Explanation:
To solve this problem, we can start by creating a graph where the key is the manager and the value is a list of employees reporting to that manager. Then, we can perform a depth-first search (DFS) starting from the given manager to find all employees reporting to this manager.
Algorithm:
- Create a graph where the key is the manager and the value is a list of employees reporting to that manager.
- Perform a depth-first search (DFS) starting from the given manager to find all employees reporting to this manager.
Time Complexity:
The time complexity of this solution is O(V + E), where V is the number of vertices (managers) and E is the number of edges (relationships between managers and employees).
Space Complexity:
The space complexity of this solution is O(V + E) for storing the graph and the visited set.
:
Solutions
class Solution {
public List<Integer> countSubordinates(int n, int[][] manager, int[] informTime) {
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int i = 0; i < n; i++) {
graph.putIfAbsent(manager[i][0], new ArrayList<>());
graph.get(manager[i][0]).add(i);
}
return dfs(graph, informTime, 0);
}
private List<Integer> dfs(Map<Integer, List<Integer>> graph, int[] informTime, int manager) {
List<Integer> subordinates = new ArrayList<>();
if (graph.containsKey(manager)) {
for (int subordinate : graph.get(manager)) {
List<Integer> subordinatesOfSubordinate = dfs(graph, informTime, subordinate);
subordinates.add(informTime[manager] + Collections.max(subordinatesOfSubordinate));
}
}
return subordinates;
}
}Loading editor...