Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/minimum...
0:00 - Read the problem
2:30 - Drawing Explanation
7:38 - Coding Explanation
leetcode 1443
#neetcode #leetcode #python

[@MP-ny3ep]

Thank you for the daily leetcode problems. For beginners like me , its very helpful. You're a godsend.

[@hardikvora3744]

Thank you so much for coming back to solve daily problems. These are very helpful! :D

[@FatCowFat]

thank you for explaining the daily leetcode problems 👍

[@arpanbanerjee6224]

you make things super easy! following your channel for a long time now....

[@laumatthew71]

Amazing solution and explanation, thank you !

[@picnicbros]

I was able to make it work with 53/54 but stuck for the last test case, and this video literally posted when I decided to seek help. Thank you!

[@NeetCodeIO]

I actually had the same issue as you I'm guessing 😅

[@arpanbanerjee6224]

@@NeetCodeIO Can you please tell me what was the issue. Or can you tell me the mistake in the code which resulted the last test case to fail

[@phaneendhrachinta7295]

Thanks for the Solution, clearly explained. !

[@readonlylogin]

Great explanation! I don't know python. And now I start thinning about learning python because realization is so cool!

[@kapilchoudhary2922]

Beautiful explanation!!

[@alqam2011]

Thank you so much for your effort it DOES HELP ALOT

[@CostaKazistov]

I did a double take when I saw the # of subscribers.
Seemed off by a factor of 100.
Now I get it.

[@xcampus]

welcome back neetcode.

[@kenmatsuru3470]

truely amazing!

[@krateskim4169]

Awesom explanation

[@krishnavamsi9326]

You are a great teacher bro! you changed my coding skills forever! Thank you very very much!😀

[@rsKayiira]

Great solution and explanation. Only thing I wonder if using a visited hashset may have made the solution clearer

[@nihalbhandary162]

wouldnt matter it is a tree, all the nodes that will be visited could only be encountered once. ( you cant arrive at same vertex from 2 different paths in a tree because it would be a cycle).

[@mohamedsalama2743]

this problem is part of the Trees section in your neetcode list where it should be part of Graphs

[@timmyfrank3]

agreed

[@nsandeep7574]

Good explanation

[@NeetCodeIO]

Glad to help!

[@imaadf5124]

Will you be posting all new leetcode videos on this channel?

[@NeetCodeIO]

Yes, all future LC videos

[@noahgsolomon]

Feel like this one should’ve been hard rated

[@shensean1784]

It has to be a noncyclic graph (tree).

[@cj-nr5ni]

Nailed it

[@xcampus]

please answer this question.
if gennady korotkevich is for codeforce, __________________ is for leetcode?
a, neetcode
b,neetcode
c,neetocode

[@MARTIN-101]

0:40 why this is not a binary tree ?

[@ojaswiawasthi3645]

Hi !! Thank u so much for this solution !! But can u please can u solve this code by dry run. Actually I got stuck at dfs(4,1). I guess it should return 2 but I come across the continue statement ? :(

[@aakashgoswami2356]

This guy must be protected at any cost.

[@josnamohan9522]

Can anyone explain why was there a need to check if child == parent?

[@josnamohan9522]

@NeetCodeIO

[@basecase]

@@josnamohan9522 while creating adjajency list we are adding the same edge twice e.g. adj[0] has 1 and adj[1] also has 0 otherwise there will be an infinite loop.

[@josnamohan9522]

@@basecase Thanks for the explanation!

[@NeetCodeIO]

Yeah, Harsh answered it. You might think we don't need to add the edge twice, I did too, but the last test case will fail. Reason is that we need to be able to travel in both directions for this graph, even though it's a tree.
And that test case has a child node, with two parents.

[@baomao139]

It didn't work using the above code. I think line 17, it doesn't need to add 2 to every childTime. It should be t += childTime. If at least one childTime > 0 then t += 2 (only once )

[@dera_ng]

Omg

[@parikshitjuneja]

C++ Solution for the same code
class Solution {
public:
int minTime(int n, vector& edges, vector& hasApple) {

vector adj(n);
for (auto edge : edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
return dfs(0, -1, adj, hasApple);
}
int dfs(int curr, int parent, vector& adj, vector& hasApple) {
int time = 0;
for (auto child : adj[curr]) {
if (child != parent) {
int childTime = dfs(child, curr, adj, hasApple);
if (childTime > 0 || hasApple[child]) {
time += (childTime + 2);
}
}
}
return time;
}
};

[@englishtechnique4813]

why not in java

[@thomas_shelbyyt1349]

Big Fan of your work bro

[@NeetCodeIO]

Thank you 🙏