Maximum Number of K-Divisible Components - Leetcode 2872

Maximum Number of K-Divisible Components - Leetcode 2872 - Python

Рет қаралды 7,932

NeetCodeIO

Күн бұрын

Пікірлер: 39

@NeetCodeIO Ай бұрын

love it when i get to break out the red shirt

@siddardha14 Ай бұрын

Instead of returning total, if we included the component in our sum, we could return 0 from the recursion which would solve the way of counting too

@julianelmasry9556 Ай бұрын

Self proclaimed and most voted GOAT

@mohammadrouzegar3275 Ай бұрын

Lovely solution! I like your approach that avoids using the 'visited' hash set.

@greedyfishbones Ай бұрын

7:15 the +1 caught so off guard i started wheezing

@strobes2638 Ай бұрын

Probably just me having no attention span, but I feel like the contradiction proof explanation wasn't super intuitive even though I solved it before watching, so I wanted to post my thought process even though it's basically the same thing. The way I thought about it was: since the sum of all nodes is divisible by k, whenever we traverse the graph and find a connected set of nodes divisible by k, the sum of the remaining nodes branching off in the graph are also divisible by k. Is there any reason we can't pop it immediately?-> if there are any subtrees branching off not divisible by k that we would "strand". To avoid this, we just work bottom up from the leaf nodes using postorder traversal so we can always pop a component off as soon as the sum is divisible since there's nothing to "strand".

@NeetCodeIO Ай бұрын

Strand is honestly a really good word for this, thanks for commenting. Really liked the way you explained it.

@strobes2638 Ай бұрын

@@NeetCodeIO thanks! I still got a lot from watching your implementation, I wasted a lot of memory on my recursion doing a bunch of stuff like passing a visited node set instead of just keeping track of the parent lmao

@caiorenato1 Ай бұрын

i wanna be good at leetcode, you are helping me alot, God bless your life my friend.

@henokassalif8175 Ай бұрын

My guy just pointed out all the questions I had with the problem examples / description in the first 2 mins of the video

@shibambiswas Ай бұрын

7:15 Bro reminded us about this on the longest night of the year.

@SarweshParsewar Ай бұрын

yeah true😢

@K9Megahertz Ай бұрын

The real challenge to this problem is finding an applicable use case for it.

@baetz2 Ай бұрын

Imagine you have a distributed map-reduce or stream-processing system, and a pool of workers with a tree-like workflow. Some parts of the workflow are calculation-heavy, while others are lighter. Your task is to partition this workflow into equally performant subtrees to put them to different machines. Let's say k is performance unit of a subtree, so if one subtree consumes 2k and other consumes 3k, then you use a cluster of 2 machines for the first subtree and 3 machines for the second.

@K9Megahertz Ай бұрын

@@baetz2 Why would you use a tree? A flat list of workers would be better no?

@baetz2 Ай бұрын

@@K9Megahertz I would use a tree if the workflows were heterogenous and branching. Something where we want to separate concerns, handle errors independently, scale independently. A map-reduce system can be a tree like that with one of the nodes being a pool of mappers and another - a pool of reducers. Disclaimer: I haven't build systems like that irl, it's just my attempt to come up with a use case for this problem.

@MP-ny3ep Ай бұрын

Terrific explanation ! You made a hard problem look easy

@AadiyKhan Ай бұрын

6:26 nobody does it better than my goat

@johnniewalkerjohnniewalker2459 Ай бұрын

Excellent solution!!!

@adilansari-hq9ge Ай бұрын

Good to see you bro!

@sirojiddinSoftwareEngineer Ай бұрын

Good job

@imranaziz7479 Ай бұрын

So basically, every time we run dfs, we are checking to see if we can break off the connection between cur and parent, which will add one more connected component?

@randheerkumargautam6433 Ай бұрын

yes