Binary Tree Cameras | Leetcode | DP on Trees

good coding problem and an even better solution is here ;)
Enjoy watching!
Problem link: leetcode.com/p...
Solution link: leetcode.com/s...
alternate link: ideone.com/5oFPfG
Super useful books for algo ds and programming fundamentals!
1. Introduction to Algorithms by Cormen: amzn.to/35AmQqu
2. The Algorithm Design Manual: amzn.to/2K9RGPq
3. Fundamentals of Data Structures in C++: amzn.to/2LCwIsN
4. Object-Oriented Programming by E Balagurusamy: amzn.to/2Xxmdtr
5. Head First Java: amzn.to/39kb44K
6. Cracking the coding interview: amzn.to/3iDOHLK
7. Database System concepts: amzn.to/3pisuFQ
8. Operating Systems: amzn.to/39fcmis
9. Discrete Mathematics: amzn.to/2MlgCE6
10. Compiler Design: amzn.to/3pkYvx2

[@elijah9610]

Dude, the intro is sooo funny 😂😂😂😂 I had to like it

[@AlgosWithKartik]

😂

[@shashankgupta29]

I would like to thank you so much for bringing up such nice intuitive approaches !!
You are a true gem!
I hope that I could press that like button multiple times !!

[@AlgosWithKartik]

Thanks Shashank :)

[@NamanBansal]

Loved the intro!

[@tawfik1546]

yes , it got me hooked

[@abhinaysingh637]

Kaafi cool ban gye aap pehle ek min me😂

[@hymnish_you]

Thankyou so much bro, I have used up a whole day to understand this. I have watched this video around 8 times coz I can't able to implement it due to the edge cases w/o referring to your code. Your content is no doubt exceptional, Thanks for that.
if(root == null) {
if(willPlace) return 1001;
return 0;
}

[@AlgosWithKartik]

You're welcome and thanks so much for the nice words :)
Keep learning and coding.

[@tathagatnegi5923]

Thanks👍 one day every1 will came to know about the precious content of your channel ..

[@AlgosWithKartik]

So nice of you

[@gauravarora8405]

great explanation. i missed the case where parent can cover a child,, and so missed that state and couldn't figure out what was wrong..Also can you please explain the greedy solution and first explain why it works... That blew my mind

[@sujoyseal195]

"Who can explain it better than Kartik Arora?🤣🤣🤣🤣" . I have not watched the full video yet , but my answer will be : Kartik Arora himself . Btw great job !

[@AlgosWithKartik]

Thanks Sujoy :)

[@evolve.everydayy]

could you explain the last condition dp(u,0,0) for a general tree with more than 2 subtrees(the code)

[@shubheshtiwari8525]

bhiya ji to maze maze me samjha dete hain aur itni aasani se samjh bhi aa jata hai.cha gye bhiya ji.
like and subscribe zaroor kro bhaiyon

[@AlgosWithKartik]

yeh hui na baat, thankss :D

[@tejasnakhate]

Where were you all these time....spent so much time on this problem already

[@tharunchowdary14]

Mastering dp from this channel 🔥

[@AlgosWithKartik]

Glad to know man :)

[@kSERITIKGupta]

Sweet and Simple Explaination really loved it

[@sdeBack1]

15:03, dp( u , 0 , 0 ) than why need of Case 1 and Case2. ( we have to return inf ) As we can see if the current node and parent node have not camera then if we place the camera its child node then the child node can only monitor the current node, not the parent node( no one can monitor) .
Anyone can tell me please ?

[@soumyaporel6955]

Parent node is monitored by the camera in grandparent node i guess

[@kunalpuri6935]

Nice tutorial, Kartik. Just one suggestion. I think the leaf case is not required to be handled. The base case (root == NULL) and the recursion itself handle that scenario. Thanks

[@psurya3053]

thank you sir , i struggled a lot while solving, you made it easier .

[@parthpawar7837]

I think whenever you upload a video, you should mention that somewhere on Codechef Discuss, atleast that's how I found this amazing channel, maybe more people come across your channel this way!

[@AlgosWithKartik]

Thanks Parth for the tip and the appreciation :)
Will try to share the videos on relevant platforms.

[@prajitbanerjee8226]

Intro was legendary

[@sahilkalamkar5332]

Unable to understand why is there a need of keeping the monitoring state?

[@divanshmahajan1769]

why are we considering a case where we allow the parent also and the grand parent of current node also to not have the camera ? we do this for both left and right child and suppose it gives min answer ..wont it be wrong?

[@ujjwalmittal3785]

Time will be order of nlogn ig, only because of the cache ie dp array . We are using map here and not unordered map .
We can't use unordered map .
Also we can't take a 3d dp because the first parameter is a node and not an integer

[@AlgosWithKartik]

Give a number to each node. unordered map node*, int.
Then make 3d array for dp.

[@ujjwalmittal3785]

@@AlgosWithKartik oh yes this idea is great .
Thanks a lot sir .

[@bhuwaneshnainwal8323]

God Of DP :)

[@AlgosWithKartik]

Thanks Bhuwanesh :)

[@3darpan]

Can you explain your base case when root==NULL ?
Why cant we always return 0?

[@AlgosWithKartik]

if node X is not monitored and X expects one of the child nodes to have a camera but turns out X has no child nodes. Let's say now I call solve(X->left).
Then returning a 0 would be incorrect. I should return something that represents it is impossible to cover all the nodes now, given that X is not monitored.
Let me know if this clears your doubt.

[@vishnuvardhan-md1ux]

please explain line sweep and suffix arrays.

[@yourbestie4138]

super

[@skt7088]

great video sir,please make a video on how to make progress in codeforces contests,what to do if we are not able to solve div2c and div2d problems?

[@frogloki882]

This seems like a modified version of knapsack

[@ujjvalsharma5055]

I completely encourage you to make more videos and work harder. You are doing a great job :), but I felt the problem could be explained a bit simpler. However, your videos are definity great and worth it!!

[@AlgosWithKartik]

Thanks for the appreciation and the feedback :)

[@sujoyseal195]

Great

[@GauravSingh-wi5pc]

if someone write bad about the features or anything , you will work on yourself ( no point of removing that comment )

[@GauravSingh-wi5pc]

i love your content btw

[@jaishriharivishnu]

lol... in the starting of video, all of a sudden i lost my dizziness.

[@MayankKumar-nn6us]

link is not opening

[@tle964]

Sir please switch on the camera for the whole video... it feels more connecting...hope you understand:)

[@AlgosWithKartik]

I do understand. I'll try to set it up properly so I can have the cam on for the entire video

[@tle964]

@@AlgosWithKartikyes sir..thank you🙂

[@tomorrowcut]

Another great video.

[@bhamidipatisatwik1165]

Can we extend this solution to a k-ary tree from this binary tree approach?

[@AlgosWithKartik]

yes we definitely can!
Try solving it in O(N) time.

[@bhamidipatisatwik1165]

@@AlgosWithKartik thank you bhaiya

[@divyanshusingh9238]

Great video 🔥

[@AlgosWithKartik]

thankyou sir :D

[@carry4398]

can we memoize using 3D vector ??? how we will store TreeNode's address in vector??

[@AlgosWithKartik]

Yes we can.
Give a number to each node of the tree.

[@carry4398]

@@AlgosWithKartik oh, Got it! thanks :)

[@shaswatadutta4451]

Can it be done using BFS?

[@AlgosWithKartik]

Not sure but I don't think so

[@youroverlord3886]

can anyone explain line 34?

[@SuryaPrakash-pf9dr]

solution link is not working

[@AlgosWithKartik]

I think you need to be logged in to leetcode for accessing that link.
adding ideone link in description instead.

[@SuryaPrakash-pf9dr]

@@AlgosWithKartik logged in but not working btw i understand the solution thanks (y)

[@Nikhil-ov6sm]

happy to see how similar my code is to yours xD...

[@ayushthakur2896]

Uniteresting problem xdddddddddddd