1376 Time Needed to Inform All Employees

Techniques Used

• DFS
• Graph

Difficulty Level

• Medium
• Need to Revisit

Approach

• Create a minutes array that will store the amount of time that it takes for each employee to receive the news.
• We mark the minutes[headID] = 1 so as to distinguish it from non-visited IDs, mark the intial value of max variable as 1 to accomodate this. We will able to correct this by subtracting 1 from our ultimate result.
• At each level, call our utility find function, and keep storing its result if it is greater than the max value.
• In our find function:
  • If the minutes[x] == 0 (meaning that x has not been visited)
    • Find the manager of x (manager[x]) in the variable xManager
    • Now the value of minutes[x] will be the sum of (calling find function of xManager ID) and time[xManager](time that it takes for xManager to get the news)
• Return max - 1 (Our initial starting value was 1 greater than 0)

Complexity:

• Time Complexity: O(N^2)
• Space Complexity: O(N)

Code: Java

class Solution {


    static int[] minutes;

    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {

        minutes = new int[n];

        minutes[headID] = 1; 
        int max = 1; 

        for(int i = 0; i < n; i++){
            max = Math.max(max, find(manager, informTime, minutes, i));
        }

        return max - 1;


    }


    int find(int[] manager, int[] time, int[] mminutes, int x){

        if(minutes[x] == 0){
            int xManager = manager[x];
            minutes[x] = find(manager, time, minutes, xManager) + time[xManager];    
        }

        return minutes[x];


    }


}