1376. Time Needed to Inform All Employees

1376. Time Needed to Inform All Employees

Here is the link.


C# Optimal solution using stack

uly 17, 2020
Introduction
It is the second algorithm in my Leetcode phone screen mock interview. I like to write down my thought process and think about how to expedite my problem solving thinking about using stack.

Case study
It is a good idea to talk about the solution using a test case. For example,
[1, -1, 1], and informTime array is [0, 1, 0]. How to solve the problem?

I think that it is most important for me to use an array time[] to mark visited nodes in the tree and also avoid recalculation same nodes again and again.

The quickest way is to start from any employee id, and then go through its parent node - manager id until the one solved with time[employee id]. Stack is very helpful to reverse the order, so that calculation can start from parent node in the tree first, go down child node.

First of all, set array time default value -1. And also set headId time value = 0;
Go over the test case, start from employee id = 0, time[0] = -1, so push it to the stack, manager[0] = 1, time[1] = 0. So parent node of employee id = 0 is solved already.
Next pop up nodes from stack, one by one calculate the time based on time[parent node] and informTime[parent node id].

I will add more later to make this practice more helpful for me to review.

Time complexity
It is a tree traversal algorithm, since every edge is visited once only, so it is the optimal solution.
Time complexity is O(N), N is total number of nodes.

Space complexity
Since maximum height of tree is O(N), N is total number of nodes. So space complexity worst case is O(N), average case is height of tree, O(logN).

The stack is used to store the path from leaf node to root node.

public class Solution {
    public int NumOfMinutes(int n, int headID, int[] manager, int[] informTime) {
         if(n < 0)
            return 0; 
        
        var time = new int[n];
        for(int i = 0; i < n; i++)
        {
            time[i] = -1; 
        }
        
        time[headID] = 0; // need no time
        
        for(int i = 0; i < n; i++)
        {
            var current = manager[i]; 
            if(time[i] != -1)
            {
                continue; 
            }
            
            // push current id and it's parents not solved into stack. 
            var stack = new Stack<int>(); 
            stack.Push(i);
            
            while(time[stack.Peek()] == -1)
            {
                var next = manager[stack.Peek()]; // 2
                if(time[next] == -1)
                {
                    stack.Push(next);
                }
                else 
                {
                    break; 
                }
            }
            
            var parentId = manager[stack.Peek()]; // 0
            var parentTime = informTime[parentId]; //1
            while(stack.Count > 0)
            {
                var child = stack.Pop(); // 0
                time[child] = time[parentId] + parentTime; // 1
                
                // reset
                parentId = child; 
                parentTime = informTime[parentId];
            }
        }
     
        return time.Max(); 
    }
}