We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Time Needed to Inform All Employees

Number: 1492

Difficulty: Medium

Paid? No

Companies: Google, Microsoft, Amazon, Verily

Problem Description

We are given a company structure represented as a tree with n employees, where each employee (except the head) has a direct manager. The head employee (with id headID) starts to inform his subordinates about urgent news. Each employee takes a specified number of minutes to inform all of his direct subordinates. The task is to calculate the total time needed to inform all employees in the company.

Key Insights

  • The company structure forms a tree with the head as the root.
  • We need to propagate the news from the head down through all branches.
  • The time taken for the news to fully propagate is determined by the longest path from the head to any leaf in the tree.
  • A Depth-First Search (DFS) efficiently traverses the tree, accumulating inform times along each branch.

Space and Time Complexity

Time Complexity: O(n) – Each employee (node) is visited once. Space Complexity: O(n) – In the worst-case, the recursion stack may hold all n nodes.

Solution

We construct an adjacency list (or tree) that maps each manager to their list of direct subordinates. Then, we perform a DFS starting from the head. For each employee, we calculate the time required to inform all their subordinates by taking the maximum time among all children and adding the current employee’s informTime. This approach correctly computes the time to disseminate the news along the longest chain in the tree.

Code Solutions

# Python solution using DFS and an adjacency list to represent the tree.
from collections import defaultdict

def numOfMinutes(n, headID, manager, informTime):
    # Build the tree: map each manager to its direct subordinates.
    tree = defaultdict(list)
    for employee, mgr in enumerate(manager):
        if mgr != -1:
            tree[mgr].append(employee)
    
    # DFS function to compute the time to inform all subordinates under 'emp'
    def dfs(emp):
        max_subordinate_time = 0
        # Traverse all direct subordinates of the employee
        for subordinate in tree[emp]:
            max_subordinate_time = max(max_subordinate_time, dfs(subordinate))
        # Total time is the current employee's inform time plus max time required by subordinates.
        return informTime[emp] + max_subordinate_time
    
    return dfs(headID)

# Example usage:
# n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
# print(numOfMinutes(6, 2, [2,2,-1,2,2,2], [0,0,1,0,0,0]))
← Back to All Questions