1376. Time Needed to Inform All Employees

#bfs #graph

Problem

Time Needed to Inform All Employees - LeetCodeLeetCode

Intuition

Time Complexity

Space Complexity

Solution

class Solution {
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        // n -> manager.length (number of employees)
        // Time Complexity: O(n) 
        // O(n) -> Build graph || O(n) -> BFS traversal
        // O(n) + O(n) = 2 O(n) = O(n)

        // Space Complexity: O(n)
        // O(n) -> Graph || O(n) -> Queue
        // O(n) + O(n) = 2 O(n) = O(n)
        
        // Build the hierarchy graph
        Map<Integer, List<Integer>> graph = new HashMap<>();

        // Traverse each employee and assign them to their respective managers in the graph
        for (int emp = 0; emp < manager.length; emp++) {
            int mgr = manager[emp];
            graph.putIfAbsent(mgr, new ArrayList<>());
            graph.get(mgr).add(emp);
        }

        int count = Integer.MIN_VALUE;

        // Use a queue to perform breadth-first traversal of the graph
        Deque<int[]> queue = new ArrayDeque<>();
        // Start with the root manager (CEO) and initialize the cumulative time as 0
        queue.offer(new int[]{headID, 0});

        // Continue traversal while there are managers in the queue
        while (!queue.isEmpty()) {
            int[] point = queue.poll();
            int managerAtCurrentLevel = point[0];
            int cumulativeTime = point[1];

            // Update the maximum cumulative time encountered so far
            count = Math.max(count, cumulativeTime);

            // Check if the current manager has any subordinates
            if (graph.containsKey(managerAtCurrentLevel)) {
                // Process each subordinate of the current manager
                for (int emp : graph.get(managerAtCurrentLevel)) {
                    // Add the subordinate to the queue with an updated cumulative time
                    queue.offer(new int[]{emp, cumulativeTime + informTime[managerAtCurrentLevel]});
                }
            }
        }

        // The maximum cumulative time represents the total time for the news to reach all employees
        return count;
    }
}