Distribute Coins in Binary Tree | Distribute candies in a binary tree | Leetcode 979 | GFG
Vložit
- čas přidán 24. 07. 2024
- Whatsapp Community Link : www.whatsapp.com/channel/0029...
This is the 36th Video of our Playlist "Binary Tree : Popular Interview Problems".
In this video we will try to solve a good Binary Tree problem -
- Distribute candies in a binary tree (GFG)
- Distribute Coins in Binary Tree (Leetcode - 979)
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Distribute Coins in Binary Tree | Distribute candies in a binary tree | Leetcode 979 | GFG | codestorywithMIK
Company Tags : Microsoft
My solutions on Github(C++ & JAVA) : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/distrib...
GfG Link : www.geeksforgeeks.org/problem...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Approach Summary : A recursive approach is used to traverse the binary tree. For each node, the function calculates the total number of extra candies/coins that can be distributed among its left and right subtrees, along with the candies at the current node. The function also updates the moves variable to keep track of the total number of moves required to distribute candies/coins. The distributeCandy function initializes the moves variable and checks if the tree has only one node. If it does, the function returns 0. Otherwise, it calls the solve function to perform the candy/coins distribution and returns the total number of moves required. Overall, the code implements a candy/coins distribution algorithm for a binary tree, aiming to minimize the total number of moves while ensuring each node receives an appropriate number of candies/coins.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
02:22 - Problem Explanation with Example
06:36 - Intuition building with complete dry run
15:10 - Story to code
18:12 - Dry Run of Code
23:36 - Time and Space
24:00 - Coding it up
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #2024 #newyear
For every Candidate who gave up on DSA you adds a new Story in their life.
❤️❤️
For me too. I am into DSA because of this legend.
True
true i'm the one
true. this guys is a legend
🔥🔥 Let’s make this guy famous.
He deserves it
The explanation of this problem is truly outstanding, leaving no room for confusion.
thank you Sir 😀
Story wale Bhaiyyaa🤩
thank you. u are superb!!!!!
😇🙏❤️
ekdum se inhone waqt badal diya, jasbat badal diye, coding ke halat badal diye... GOAT for a reason
Hats off to your unique style of teaching. Every point cleared.
i think i might be one of your earliest students... since 2.5k subscribers...
❤️❤️🙏🙏
Me too bro
Similar Leetcode Problem (POTD Today of 18th May, 2024) - leetcode.com/problems/distribute-coins-in-binary-tree
Sir, in the problem statement posted by Leetcode in today's daily challenge demands to calculate the minimum number of moves. It took me around 30-40 minutes to understand the significance of the word "minimum". I was thinking about multisource BFS, but could not progress further.
thankyou sir came here cause of the potd, but will be staying cause of your amazing narration.
Finally I found a channel that ...explains concepts exactly the way I understand. Its really helpful.Thankyou for the initiative .Keep up the good work.
You are most welcome 🙏🙏
Thanks sir for the best explaination please bring GFG POTD solution regularly just like LC POTD .
thank you mazhar sir...i first attempted this question 7-8 months back and after not approaching and not understanding through different video tutorials I've decided to left this question and now I totally understood this question thank you...
bhai kya bawal samjhate ho , maja aa jata h.
10 mins into your video I got the idea how to write the story .. thanks for making DSA easy as a cake ... couldn't have done without you
Best explanation so far! You never disappoint us!
Glad you think so! 😇🙏❤️
Very nice explanation
Amazing explanation, crystal clear!
thanks for this AMAZING story solution.
Thanks for teaching DSA in this story wise way.
wow bhaiya!!! impressive!!!
Was eagerly waiting for this video thanks a lot bhaiya ❣️
bhai hats off to yaar. kya hi amazing tarika hai aapke explain karne ka. just mind blowing
waiting for 50k bhaiya
loved the approach
Thankyou bhaiya!
you explanation is amazing. you have given me hope.
best solution for this question so far
One day when I'll make it to google, I will not forget to mention you.
This means a lot. I am sure you will reach your goal. ❤️
Thanks Bhai 12:30 yaha tak dekha almost aagaya tha par ye example fail hora tha Input: root = [0,3,0] Output: 3 then "story to code" timestamp wala part dekha got an idea of if child is 0 then we have to send -1. Once again Thanks bhai ❤️❤️
brilliant explanation!
❤❤❤❤❤❤waited
Thanks a lot bhaiya ❤❤
bhaiya ek request h jaise aap phle hrr question ke phle motivation quote dette the 2 min ka vo fir se continue kr do pls
Noted on this ❤️🙏
Nice Explanation!!
thanks sir great explanation ☝
i write things just like you did, but was unsure how to add those up in moves to ans, i messed with code and i don't know why i wrote abs(left)+abs(right), but it got accepted. maybe my knowleged and thought process is increasing by doing potd and watching ur solutions
❤️❤️
Thank You Sir :)
Hats off 🙏🏻
Thank you sir ...
great explaination
Thanku bhaiya ❤
You are unique.
bhai aapko sirf voice se hi pehchante hai apna face bhi reveal krdo kabhi😅😅😂
Great explaination ✨ Sir please upload solutions for biweekly contest if possible..
Great video 👌🏻
Please make a video on todays leetcode contest question 4.
Guruji. Itna acha koi kaise parha sakta hai bhai.
Thank you 🥹
please make more and more videos on graphs
Hi sir, can you please make a video on questions to get started for competitive programming on Codeforces. Or guide for the same.
Very Nice explanation.Just one query ..where do you find so much variety of problems for a single topic, is there any list u following/or any forums?or random pick
i love you bhaiya 😭😭😭😭
Love you all 😇❤️🙏
Keep working hard.
We all will rock
❤
today's gfg problem vertex cover ki bhi video upload krdo bhaiya
👌🏻👌🏻
bhai tu goat hain yaar sab samaj aagaya fr
bhya please solve this question
leetcode 1366 :
Rank Team by Votes..
I'm facing lot of problem in optimization of this problem.
please have a look
Will soon check ❤️
can anybody please explain kinda a proof how this equation { moves += abs(l) + abs(r) } works not able to visualise that coins/candy movement how adding that extra on left and right subtree gives us total moves
🙇♂🙇♂🙇♂
Bhaiya we want regular gfg potd also ❤
Yes @codestorywithMIK
bro ek baat batatyo ki recursion question mein hum question puchte hai ki jaise aap ne question mein pucha ki left and right se kitni extra candies ye kaise pata chalta hai ki hum recursion se kya question puche ki wo hamara sub problem solve karde
Can you plz, make a vdo on this question from leetcode - 1993. Operations on Tree, It's a request
Hi, I am not getting one thing here. In JAVA code (from your github links), I am able to see you have used one moves array, and adding value at it 0th index and returning 0th index. But for C# it seems moves is an integer variable. That makes sense! What I wanted to know is why in JAVA we used an array instead of moves as integer variable?(In that case I am getting error as well). Would be great, if you please explain!
In Java, primitive data types like int are passed by value, meaning when you pass an int to a method, a copy of the value is made and passed to the method. Changes made to the parameter inside the method do not affect the original value outside the method.
To achieve similar behavior to passing by reference in C++, you can use an array or an object. In the provided Java code:
public static int distributeCandy(Node root) {
if (root == null || (root.left == null && root.right == null)) {
return 0;
}
int[] moves = {0};
solve(root, moves);
return moves[0];
}
Here, moves is an array of size 1. Arrays are objects in Java, and when you pass an array to a method, you are passing a reference to the array object. Inside the distributeCandy method, moves[0] is modified by the solve method, effectively mimicking the behavior of passing moves by reference.
private static int solve(Node root, int[] moves) {
if (root == null) {
return 0;
}
int l = solve(root.left, moves);
int r = solve(root.right, moves);
int totalExtraCandies = (l + r + root.data) - 1;
moves[0] += Math.abs(l) + Math.abs(r);
return totalExtraCandies;
}
The solve method takes an array moves as a parameter. Inside the solve method, the value of moves[0] is updated to reflect the total moves made. Since arrays are objects in Java, changes made to the array inside the solve method will be reflected outside the method, similar to passing by reference in C++.
@@codestorywithMIK Thanks a lot for this much brief!🙂
Now it makes sense!
Water the plants on gfg ,ka code jo apne karaye hai similar questions Leetcode 1326 par work nahi kar raha hai...why?
They are not entirety same. One difference you can see that in GFG, the element can also be 0
But in leetcode all number will be > 0
@@codestorywithMIK code me kis point par change karne hoga.
Kay app code me change kare ke GitHub par push kar sakte hai (for Leetcode_1326)?
You are O+
Means a lot 🙏
sir gfg pr aapka java wala solution error dera h please check...
Updated the code now. It works fine now ❤️
how did you arrive at the conclusion that moves should be l+r
Mik sir enable topmate...
Question kya puchna hai recursion mei, yhi issue hain 😢
Hi bhaiya aaj 1 month baad contest diya. Solved 2 question but took 1.5hrs, earlier used to do in 30-40 min. Looks like exams had a big toll on me :( Kya karu , is it normal ??
Don’t worry. It happens.
Keep giving contests no matter what.
sir agar coins bich wale node per hua toh
matlab
0
4 0
0
phir kya hoga?
Output will be 4.
Left most leaf(0) will return -1 to it's parent
Then node(4) k lie totalExtraCandies = (-1 + 0 + 4) - 1 = 2
Now it will calculate moves = abs(l) + abs(r) = 1;
return totalExtraCandies = 2
Not node(0) i.e. root will get l = 2 from its left child as calculated above and similarly it will get r = -1 from it's right child.
moves += abs(l) + abs(r)
moves = 1 + (abs(l) + abs(r))
moves = 1 + (2 + 1) = 4
when to create a new function and when to just use the given one only ?
Actually you can ALWAYS write a separate function of your own to call in recursion.
What I always do is that whenever you have to pass an extra parameter which is not present in the main function (provided by leetcode), then I write my own function.
If I don’t have to pass any extra parameter, then the given function can itself be used to call in recursion.
suggest some more problems so that I can confident in making stories before coding the tree problem
Sure.
Try Maximum Width Of Binary Tree
Binary Tree Maximum Path Sum
Sir Today GFG Problem??????
Unfortunately I couldn’t get time today.
Will definitely try to upload tomorrow 🙏🙏
class Solution {
int ans=0;
public int distributeCandies (Node root){
dfs(root);
return ans;
}
public int dfs(Node root){
if(root==null) return 0;
int l=dfs(root.left);
int r=dfs(root.right);
ans+=Math.abs(l)+Math.abs(r);
return root.data+l+r-1;
}
}
🎉❤
Bhai thora ad kam kri yar..30 min. 8-10 ad .. concentration kharab ho rha h
❤