Time Needed to Inform All Employees - Leetcode 1376 - Python

[@manerivasanthkumar606]

bro update your website please

[@anujapuranik2000]

This explanation is so simple and mad easy. Thankyou for all your work and efforts!

[@uptwist2260]

Thanks for the daily
ig kinda like max depth but weighted edges.

[@julianelmasry9556]

why is adding the maxTime at each level incorrect? it makes sense to me but I fail at test case 8

[@deadlyecho]

If you are adding the max time at each level that means that you have assigned that level's manager some extra delay time to relay the info down to the employees which is not the case.. for the example shown below, if we follow your approach the result would be 5 but the correct result is 4 beacuse beacuse the process is done in parallel so taking the max and adding it, will add a delay to the result.
0 ( adds 1)
/ \
1 (adds 1) 1 (adds 2)
/ \ / \
2 2 (adds 2) 3 3 (adds 1)
/ \ /\
5 5 4 4

[@JefferyChiang-l3x]

I stuck in the same case and finally I figure out why. The inform passing path should be sequential. In case 8. 6->2 will take 975 and 8->5->0 will take 261+170. If you adding maxtime at each level you would have 6->2 adding 5->0 but its not a valid path.

[@krateskim4169]

Thank you

[@netanelkomm5636]

Damn, i spent like an hour trying to figure out what went wrong in my code. Eventually I realised that I used, i one place, informTime[i] (i.e the current employee) rather than informTime[headID]. I used dfs btw.

[@MP-ny3ep]

Beautifully explained. Thank you!

[@manalitiwari3410]

Hi, Are you not uploading this new content on your Neetcode All list on the website?

[@daniel860305]

Hi @NeetCodeIO, what do you think about starting DFS from the leaf node and traversing back to the root? That we wouldn't need to create another graph and it is possible to reach O(1) space complexity with path compression.

[@Josh-lz9pd]

I thought about this too, I just think DFS would depend more on how lucky you get (because you need to get the leaf with the most expensive time costs)

[@zweitekonto9654]

You would still require extra space to keep track of which leaf nodes and path you have traversed?

[@daniel860305]

@@zweitekonto9654 Actually not because by path compression I detach the visited nodes from the original tree (basically modify the manager array) so that I could retrieve the informTime of a visited node in O(1) time

[@YT.Nikolay]

Thanks for the video! But I think it should be: q = deque([(headID, informTime[headID])]), in case if it takes some time to inform head of managers

[@deadlyecho]

It is not mentioned in the problem statement that this could be the case, so it doesn't actually matter... both are correct

[@NeetCodeIO]

I believe informTime[headID] is the time it takes to inform employees of head, not head itself.

[@dossymzhankudaibergenov8193]

another version of problem "max sum from root to leaf"

[@michael._.]

Dear Neetcode, could you do a video on **956. Tallest Billboard** when you are free? Always appreciating your videos, thank you ≧◉◡◉≦

[@sumitsharma6738]

I Come up with some different approach but similar xD
Build a Tree and finding the max time using postOrder Traversal
class Solution {
public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
List adj = new ArrayList();
for(int i=0;i

[@metarus208]

Hey Neetcode, I became a paid member of your website but there doesn't seem to be much content. Hope you're alright. Waiting for more uploads from you soon.

[@liftandshiftdev3222]

1249ms runtime beats 80%. Wow. My java dfs only took 100 ms and cant beat 50%

[@champion5946]

great

[@satwiktatikonda764]

why arent uplaoding daily LC🥲 ?we go through ur videos when ever we have any dbt ,cause ur explanation is the best