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

0% completed

Vote For New Content
Time Needed to Inform All Employees (medium)
On this page

Problem Statement

Examples

Try it yourself

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.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

On this page

Problem Statement

Examples

Try it yourself