Time Needed to Inform All Employees — LeetCode 1376 Python Solution

The problem

A company has n employees with a unique ID for each employee from 0 to n - 1. The head of the company is the one with headID.

Example

Input

n = 1, headID = 0, manager = [-1], informTime = [0]

Output

0

Explanation

The head of the company is the only employee in the company.

Python solution

class Solution:
    def numOfMinutes(
        self, n: int, headID: int, manager: List[int], informTime: List[int]
    ) -> int:
        def dfs(i: int) -> int:
            ans = 0
            for j in g[i]:
                ans = max(ans, dfs(j) + informTime[i])
            return ans

        g = defaultdict(list)
        for i, x in enumerate(manager):
            g[x].append(i)
        return dfs(headID)

Complexity

Pattern: Tree Traversal

Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 1376. Time Needed to Inform All Employees is filed here because LeetCode tags it Tree, which is the vocabulary this hub collects.

The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Related problems