Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Time Needed to Inform All Employees
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

A company has n employees, each with a unique ID from 0 to n-1. The head of the company has an ID headID.

Each employee has a direct manager, indicated by the manager array, where manager[i] is the direct manager of the i<sup>th</sup> employee. The head of the company has no manager, so manager[headID] = -1.

The company needs to inform all employees about urgent news. The head will inform their direct subordinates, who will then inform their subordinates, and so on. Each employee i needs informTime[i] minutes to inform all their direct subordinates.

Return the number of minutes needed to inform all the employees about the urgent news.

Examples

Example 1

  • Input: n: 6, headID: 2, manager: [2, 2, -1, 2, 2, 2], informTime: [0, 0, 1, 0, 0, 0]
Image
  • Output: 1
  • Explanation: Employee 2 informs all subordinates (0, 1, 3, 4, 5) in 1 minute.

Example 2

  • Input: n: 4, headID: 0, manager: [-1, 0, 0, 1], informTime: [2, 1, 0, 0]
Image
  • Output: 3
  • Explanation:
    • Employee 0 informs 1 and 2 in 2 minutes.
    • Employee 1 informs 3 in 1 more minute. Total time = 2 + 1 = 3 minutes.

Example 3

  • Input: n: 7, headID: 6, manager: [1, 3, 3, 4, 6, 6, -1], informTime: [0, 2, 0, 1, 2, 0, 1]
  • Output: 6
  • Explanation: Employee 6 informs 4 and 5 in 1 minute, 4 informs 3 in 2 minute, 3 informs 1 and 2 in 1 minute,and 1 informs 0 in 2 minutes. Total time = 1 + 2 + 1 + 2 = 6 minutes.

Constraints:

  • 1 <= n <= 10<sup>5</sup>
  • 0 <= headID < n
  • manager.length == n
  • 0 <= manager[i] < n
  • manager[headID] == -1
  • informTime.length == n
  • 0 <= informTime[i] <= 1000
  • informTime[i] == 0 if employee i has no subordinates.
  • It is guaranteed that all the employees can be informed.

Solution

To solve this problem, we'll use a depth-first search (DFS) approach. We treat the employee-manager relationships as a tree, where the root is the head of the company. We'll traverse this tree starting from the root (headID) and calculate the total time required to inform all employees. For each employee, we will recursively calculate the time needed for their subordinates and add their inform time. This approach ensures that we account for the maximum time required at each level of the hierarchy.

Using DFS is effective because it allows us to explore each branch of the tree thoroughly before moving to the next. This ensures that we capture the maximum time needed for any branch, leading to an accurate calculation of the total inform time.

Step-by-Step Algorithm

  1. Initialize Data Structures:

    • Create a list (or equivalent in other languages) called employeeTree to represent the hierarchy of employees. Keys are managers and values are lists of their subordinates.
    • Initialize a variable totalTime to store the maximum time required to inform all employees.

  2. Build the Employee Hierarchy:

    • Iterate through each employee i from 0 to n-1.
    • If manager[i] is not -1, add i to the list of subordinates for manager[i] in employeeTree.

  3. Depth-First Search (DFS) Traversal:

    • Define a recursive function calculateTime(employeeTree, timeToInform, currentEmployee, currentTime):
      • Update totalTime to be the maximum of totalTime and currentTime.
      • For each subordinate of currentEmployee, call calculateTime recursively, updating currentTime by adding timeToInform[currentEmployee].

  4. Start DFS from Head:

    • Call the calculateTime function with the head of the company (headID), timeToInform array, and initial time 0.

  5. Return Result:

    • Return totalTime as the result, which is the total time needed to inform all employees.

Algorithm Walkthrough

Using the input:

  • n: 7
  • headID: 6
  • manager: [1, 3, 3, 4, 6, 6, -1]
  • informTime: [0, 2, 0, 1, 2, 0, 1]
Image

  1. Initialization:

    • employeeTree is an empty Map.
    • totalTime is set to 0.

  2. Build the Employee Hierarchy:

    • For employee 0, manager is 1. Add 0 to subordinates of 1: employeeTree = {1: [0]}.
    • For employee 1, manager is 3. Add 1 to subordinates of 3: employeeTree = {1: [0], 3: [1]}.
    • For employee 2, manager is 3. Add 2 to subordinates of 3: employeeTree = {1: [0], 3: [1, 2]}.
    • For employee 3, manager is 4. Add 3 to subordinates of 4: employeeTree = {1: [0], 3: [1, 2], 4: [3]}.
    • For employee 4, manager is 6. Add 4 to subordinates of 6: employeeTree = {1: [0], 3: [1, 2], 4: [3], 6: [4]}.
    • For employee 5, manager is 6. Add 5 to subordinates of 6: employeeTree = {1: [0], 3: [1, 2], 4: [3], 6: [4, 5]}.
    • For employee 6, manager is -1. No update needed.
    • Final employeeTree = {1: [0], 3: [1, 2], 4: [3], 6: [4, 5]}.

  3. DFS Traversal:

    • Start DFS from headID 6 with currentTime 0.
    • At employee 6, update totalTime to max(0, 0) = 0.
      • Visit subordinate 4, currentTime = 0 + informTime[6] = 1.
        • At employee 4, update totalTime to max(0, 1) = 1.
          • Visit subordinate 3, currentTime = 1 + informTime[4] = 3.
            • At employee 3, update totalTime to max(1, 3) = 3.
              • Visit subordinate 1, currentTime = 3 + informTime[3] = 4.
                • At employee 1, update totalTime to max(3, 4) = 4.
                  • Visit subordinate 0, currentTime = 4 + informTime[1] = 6.
                    • At employee 0, update totalTime to max(4, 6) = 6.
                  • Employee 0 has no subordinates. Return to employee 1.
              • Employee 1 has no more subordinates. Return to employee 3.
              • Visit subordinate 2, currentTime = 3 + informTime[3] = 4.
                • At employee 2, update totalTime to max(6, 4) = 6.
                • Employee 2 has no subordinates. Return to employee 3.
            • Employee 3 has no more subordinates. Return to employee 4.
          • Employee 4 has no more subordinates. Return to employee 6.
      • Visit subordinate 5, currentTime = 0 + informTime[6] = 1.
        • At employee 5, update totalTime to max(6, 1) = 6.
        • Employee 5 has no subordinates. Return to employee 6.
    • Employee 6 has no more subordinates.

  4. Return Result:

    • The total time required to inform all employees is totalTime, which is 6.

Code

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • Building the adjacency list takes O(n).
  • The DFS traversal also takes O(n) because each node (employee) is visited once.
  • Thus, the overall time complexity is O(n).

Space Complexity

  • The space needed for the adjacency list is O(n).
  • The call stack for DFS can go as deep as the height of the tree, which in the worst case is O(n).
  • Thus, the overall space complexity is O(n).

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible