Time Needed to Inform All Employees - Practice Coding Problems

Time Needed to Inform All Employees - Problem

A company has n employees with unique IDs from 0 to n - 1. The head of the company has ID headID.

Each employee has one direct manager given in the manager array where manager[i] is the direct manager of the i-th employee, and manager[headID] = -1. The subordination relationships form a tree structure.

The head wants to inform all employees of urgent news. He will inform his direct subordinates, and they will inform their subordinates, and so on until all employees know the news.

The i-th employee needs informTime[i] minutes to inform all direct subordinates. After informTime[i] minutes, all direct subordinates can start spreading the news.

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

Input & Output

Example 1 — Basic Tree Structure

$ Input: n = 6, headID = 0, manager = [-1,0,0,1,1,2], informTime = [1,1,0,0,0,0]

› Output: 2

💡 Note: Employee 0 needs 1 minute to inform employees 1 and 2. Employee 1 needs 1 minute to inform employees 3 and 4. The maximum time is 1 + 1 = 2 minutes to reach employees 3 and 4.

Example 2 — Single Path

$ Input: n = 1, headID = 0, manager = [-1], informTime = [0]

› Output: 0

💡 Note: Only one employee (the head), so no time needed to inform anyone.

Example 3 — Unbalanced Tree

$ Input: n = 4, headID = 0, manager = [-1,0,1,2], informTime = [2,1,0,0]

› Output: 3

💡 Note: Chain: 0 → 1 → 2 → 3. Total time: 2 + 1 + 0 = 3 minutes to reach employee 3.

Constraints

1 ≤ n ≤ 10⁵
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

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Company hierarchy with manager relationships and inform times

Information Flow

Information spreads from head through managers to employees

Maximum Time

Find the longest path from head to any employee

Key Takeaway

🎯 Key Insight: The problem is finding the maximum depth-weighted path in a tree, where each node contributes its inform time to the total.

Asked in

A Amazon 25 M Microsoft 18 G Google 15 F Facebook 12

The key insight is that this is a tree traversal problem where we need to find the maximum time to reach any leaf employee. The optimal approach uses DFS to traverse the tree once, calculating the maximum inform time for each subtree. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ BFS Level-by-Level	O(n)	O(n)	Use BFS to process employees level by level, accumulating time at each level
Brute Force - Check All Paths	O(n²)	O(n)	Find all paths from head to each employee and calculate time for each
DFS Tree Traversal	O(n)	O(n)	Build adjacency list and use DFS to find maximum time to any leaf

BFS Level-by-Level — Algorithm Steps

Build subordinate lists for each manager
BFS from head, processing level by level
Track maximum time across all paths

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Queue

Initialize with head employee and time 0

Process Level

For each employee, add subordinates with accumulated time

Track Maximum

Keep track of maximum time seen across all paths

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int employee;
    int time;
} QueueItem;

int solution(int n, int headID, int* manager, int* informTime) {
    // Build adjacency list
    int** subordinates = (int**)malloc(n * sizeof(int*));
    int* subCount = (int*)calloc(n, sizeof(int));
    
    // Count subordinates for each employee
    for (int i = 0; i < n; i++) {
        if (manager[i] != -1) {
            subCount[manager[i]]++;
        }
    }
    
    // Allocate space for subordinates
    for (int i = 0; i < n; i++) {
        subordinates[i] = (int*)malloc(subCount[i] * sizeof(int));
        subCount[i] = 0; // Reset to use as index
    }
    
    // Fill subordinates lists
    for (int i = 0; i < n; i++) {
        if (manager[i] != -1) {
            subordinates[manager[i]][subCount[manager[i]]++] = i;
        }
    }
    
    // BFS using array as queue
    QueueItem* queue = (QueueItem*)malloc(n * sizeof(QueueItem));
    int front = 0, rear = 0;
    queue[rear++] = (QueueItem){headID, 0};
    int maxTime = 0;
    
    while (front < rear) {
        QueueItem current = queue[front++];
        if (current.time > maxTime) {
            maxTime = current.time;
        }
        
        for (int i = 0; i < subCount[current.employee]; i++) {
            queue[rear++] = (QueueItem){subordinates[current.employee][i], current.time + informTime[current.employee]};
        }
    }
    
    // Free memory
    for (int i = 0; i < n; i++) {
        free(subordinates[i]);
    }
    free(subordinates);
    free(subCount);
    free(queue);
    
    return maxTime;
}

int main() {
    int n, headID;
    scanf("%d", &n);
    scanf("%d", &headID);
    
    int* manager = (int*)malloc(n * sizeof(int));
    int* informTime = (int*)malloc(n * sizeof(int));
    
    char line[1000];
    scanf("%s", line);
    // Simple parsing for [1,2,3] format
    char* token = strtok(line + 1, ",]");
    int i = 0;
    while (token != NULL && i < n) {
        manager[i++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    scanf("%s", line);
    token = strtok(line + 1, ",]");
    i = 0;
    while (token != NULL && i < n) {
        informTime[i++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(n, headID, manager, informTime));
    
    free(manager);
    free(informTime);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each employee is visited exactly once during BFS traversal

✓ Linear Growth

Space Complexity

O(n)

Queue can contain up to n employees, plus adjacency list storage

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

BFS Level-by-Level — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler