Coding Interview Prep: Time Needed to Inform All Employees - C++

Here we will go over the solution to the Leetcode problem #1376: Time Needed to Inform All Employees

The problem deals with figuring out how long it would take a head of a company to send an urgent message through an organization by giving it to his subordinates, and having them send it to their subordinates.

Modeling the problem

We can use a depth-first search (DFS) approach to determine the total amount of time needed to inform all employees. We'll model the management hierarchy as a tree using an adjacency list, where each node represents an employee and edges represent direct manager-subordinate relationships.

Function: numOfMinutes

    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        // Create an adjacency list to represent the company's hierarchy
        vector<vector<int>> adjList(n);
        for (int i = 0; i < n; ++i) {
            if (manager[i] != -1) {
                adjList[manager[i]].push_back(i);
            }
        }

        // Use DFS to find the maximum time to inform all employees
        return dfs(headID, adjList, informTime);
    }

This function initializes the process of calculating the total time required to inform all employees.

• Create an adjacency list

  • We represent the company's hierarchy using an adjacency list where each index corresponds to a manager and contains a list of their direct subordinates.

• We initiate a DFS traversal starting from the head of the company to calculate the maximum time required to inform all employees.

Function: dfs

    int dfs(int curr, const vector<vector<int>>& adjList, const vector<int>& informTime) {
        int maxTime = 0;
        for (int subordinate : adjList[curr]) {
            maxTime = max(maxTime, dfs(subordinate, adjList, informTime));
        }
        return maxTime + informTime[curr];
    }

This helper function performs a depth-first search to calculate the maximum time required to inform all subordinates starting from a given employee.

1. Initialize maximum time:

   • For the current node, initialize the maximum time to inform subordinates as zero.

2. Recursive DFS call for subordinates:

   • For each subordinate of the current employee, recursively call dfs to calculate the time required to inform their subordinates. Track the maximum time needed among all subordinates.

3. Calculate total time for current node:

   • The total time for the current node is the maximum time needed to inform its subordinates plus the time the current node itself takes to inform its direct subordinates.

Wrapping it up

This approach efficiently calculates the total time required to inform all employees using DFS, ensuring that the information spreads in the minimum time possible. Such techniques are not only applicable in organizational communication but also in various network propagation problems.