---
tags: leetcode
---

# [1376. Time Needed to Inform All Employees](https://leetcode.com/problems/time-needed-to-inform-all-employees)
---
# My Solution
## Solution 1
### The Key Idea for Solving This Coding Question
### C++ Code

class Solution {
public:
    int numOfMinutes(int n, int headID, vector<int> &manager, vector<int> &informTime) {
        vector<vector<int>> tree(n);  // tree, adjacency list

        // Use adjacency list to build the tree/graph.
        for (int i = 0; i < n; ++i) {
            if (i == headID) {
                continue;
            }
            tree[manager[i]].push_back(i);
        }

        return dfs(tree, headID, informTime);
    }

private:
    int dfs(vector<vector<int>> &tree, int currID, vector<int> &informTime) {
        if (tree[currID].empty()) {
            // currID has no any subordinates. It is a leaf.
            return 0;
        }

        int timeNeeded = 0;
        for (auto &nextID : tree[currID]) {
            timeNeeded = max(timeNeeded, dfs(tree, nextID, informTime));
        }

        return timeNeeded + informTime[currID];
    }
};

### Time Complexity
$O(n)$
$n$ is the number of employees.
### Space Complexity
$O(H)$
$H$ is the height of the tree.
## Solution 2
### The Key Idea for Solving This Coding Question
### C++ Code

struct nodeData {
    int accumulatedTime;
    int id;
    nodeData(int accumulatedTime, int id) : accumulatedTime(accumulatedTime), id(id) {}
};

class Solution {
public:
    int numOfMinutes(int n, int headID, vector<int> &manager, vector<int> informTime) {
        vector<vector<int>> graph(n);
        for (int i = 0; i < manager.size(); ++i) {
            if (i == headID) {
                continue;
            }
            graph[manager[i]].push_back(i);
        }
        
        queue<nodeData> q;
        int totalTime = 0;
        
        q.push(nodeData(0, headID));
        while (!q.empty()) {
            nodeData curr = q.front();
            q.pop();
            
            if (graph[curr.id].empty()) {
                if (totalTime < curr.accumulatedTime) {
                    totalTime = curr.accumulatedTime;
                }
            }
            
            for (auto &nextID : graph[curr.id]) {
                q.push(nodeData(curr.accumulatedTime + informTime[curr.id], nextID));
            }
        }
        
        return totalTime;
    }
};

### Time Complexity
$O(n)$
$n$ is the number of employees.
### Space Complexity
$O(n)$
# Miscellaneous
<!--
# Test Cases

1
0
[-1]
[0]

6
2
[2,2,-1,2,2,2]
[0,0,1,0,0,0]

6
0
[-1,0,0,1,1,2]
[3,2,4,0,0,0]

* Wrong Answer:

15
0
[-1,0,0,1,1,2,2,3,3,4,4,5,5,6,6]
[1,1,1,1,1,1,1,0,0,0,0,0,0,0,0]

* Time Limit Exceeded
https://leetcode.com/submissions/detail/771498356/testcase/
-->