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

[@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

[@mohammadrouzegar3275]

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

[@julianelmasry9556]

Self proclaimed and most voted GOAT

[@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

[@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.

[@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

[@MP-ny3ep]

Terrific explanation ! You made a hard problem look easy

[@shibambiswas]

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

[@SarweshParsewar]

yeah true😢

[@AadiyKhan]

6:26 nobody does it better than my goat

[@johnniewalkerjohnniewalker2459]

Excellent solution!!!

[@sirojiddinSoftwareEngineer]

Good job

[@Everafterbreak_]

this one demotivated me really bad ngl

[@adilansari-hq9ge]

Good to see you bro!

[@kanjurer]

Neetcode, can you solve the Tandoori Chicken problem next?

[@Axel.Blazer]

what is the number or is this the exact title?

[@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

[@syuufukuinjp]

keep it up bro

[@ahmedtremo]

great video as usual :D

[@mechano6505]

My goat coming in clutch

[@saketh8937]

neetcode to the rescue!

[@staywithmeforever]

13:30 copying 0 😅

[@tawfikkoptan5781]

MY GOAT 🔥❤️🔥❤️🔥❤️

[@sauravsingh4497]

Its a good day when my goat posts

[@prasanna.83]

Can anyone explain why he declines the claim he made earlier regarding that theoretical limit being 3?

[@rajsuriyang3427]

The reason we come here is for the math.

[@unknown-mf7dd]

fk this problem

[@IamAWESOME3980]

how the hell can people problem-solve to the answer here. this is such bs

[@jchaodubs]

lebron

[@NoobCoder-n7x]

First!