Maximum Number of K-Divisible Components - Leetcode 2872 - Python
NNeetCodeIO@NeetCodeIO · 352K subscribers
- Views
- 6.3K
- 6,273
- Outlier
- ×0.7
- Median 9.2K
- Length
- 18:51
- Published
- Nov 28, 2025
- Friday
- Comments
- 30
- 229 likes
Script
How it's written
- Words
- 3,586
- Words a minute
- 190
- Reading time
- 16 min
- Segments
- 13
The hook
0:00–0:26Hey everyone, welcome back and let's write some more neat code today. Long day, but you guys know me, I'm the goat. So, I see a hard problem today. I see some people in need of an explanation in particular of why the solution of this problem works. And I really hope by the end of this video, you know why they call me the goat. I'm just kidding. I'm not that self-absorbed. The idea behind this problem is that we're given an undirected tree. And that's what I really want you guys to focus on. This
Structure
Hey everyone, welcome back and let's write some more neat code today. Long day, but you guys know me, I'm the goat. So, I see a hard problem today. I see some people in need of an explanation in particular of why the solution of this problem works. And I really hope by the end of this video, you know why they call me the goat. I'm just kidding. I'm not that self-absorbed. The idea behind this problem is that we're given an undirected tree. And that's what I really want you guys to focus on. This is a graph problem. Yes, but don't forget that this data structure is a tree. That's the first step. It's not a binary tree. They don't say that anywhere in the problem description. So, don't make that assumption. Yes, they drew it like a binary tree to trick you. That's okay. But it's not a binary tree. So, first I just want you to know what's the root of this tree? I mean, you might say it's this, but is that really true? I mean, why can't this guy be the root? I don't see why not. Who says nodes can't have more than two children? Who said this was a binary tree? Don't assume things. Don't make that cognitive error because we could draw this like this. I could put the two at the top and I could say it has three children. It has a four, a zero, and a one. So like this. And then I could say, well, the one has a child as well. It has a child of three. So why can't I draw the tree this way? Who says? And the fact that this is a tree, remember, guarantees no cycles in the graph. So don't forget that either. They don't say that in the
Watch from 0:00problem description. It'd probably make it a little bit easier if they did, but that's why this is a hard problem. So we got the basics out of the way. Let's now actually read the problem. We're given this data structure. It's represented by these variables. I won't go super into it. I mean, very standard. We have um nodes numbered from 0 to n minus one. We have the edges. A node is labeled from 0 to n minus one just so they have a unique uh way to like identify it. We could call that the ID of the node. But each node has a value as well. So it could be one, it could be 8, it could be 144. Who knows? This is the mapping here. So we can use the ID of the node to get the value just by indexing this array. Fantastic. Okay, now we got that out of the way. What is the problem asking of us? Well, again, they don't mention this in the problem description, but they mention it at the bottom. First of all, the sum of all of these values is guaranteed to be divisible by K. The sum right now, it's not like the sum of these, it's the sum of the array here. So, if I say 1 + 8 + 1 + 4 and then another four, and you total all of these up, you get uh 10 + 8 18. and that is divisible by 6. If you divide it by six, you get three. So what this calculation tells me, okay, I guess I'll tell you what the calculation tells me after I tell you what the problem is asking. The problem is saying split this tree or
Watch from 1:31this graph, let me make it slightly bigger such that here and here each of these uh components like this is a connected component. All the nodes are connected and this is a connected component. We achieved that by breaking this edge. And the sum of this I believe is going to be the zeroth value, the second value and the last value which is a sum of six. And you take uh the remaining values which is 4 and 8 and then you get a sum of 12 over here. So 6 and 12. Uh the sum of all these nodes is divisible by k which is six. Same thing over here. What I was going to say earlier is that this calculation down here tells me that at most we could have three connected components. In this problem, the answer is two, but the theoretical limit is three. Now, I think that's actually not necessarily true because I think if the values were allowed to be zero, it could be larger than that because you could literally just have a node with zero and a node with zero over here. And I think actually given the constraints of this problem, that is possible. Also now that I think of it this is not necessarily the theoretical limit but along these lines of thinking we are building intuition about this problem because one thing for sure we know that the whole thing was divisible by K. So if I take uh this part of it and this is divisible by k then the remaining portion is also guaranteed to be divisible by k because think of it this way I have some number
Watch from 3:02let's say 100 and I have some number 10 and let's say this is my k value like 100 is divisible by 10 right the value would be uh 10 but if I take 10 away from 100 it's still divisible by K. If I take any multiples of 10 away from 100, it's still divisible by K. So that's the intuition behind this. Okay. Now what? Now I still have no idea how to solve this problem. I mean it looks like a graph problem, but at the same time it is a tree. So we can kind of use that to our intuition. But at the same time it looks like a tree. So we can use that to our advantage or at least we can try to. But how do we do it? DFS, BFS. What kind of graph algorithm? What are exactly are we trying to do? Well, let me think of an example. Maybe this can help me. So, if I have K, what if I had a tree full of K's? What would that look like? Something like this, maybe. Well, in that case, we know that we could split it every single way. We could break every edge and we'd end up with a bunch of connected components that we could count. How would I go about solving this problem? Like how would an algorithm look like? Let's say I pick any node arbitrarily to be the root. Let's just say this one. I run some kind of DFS algorithm. And even though when we code it up, it's going to be coded up as like a graph algorithm, but really we're running it on a tree. Don't forget that.
Watch from 4:32So I'm thinking now from the topdown perspective, we could say, okay, I have this node here. Is it divisible by K? Well, yes, it is. So, automatically I say break this and break this. I'm not saying that's how I'm going to code it up, but that's how I think about the problem now. And so, I think, well, nobody needed this guy. Nobody. Because to become divisible by K was the goal. A four needs a two to become divisible by K. Or it needs an eight or it needs a 14. It needs 2 + K * N. Any multiple of K. This literally is K. It's K, the value K. So why would we need that? This is unnecessary. Whether we have zero of them or one of them, nobody needs it. Okay. So continuing with this line of thinking, then we might get here and we kind of do the same thing. We start from zero. Our current sum right now is zero. So we kind of start all over. But can we really continue with such a topdown approach? What if the value here was five? So this guy needs a plus one. Or maybe all of us do. Just kidding. So now once again, I'm thinking in terms of an example. I'm forgetting everything else.
Watch from 6:02And I'm just thinking, okay, maybe this guy has a one as a child. And we do the DFS. We collect the sum of the child. We return it back up. we add it. It's six divisible by K. Great. Increment the result by one. And if it was not, if the child here was not, if it was two, we return that. And this is then not divisible by K. So that's a very simple scenario. But what if this node had multiple children? That's a more interesting scenario. Let's think about that. Let's take a look at this example. And now I'm actually just going to tell you what the solution is. and then I'm going to try to like prove it to you. I mentioned we're going to try to like do things top down, but actually we're going to do it bottom up. It's easier to implement that way. The idea is this. We're going to start here. Uh just thinking about this like very simple example. We have five. That's our current sum. We don't really check if that's divisible by K just yet. We want to get to the base case. And then we go to like the child here and that's the base case. Is this node itself in isolation divisible by K? It's not. So we can't increment the number of connected components. Um we try the other side. Is this an isolation? No, it's not. So it needs to be connected to something like it's guaranteed because we know that the solution to this problem it guarantees either the whole thing is a connected component or this like a portion of it is a connected component and then the rest of it is also a connected component. So based on
Watch from 7:25that we can say this from the perspective here when we have five and we return the sums up to this guy we get 5 + 7 and we find that yes that's divisible by k and we only need to check that that's how we uh solve this problem optimally and you probably don't believe me because you're thinking to yourself this well we only needed to check if this was a connected component or this was a connected component or this was a connected component we only needed to check every subree. But how can that be? Well, it's very simple actually, but you probably don't think about it unless you're very very mathematical. It's called a proof by contradiction. Let me show it to you nice and slow. Suppose something else. Suppose this. What if I just get rid of everything? We look at this very, very simplified example and I say I put a one over here and I put a two over here. You're probably thinking, isn't it possible that sometimes something like this could be a connected component and then this in isolation could also be a connected component? Well, if this was the entire tree, the code that I just mentioned to you, the algorithm that I just mentioned to you will not work. But this could never possibly be the entire tree. Can you tell me why? Because the whole sum it looks like is about eight and that's not divisible by K. we were guaranteed it would be divisible by K. Okay, but
Watch from 8:56you're probably thinking even in that case, well, okay, well, what if uh we still had that subree? It looks like that subree. Let me uh fill the values in again. So, we have a one over here and a two over here. The algorithm I mentioned is still going to miss this connected component, isn't it? Well, no, it's actually not because this is not a connected component. Because if it was, then this thing here that we already determined was not a valid connected component. It's a two by itself. It needed somebody to be included with. It needed a four, a delta of four. So, there was no connected component to be found here in the first place because we played ourselves. We forgot the fact that over here that if this doesn't sum, if it's not divisible by K, there's some difference with K. I mean, this is a sum of eight. So, it needs a four or a minus two, I guess, but probably a plus4. Then, it's guaranteed that the rest of this side here, it has a plus4. So at the very least again we can guarantee that this thing needs to be either included maybe with this node or some connected component with that part. And I know at least for me this is kind of a very insane concept. I just enjoy thinking about these kind of ideas contradictions proofs and stuff. That doesn't mean it's easy. Even if I've convinced you that this solution will work it's not so easy to come up with.
Watch from 10:26So now finally, let's summarize what we've talked about and kind of go through an example. Okay, so this is the example I'm going to go over, but actually I'm going to jump into the code right now because I just want to make sure that we're on the same page. The code is actually very very easy and I think then when we come back to this example, I can really show you why it actually works. Okay, so let's uh jump into this. I can get rid of all that. So first things first, just some overhead. We're given a bunch of parameters. Let's just build an agency list out of it. Not a big deal. I usually use default dicts in Python. I won't go over the minor details cuz this is a long enough uh video and problem. But if you don't know these little tricks and stuff, you can probably check out my Python for coding interviews course. Bunch of interactive problems. We're just uh going through the undirected graph in the edges and then mapping uh n1 adding it to the list of neighbors. Uh n2 is added and then same thing uh the other way. I'll create a result variable for how many connected components we have. That's what I'm going to end up returning. And then I'm going to write a DFS which is going to run from the root of the tree. We're going to call this DFS like this. I'm going to pass in zero as the starting point. Why zero? Because any node could be the root. It doesn't matter. So, okay, we have our current node here. And then this is the code. So, we start here. the total sum that we have. We want the value of the zeroth node. We are actually given a array of values. We
Watch from 11:56can use uh the zeroth node to get the value of it. And then that'll be our total so far. And then we're going to go through every neighbor or better yet we could call it the child of the current node. Every child and then recursively we're going to compute the sum of the current subree. So we're going to add to the total the DFS of the current subree. But we don't want to get stuck in an infinite loop, do we? Because I could go back down to my child, but my child could go back up to me cuz we're both neighbors the way the graph is set up. So, we add in a second parameter. We add the parent of the node. And for initially, we can just give it an invalid value like negative 1 because we know that there isn't any node that has an ID of negative 1. And this way we can eliminate the cycle by saying okay here I was your parent the current node was your parent. So if I recursively call this and then I execute this code again I don't want to run dfs again starting from my parent. So I'm going to say if the child that we're looking at is not equal to the parent. That's when we want to execute this part of the code. And then the last couple things here. This is the part that I'll have to convince you of why it works. If the total is divisible by k, it's going to be equal to zero like that. Then we can increment the result. With Python, you have to declare that guy up there a non-local in here to make sure that we use that version of it and not like a local copy
Watch from 13:26of it. And then down here we can return the total. So this is working code. Let me prove it. Okay, unfortunately I kind of screwed up and that probably made the explanation confusing. So pair first of all I should have been parent but also the parent of the child was the current node. I'm sorry I must have misspoke but the current node is the parent of the child. And for some reason over here I have a zero when we should have been using cur. And again I apologize for that. With those minor fixes we can see that this code does work and it is efficient because you can see that running this we are really only visiting each node once. We're not getting stuck in a cycle. We're treating this as a tree. We're doing a bottom up DFS, summing up all of the sub trees. We know there's no cycle in this graph. So why exactly does this work again? Well, let's get into this example. It's a bottom up problem where we only consider sub trees. If you weren't convinced before, let's look at it now. So if I start bottom up here, I got a one, not divisible by three. Our k value is three in this example. Okay, I'm here. Is this divisible by three? No. Okay. And then we're back up uh here. And so now we're looking at this subree which is divisible by three. We got the sum one and we got five here. So that was a six.
Watch from 14:57Six is divisible by three. So we have a connected component here. But let's look at the other example cuz we kind of considered a few examples. We considered okay the whole subree was divisible by K. Okay, that makes sense cuz then everything else is also divisible by K. We considered where each and every single node is divisible by K. If this was K, like if it was three, that's great. If this is three, that's great. And if this is three, that's great because it doesn't matter if we take this in isolation or we take the entire subree. But what about the case, and it does exist where we do have a subree like this one. What would that look like? It might look something like this. Let me use the space down here for a second. What if I had a two, a one, and a six over here? Well, then bottom up, I'm going to say this guy is not divisible by K. I'm going to say this guy is divisible by K. So, plus one, right? This is divisible by K. That's fantastic. Now, from here, I take left and right and I sum them up. It's nine. It's divisible by K. But you're probably thinking, "No, you missed it. This one was also divisible by K. And I'm telling you that the problem didn't say build the connected components. It just said count them. Who cares if we say that this was a connected component and this one was as well because it doesn't necessarily matter how you like actually count them. So long story short, I think that's like a bit of the intuition. I'll
Watch from 16:21quickly go through the rest of this example, but I think that intuition is probably why you were here. But uh now to go through the rest of this, we count this as a connecting component. We go back up. We say I have a six for you. Uh the three and then we go back down here recursively six. And then we do bottom up. Two is not divisible by K. One is not divisible by K. Send these back up. We get a 9 divisible by K. So we found one more connected component here. And this. Now we look at this and we take the left and the right add it all up and it's divisible by K. If we started with K, it's guaranteed it's guaranteed that if you take the left and right sub trees and maybe there's a third sub tree or a fourth subree. If you take all of them and add them all up, it's guaranteed the total is divisible by K. That's the intuition. It's very, very hard. Don't feel bad about yourself. But wasn't that a very elegant algorithm? I thought it was pretty beautiful. Thanks for watching. and I'll see you soon.
Watch from 17:51Full transcript
- 0:00
Hey everyone, welcome back and let's write some more neat code today. Long day, but you guys know me, I'm the goat. So, I see a hard problem today. I see some people in need of an explanation in particular of why the solution of this problem works. And I really hope by the end of this video, you know why they call me the goat. I'm just kidding. I'm not that self-absorbed. The idea behind
- 0:20
this problem is that we're given an undirected tree. And that's what I really want you guys to focus on. This is a graph problem. Yes, but don't forget that this data structure is a tree. That's the first step. It's not a binary tree. They don't say that anywhere in the problem description. So, don't make that assumption. Yes, they
- 0:41
drew it like a binary tree to trick you. That's okay. But it's not a binary tree. So, first I just want you to know what's the root of this tree? I mean, you might say it's this, but is that really true? I mean, why can't this guy be the root? I don't see why not. Who says nodes can't have more than two children? Who said this was a binary tree? Don't assume things. Don't make that cognitive
- 1:03
error because we could draw this like this. I could put the two at the top and I could say it has three children. It has a four, a zero, and a one. So like this. And then I could say, well, the one has a child as well. It has a child of three. So why can't I draw the tree this way? Who says? And the fact that this is a tree, remember, guarantees no
- 1:26
cycles in the graph. So don't forget that either. They don't say that in the problem description. It'd probably make it a little bit easier if they did, but that's why this is a hard problem. So we got the basics out of the way. Let's now actually read the problem. We're given this data structure. It's represented by these variables. I won't go super into
- 1:46
it. I mean, very standard. We have um nodes numbered from 0 to n minus one. We have the edges. A node is labeled from 0 to n minus one just so they have a unique uh way to like identify it. We could call that the ID of the node. But each node has a value as well. So it could be one, it could be 8, it could be 144. Who knows? This is the mapping
- 2:08
here. So we can use the ID of the node to get the value just by indexing this array. Fantastic. Okay, now we got that out of the way. What is the problem asking of us? Well, again, they don't mention this in the problem description, but they mention it at the bottom. First of all, the sum of all of these values
- 2:28
is guaranteed to be divisible by K. The sum right now, it's not like the sum of these, it's the sum of the array here. So, if I say 1 + 8 + 1 + 4 and then another four, and you total all of these up, you get uh 10 + 8 18. and that is divisible by 6. If you divide it by six,
- 2:50
you get three. So what this calculation tells me, okay, I guess I'll tell you what the calculation tells me after I tell you what the problem is asking. The problem is saying split this tree or this graph, let me make it slightly bigger such that here and here each of these uh components like this is a connected component. All the nodes are
- 3:11
connected and this is a connected component. We achieved that by breaking this edge. And the sum of this I believe is going to be the zeroth value, the second value and the last value which is a sum of six. And you take uh the remaining values which is 4 and 8 and then you get a sum of 12 over here. So 6
- 3:32
and 12. Uh the sum of all these nodes is divisible by k which is six. Same thing over here. What I was going to say earlier is that this calculation down here tells me that at most we could have three connected components. In this problem, the answer is two, but the theoretical limit is three. Now, I think that's actually not necessarily true
- 3:54
because I think if the values were allowed to be zero, it could be larger than that because you could literally just have a node with zero and a node with zero over here. And I think actually given the constraints of this problem, that is possible. Also now that I think of it this is not necessarily the theoretical limit but along these lines of thinking we are building intuition about this problem because one thing for sure we know that the whole
- 4:16
thing was divisible by K. So if I take uh this part of it and this is divisible by k then the remaining portion is also guaranteed to be divisible by k because think of it this way I have some number let's say 100 and I have some number 10 and let's say this is my k value like
- 4:38
100 is divisible by 10 right the value would be uh 10 but if I take 10 away from 100 it's still divisible by K. If I take any multiples of 10 away from 100, it's still divisible by K. So that's the intuition behind this. Okay. Now what? Now I still have no idea how to solve
- 5:01
this problem. I mean it looks like a graph problem, but at the same time it is a tree. So we can kind of use that to our intuition. But at the same time it looks like a tree. So we can use that to our advantage or at least we can try to. But how do we do it? DFS, BFS. What kind of graph algorithm? What are exactly are we trying to do? Well, let me think of an example. Maybe this can help me. So,
- 5:23
if I have K, what if I had a tree full of K's? What would that look like? Something like this, maybe. Well, in that case, we know that we could split it every single way. We could break every edge and we'd end up with a bunch of connected components that we could count. How would I go about solving this
- 5:44
problem? Like how would an algorithm look like? Let's say I pick any node arbitrarily to be the root. Let's just say this one. I run some kind of DFS algorithm. And even though when we code it up, it's going to be coded up as like a graph algorithm, but really we're running it on a tree. Don't forget that. So I'm thinking now from the topdown
- 6:06
perspective, we could say, okay, I have this node here. Is it divisible by K? Well, yes, it is. So, automatically I say break this and break this. I'm not saying that's how I'm going to code it up, but that's how I think about the problem now. And so, I think, well, nobody needed this guy. Nobody. Because
- 6:29
to become divisible by K was the goal. A four needs a two to become divisible by K. Or it needs an eight or it needs a 14. It needs 2 + K * N. Any multiple of K. This literally is K. It's K, the value K. So why would we need that? This
- 6:50
is unnecessary. Whether we have zero of them or one of them, nobody needs it. Okay. So continuing with this line of thinking, then we might get here and we kind of do the same thing. We start from zero. Our current sum right now is zero. So we kind of start all over. But can we really continue with such a topdown
- 7:11
approach? What if the value here was five? So this guy needs a plus one. Or maybe all of us do. Just kidding. So now once again, I'm thinking in terms of an example. I'm forgetting everything else. And I'm just thinking, okay, maybe this guy has a one as a child. And we do the
- 7:31
DFS. We collect the sum of the child. We return it back up. we add it. It's six divisible by K. Great. Increment the result by one. And if it was not, if the child here was not, if it was two, we return that. And this is then not divisible by K. So that's a very simple
- 7:51
scenario. But what if this node had multiple children? That's a more interesting scenario. Let's think about that. Let's take a look at this example. And now I'm actually just going to tell you what the solution is. and then I'm going to try to like prove it to you. I mentioned we're going to try to like do things top down, but actually we're
- 8:11
going to do it bottom up. It's easier to implement that way. The idea is this. We're going to start here. Uh just thinking about this like very simple example. We have five. That's our current sum. We don't really check if that's divisible by K just yet. We want to get to the base case. And then we go to like the child here and that's the base case. Is this node itself in isolation divisible by K? It's not. So
- 8:33
we can't increment the number of connected components. Um we try the other side. Is this an isolation? No, it's not. So it needs to be connected to something like it's guaranteed because we know that the solution to this problem it guarantees either the whole thing is a connected component or this like a portion of it is a connected component and then the rest of it is
- 8:54
also a connected component. So based on that we can say this from the perspective here when we have five and we return the sums up to this guy we get 5 + 7 and we find that yes that's divisible by k and we only need to check that that's how we uh solve this problem optimally and you probably don't believe
- 9:14
me because you're thinking to yourself this well we only needed to check if this was a connected component or this was a connected component or this was a connected component we only needed to check every subree. But how can that be? Well, it's very simple actually, but you probably don't think about it unless you're very very mathematical. It's
- 9:36
called a proof by contradiction. Let me show it to you nice and slow. Suppose something else. Suppose this. What if I just get rid of everything? We look at this very, very simplified example and I say I put a one over here and I put a two over here. You're probably thinking, isn't it possible that sometimes
- 9:59
something like this could be a connected component and then this in isolation could also be a connected component? Well, if this was the entire tree, the code that I just mentioned to you, the algorithm that I just mentioned to you will not work. But this could never possibly be the entire tree. Can you tell me why? Because the whole sum it
- 10:20
looks like is about eight and that's not divisible by K. we were guaranteed it would be divisible by K. Okay, but you're probably thinking even in that case, well, okay, well, what if uh we still had that subree? It looks like that subree. Let me uh fill the values in again. So, we have a one over here and a two over here. The algorithm I
- 10:41
mentioned is still going to miss this connected component, isn't it? Well, no, it's actually not because this is not a connected component. Because if it was, then this thing here that we already determined was not a valid connected component. It's a two by itself. It
- 11:01
needed somebody to be included with. It needed a four, a delta of four. So, there was no connected component to be found here in the first place because we played ourselves. We forgot the fact that over here that if this doesn't sum, if it's not divisible by K, there's some difference with K. I mean, this is a sum of eight. So, it needs a four or a minus
- 11:23
two, I guess, but probably a plus4. Then, it's guaranteed that the rest of this side here, it has a plus4. So at the very least again we can guarantee that this thing needs to be either included maybe with this node or some connected component with that part. And I know at least for me this is kind of a
- 11:44
very insane concept. I just enjoy thinking about these kind of ideas contradictions proofs and stuff. That doesn't mean it's easy. Even if I've convinced you that this solution will work it's not so easy to come up with. So now finally, let's summarize what we've talked about and kind of go through an example. Okay, so this is the example I'm going to go over, but actually I'm going to jump into the code
- 12:05
right now because I just want to make sure that we're on the same page. The code is actually very very easy and I think then when we come back to this example, I can really show you why it actually works. Okay, so let's uh jump into this. I can get rid of all that. So first things first, just some overhead. We're given a bunch of parameters. Let's just build an agency list out of it. Not a big deal. I usually use default dicts
- 12:27
in Python. I won't go over the minor details cuz this is a long enough uh video and problem. But if you don't know these little tricks and stuff, you can probably check out my Python for coding interviews course. Bunch of interactive problems. We're just uh going through the undirected graph in the edges and then mapping uh n1 adding it to the list
- 12:47
of neighbors. Uh n2 is added and then same thing uh the other way. I'll create a result variable for how many connected components we have. That's what I'm going to end up returning. And then I'm going to write a DFS which is going to run from the root of the tree. We're going to call this DFS like this. I'm going to pass in zero as the starting
- 13:10
point. Why zero? Because any node could be the root. It doesn't matter. So, okay, we have our current node here. And then this is the code. So, we start here. the total sum that we have. We want the value of the zeroth node. We are actually given a array of values. We can use uh the zeroth node to get the value of it. And then that'll be our
- 13:31
total so far. And then we're going to go through every neighbor or better yet we could call it the child of the current node. Every child and then recursively we're going to compute the sum of the current subree. So we're going to add to the total the DFS of the current subree. But we don't want to get stuck in an infinite loop, do we? Because I could go
- 13:54
back down to my child, but my child could go back up to me cuz we're both neighbors the way the graph is set up. So, we add in a second parameter. We add the parent of the node. And for initially, we can just give it an invalid value like negative 1 because we know that there isn't any node that has an ID of negative 1. And this way we can
- 14:15
eliminate the cycle by saying okay here I was your parent the current node was your parent. So if I recursively call this and then I execute this code again I don't want to run dfs again starting from my parent. So I'm going to say if the child that we're looking at is not equal to the parent. That's when we want
- 14:36
to execute this part of the code. And then the last couple things here. This is the part that I'll have to convince you of why it works. If the total is divisible by k, it's going to be equal to zero like that. Then we can increment the result. With Python, you have to declare that guy up there a non-local in here to make sure that we use that version of it and not like a local copy
- 14:57
of it. And then down here we can return the total. So this is working code. Let me prove it. Okay, unfortunately I kind of screwed up and that probably made the explanation confusing. So pair first of all I should have been parent but also the parent of the child was the current node. I'm sorry I must have misspoke but
- 15:17
the current node is the parent of the child. And for some reason over here I have a zero when we should have been using cur. And again I apologize for that. With those minor fixes we can see that this code does work and it is efficient because you can see that running this we are really only visiting each node once. We're not getting stuck
- 15:38
in a cycle. We're treating this as a tree. We're doing a bottom up DFS, summing up all of the sub trees. We know there's no cycle in this graph. So why exactly does this work again? Well, let's get into this example. It's a bottom up problem where we only consider sub trees. If you weren't convinced before, let's look at it now. So if I
- 15:59
start bottom up here, I got a one, not divisible by three. Our k value is three in this example. Okay, I'm here. Is this divisible by three? No. Okay. And then we're back up uh here. And so now we're looking at this subree which is divisible by three. We got the sum one and we got five here. So that was a six.
- 16:21
Six is divisible by three. So we have a connected component here. But let's look at the other example cuz we kind of considered a few examples. We considered okay the whole subree was divisible by K. Okay, that makes sense cuz then everything else is also divisible by K. We considered where each and every single node is divisible by K. If this was K, like if it was three, that's
- 16:41
great. If this is three, that's great. And if this is three, that's great because it doesn't matter if we take this in isolation or we take the entire subree. But what about the case, and it does exist where we do have a subree like this one. What would that look like? It might look something like this. Let me use the space down here for a second. What if I had a two, a one, and
- 17:03
a six over here? Well, then bottom up, I'm going to say this guy is not divisible by K. I'm going to say this guy is divisible by K. So, plus one, right? This is divisible by K. That's fantastic. Now, from here, I take left and right and I sum them up. It's nine.
- 17:25
It's divisible by K. But you're probably thinking, "No, you missed it. This one was also divisible by K. And I'm telling you that the problem didn't say build the connected components. It just said count them. Who cares if we say that this was a connected component and this one was as well because it doesn't necessarily matter how you like actually
- 17:46
count them. So long story short, I think that's like a bit of the intuition. I'll quickly go through the rest of this example, but I think that intuition is probably why you were here. But uh now to go through the rest of this, we count this as a connecting component. We go back up. We say I have a six for you. Uh the three and then we go back down here recursively six. And then we do bottom
- 18:09
up. Two is not divisible by K. One is not divisible by K. Send these back up. We get a 9 divisible by K. So we found one more connected component here. And this. Now we look at this and we take the left and the right add it all up and it's divisible by K. If we started with K, it's guaranteed it's guaranteed that
- 18:32
if you take the left and right sub trees and maybe there's a third sub tree or a fourth subree. If you take all of them and add them all up, it's guaranteed the total is divisible by K. That's the intuition. It's very, very hard. Don't feel bad about yourself. But wasn't that a very elegant algorithm? I thought it was pretty beautiful. Thanks for watching. and I'll see you soon.
Description
🚀 https://neetcode.io/ - A better way to prepare for Coding Interviews
🧑💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 - HashMap - Python
Problem Link: https://leetcode.com/problems/maximum...
0:00 - Read the problem
0:30 - Drawing Explanation
12:16 - Coding Explanation
15:49 - Drawing Explanation
leetcode 2872
#neetcode #leetcode #python
