Sum of Distances in Tree | Google | Leetcode 834 | codestorywithMIK
Vložit
- čas přidán 22. 12. 2022
- This is the 7th Video on our Graph Playlist.
In this video we will try to solve a very good and popular problem on Graph "Sum of Distances in Tree".
This is one of the best Qns on Graph which includes DP also.
Problem Name : Sum of Distances in Tree
Company Tags : Google
My solutions on Github : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/sum-of-...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview #interviewtips
#interviewpreparation #interview_ds_algo #hinglish
20 minutes into the video and was able to solve the problem on my own such is the level of teaching.op explaination sir you earned a sub 💕💕
First of all, HEARTFUL WELCOME to my channel Divyanshu ❤️❤️❤️
Thank you for your precious comments
@@codestorywithMIK Your graph series is awesome 🔥🔥
Thank you so so much ❤️❤️❤️
Feel free to spread the word ❤️❤️❤️
Already done😁
Damnnnn. I am astonished how are you able to come up with such a simplified version of explanation and code walkthrough. This is insane.
These videos will be the proof in future, that CZcams can never have a teacher like this dude.
Thank you so much ❤️❤️❤️
Daily watching your leetcode daily challenge series. Building intuition I find more and more interesting from your thought process. Keep it up brother.
bro made this video with a running nose probably, hats off man
Hats off to
The clearity you have to break a hard level question into a medium/easy one is commendable...The best explanation of the problem I have come through..Thanks for making this videos
You made my day.
Thanks a lot Sanjeeb ❤️❤️❤️
I spent the whole day trying to understand this question from discussion and CZcams videos, then ended up just copying and pasting the solution to not break the streak, and now, half way through your video, I was able to code the solution thanks man❤.
Wowwwww.
Your comment made my day. Thank you so so much 😊
I think nobody could come up with this solution in real interview if has not solved this before.
contest 😁
i got to the answer but i dont know how to code 😂😂🙄🙄🙄🙄
Jukhaam tha bhai ko but still the effort ,,, deserves Appreciation
Thanks a lot bhaiya ❤❤
Here is the code for the brute force approach:
class Solution {
public:
vector sumOfDistancesInTree(int n, vector& edges) {
// prepare the graph from the edges
vectoradj[n];
for(vectoredge:edges){
int u=edge[0];
int v=edge[1];
adj[u].push_back(v);
adj[v].push_back(u);
}
vectorans(n);
for(int i=0;i
thanku bhai helped understand
you are just the best one out there on youtube today.
One of the best explanations on CZcams for this problem😊
Iss video ka bohot intejaar tha😄
❤️❤️❤️
just feeling like wow . amazing explanation
Aadhe video me hi I coded it up and understood the clear intuition. thanks legend
Best explanation!!!!!!!
You are the best tutor on CZcams
Good One
Best explanation till now
❤ Really very well explained!! Very few put so much effort! In every video you're explaining the "WHY?" part and not only "WHAT/HOW?"
Tysm ❤️❤️❤️
Thanks for the explanation 😌
Thank you Souradeep ❤️❤️❤️
Hats off to your dedication bro. Even in running nose, you made it.
But take care of your health also
Best explanation ever broo😍😍
Thank you so much ❤️❤️❤️
Thank you 👍
Your videos are much better than others so called dsa experts
bhot saare ++++++++
Thanks for this soln . Best explanation for this question .
Thank you so much ❤️❤️❤️
great explanation ❤❤
Your way of teaching is very good. You will surpass all other youtubers soon
Maza aa gaya ! Gazab :)
Thank you 😇🙏
Your voice is like seeken youtube channel
sir can u kindly attach ur graph playlist as many recommended ur graph playlist also i f possible kindly tag dp playlist also
Thank you for the vedio :-)
Glad I could help ❤️❤️❤️
Thanks for watching
great explanation!
Thanks a lot Pranav ❤️❤️❤️
I don't know how do we even learn to think like that, the way you came up with the solution. Do people who are really good at DSA just born with this talent? or does it come from practice. I don't think I'll even be able to be as good as you or any other DSA CZcamsr. Some people are too good to be true. I'm really beating myself over it and getting depressed. Do you have anything to suggest or is it just the way it is ?
Hi there,
Actually these are very tough problems and you should never worry about these.
Very rare people like Lee, Vlad Trubachov etc are able to solve these in one go.
I also couldn't come up with this in one go.
If you talk to good coders, they will always suggest you to not waste time on very tough problems.
First cover up the important and those Qns which are asked often in interviews.
Don't worry if you are not able to solve now, you will be able to solve later for sure.
Three Suggestions :
1. BE CONSISTENT
2. If you are not able to solve, neither able to understand from CZcams or any source, skip it.
3. Focus on yourself only. Don't worry if other are able to solve. (Many of them are copying solutions or many of them might have been coding since long). Your actual COMPETITION is YOU only.
Things will fall in place soon.
The key is " CONSISTENCY " . Even in worst case, solve at least on Qn a day, no matter it's easy , medium or hard, it should teach you something new. That's important for growth.
Remember , "We all have same problems and we all are in this together. ok"
💪 Let's do it
Same feeling. But if someone can, we can too . Keep trying
7/43 done [5.2.24] ✅✅
a wonderful explanation thanks even i need not to look at your code
ur 😂explanation is like drug to me.thank you sir
used both dfs and bfs to solve this, this was nice observation based + maths question
class Solution {
public:
int dfs(int node, int par, unordered_map& adj, vector& visited, int len, vector& relativeDistances, vector& childCounts, vector& parents){
visited[node] = true;
relativeDistances[node] = len;
parents[node] = par;
int ans = 1;
for(auto& next: adj[node]){
if(!visited[next]){
ans += dfs(next, node, adj, visited, len+1, relativeDistances, childCounts, parents);
}
}
childCounts[node] = ans - 1;
return ans;
}
vector sumOfDistancesInTree(int n, vector& edges) {
// concept of relative distances, if we know distance of all other nodes from node n
// then we can calculate distances of all other nodes from another node m
// construct the adjancency list
unordered_map adj;
for(auto& edge: edges){
int u = edge[0], v = edge[1];
adj[u].push_back(v);
adj[v].push_back(u);
}
vector visited(n, false);
// we need relativeDistance from atleast one of the nodes, and we need childCounts of
// every node, and we need parents of every node
// since the formula can be derived as
// distanceSumFromChild = relativeDistanceSumFromParent - childNodes(including itself) + parentAndOthers
vector relativeDistances(n, 0), childCounts(n, 0), parents(n, -1);
// main dfs call to generate the structures
dfs(0, -1, adj, visited, 0, relativeDistances, childCounts, parents);
int distanceSumFrom0 = 0;
for(auto& e: relativeDistances) distanceSumFrom0 += e;
vector ans(n, distanceSumFrom0);
// do a bfs, since child's count is directly dependent on parent's count
vector visited2(n, false);
queue q;
q.push(0);
while(!q.empty()){
int f = q.front(); q.pop();
int par = parents[f];
visited2[f] = true;
if(par != -1){
int relativeDistSumFromParent = ans[par];
int childNodes = childCounts[f] + 1;
int parentAndOthers = n - childNodes;
ans[f] = relativeDistSumFromParent + parentAndOthers - childNodes;
}
// visit others
for(auto& next: adj[f]){
if(!visited2[next]){
q.push(next);
}
}
}
return ans;
}
};
Best Explanation !! Bro please upload string algos..
Thanks a lot.
Would you like to mention some of the string algos you would want to see the video of ?
I am trying to take feedback from everyone on what topics they want to
I was solving this question using normal dfs but stuck as har node ke liye distance and traversal kaise kru, then saw the solution. No doubt explanation is great, but still wonder how such solutions can be build in real interview scenarios. Can you suggest some tips for that?
take care of your health
Sir.. ❤ your teaching n ab toh har din leetcode ke liye ap par depend hui hu.. I want to know ke khud se aise solve kaise karpaungi😢..
Always try first on your own. Give it 1 hour max. Nahi bana then ajao samajhne
Intuition left the chat 🙃
Hi Harshit,
Would love to know if you think I should have added more on intuition part ?
Your feedback is important to me. Kindly let me know ❤️😊
Thank you
great explanation. Could you please share the code in java as well
Find my java solution below :
class Solution {
int[] res, count;
ArrayList adj;
public int[] sumOfDistancesInTree(int N, int[][] edges) {
adj = new ArrayList();
res = new int[N];
count = new int[N];
for (int i = 0; i < N ; ++i)
adj.add(new HashSet());
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
firstDFS(0, -1);
secondDFS(0, -1);
return res;
}
public void firstDFS(int root, int pre) {
for (int i : adj.get(root)) {
if (i == pre) continue;
firstDFS(i, root);
count[root] += count[i];
res[root] += res[i] + count[i];
}
count[root]++;
}
public void secondDFS(int root, int pre) {
for (int i : adj.get(root)) {
if (i == pre) continue;
res[i] = res[root] - count[i] + count.length - count[i];
secondDFS(i, root);
}
}
}
Thanks a lot Abhijit. Currently i have not worked much in Java. But i will soon share java also
Agar Woh I Pad ke notes bhi mil jate to aur bhi maja ajata
plz also explain java code
Why am I getting TLE?
class Solution {
public:
long root_result;
vectorcount;
int N;
int dfsRoot(unordered_mapadj, int curr_node,int prev_node,int curr_depth){
int total_node = 1;
root_result+=curr_depth;
for(int child:adj[curr_node]){
if(child==prev_node)
continue;
total_node+=dfsRoot(adj,child,curr_node,curr_depth+1);
}
count[curr_node]=total_node;
return total_node;
}
void DFS(unordered_mapadj, int curr_node,int parent,vector &result){
for(int child:adj[curr_node]){
if(child==parent)
continue;
result[child]=result[curr_node]-count[child]+(N-count[child]);
DFS(adj,child,curr_node,result);
}
}
vector sumOfDistancesInTree(int n, vector& edges) {
unordered_mapadj;
N=n;
count.resize(n,0);
//make the graph
for(vector vec:edges){
int u=vec[0];
int v=vec[1];
adj[u].push_back(v);
adj[v].push_back(u);
}
root_result = 0;
dfsRoot(adj,0,-1,0);
// cout
You should always try pass parameters to functions (wherever possible) by "reference"
So, just do the following changes :
int dfsRoot(unordered_map &adj, int curr_node,int prev_node,int curr_depth) {..}
void DFS(unordered_map &adj, int curr_node,int parent,vector &result) {...}
@@codestorywithMIK Thank you sir it worked,it is because if we pass them without reference on each stack a new variable is created.Thank you sir
Indeed you are right.
Thank you ❤️
Class solution {
Public int[] sum of distance in Tree(int n , int[][] edges){
final Array list [] graph =new Array list (n);
final int[] count = new int (n);
Array fill(count,1);
final int []ans=new int(n);
for(int i=0;i
The part of calculating answer for node-2 at 8:14, is not so clear.
I mean, explaining how an answer is deduced is very different from
how the idea came to a person's mind.
At 8:14, instead of directly starting to explain the node-2 ka answer, I think how that idea came to your mind, is missing.
I think that was missing in the video.
Just my observation
Feedback taken Srinish.
Thanks a lot, will keep this in mind
dfsbase have 4 arguments and you are passing 3
today is my bad day I just cannot understand this question spent hours, now I have to copy paste, no other choice.
same here brother, even after his explanation I aslo can't
@@sjxsubham... good to see I am not only one.
Don’t worry, i has happened to me multiple times. Once i get more practice then I come back and then I am able to understand
BRUTE FORCE IN JAVA :- by MIK approach
class Solution {
public int[] sumOfDistancesInTree(int n, int[][] edges) {
/*
BRUTE FORCE : -
apply bfs or dfs from all nodes and calculate distances
*/
// edges s graph bnao
// BRUTE FORCE
Map map = new HashMap();
for(var edge:edges)
{
int u = edge[0];
int v = edge[1];
map.computeIfAbsent(u,k->new ArrayList()).add(v);
map.computeIfAbsent(v,k->new ArrayList()).add(u);
}
boolean visited[] = new boolean[n];
int res[] = new int[n];
for(int i = 0;i
OPTIMAL SOLUTION IN JAVA : since in repo java sol doesnot exist
//***************************************************APPROACH 2*************************************************************************************** */
/*
hum given node s dfs lga kar uska ans calculate kr lenge
ab child jidhar hai wo or uske subtree me height 1 s kamm hogi qki ab child as a parent kaam krega to pehle parent ka ans tha
usme ab #nodes in child subtree ko ghtaado
baaki bche hue nodes ki height m 1 se increment hoga qki ab ye child s parent and parent s wo sb edges to unki disatnces bdhi
to ans = ans of given node - no of nodes in child subtree including child(x) + (n-x)
bs isi logic ko ab umplement krna h
*/
class Solution {
int root_result = 0;
ArrayList count;
public int[] sumOfDistancesInTree(int n, int[][] edges) {
// pehle to hme root ka ans store krlena h taaki isi m + ya - krke hum baaki k answers ko calulate krege
// count of child b store krna h sbhi ka to wo bhi saath k saath hi store krte and root ka result b chahiye toh inko global bna lia taaki update krte rhe saath k saath hi
count = new ArrayList(n); // initialize krdo 0 se count array ko
for(int i = 0;inew ArrayList()).add(v);
map.computeIfAbsent(v,k->new ArrayList()).add(u);
}
dfsRoot(map,0,-1,0); // 0 is current node , -1 is taaki hum apne parent k paas fir naa chle jaayen and 0 ki current level jo ki +1 hota jaega count nikalne k laam aayeaga
// yaha takkk hmare paas root ka result and sbhi nodes k child ka count aagya h
// for(var c : count)
// System.out.print(c+" ");
// System.out.println();
// to bss ek or dfs lgaane pdega jisse hum apna result array fill krte jaaege with help of root
int[] result = new int[n];
result[0] = root_result ; // shuru m root node ka result rkh dia
dfs(map,0,-1,result,n); // 0 current node and prev = -1
return result ;
}
public void dfs(Map map,int parent,int prev_node,int[] result,int n)
{
// sbhi child k paas jaao
if(map.containsKey(parent))
{
for(var child : map.get(parent))
{
if(child == prev_node)
continue;
result[child] = result[parent] - count.get(child) + (n - count.get(child)) ;
dfs(map,child,parent,result,n); // populate further results
}
}
}
public int dfsRoot(Map map , int curr_node , int prev_node , int depth)
{
int totalNode = 1 ; // current wale ko toh count krna hi h
root_result += depth ; // hm kisi level p aaye mtb ye node root se depth level p hai to root ka ans bhi update hota jaega
// ab iske child k paaas bhi jaao or dekhlo kitne nodes hain
if(map.containsKey(curr_node))
{
for(var child : map.get(curr_node))
{
if(child == prev_node) // mtlb parent k paas hi jaa rhe h to kuj nai krna h continue krdo
continue;
// agr aisa nai h toh totalNode ko update krna hoga
totalNode += dfsRoot(map,child,curr_node,depth+1); // child current node bna or current wala prev bna gya
}
}
count.set(curr_node,totalNode); // curr_node k children ka count including itself store krdia
return totalNode ;
}
}
this should have been a 15 min video at max even with proper explanation and examples. I request you to reduce the length of your videos
Hi Deepak,
I agree with you. However, I usually try to make it in such a way that a beginner who has not much practice or knowledge can understand it.
This is the reason I cover every single minute details and repeat them for making it easier.
I hope you understand. But I will definitely try to reduce the length going forward. ❤️❤️❤️
class Solution {
public:
int solve(int node, unordered_map&um,vector&vis)
{
vis[node]=1;
queueq;
q.push(node);
int level=0,ans=0;
while(!q.empty())
{
int siz=q.size();
ans+=level*siz;
while(siz--)
{
auto topi=q.front();
q.pop();
for(auto it:um[topi]){
if(!vis[it]){
vis[it]=1;
q.push(it);
}
}
}
level++;
}
return ans;
}
vector sumOfDistancesInTree(int n, vector& edges) {
vectorans;
vectorvis(n,0);
unordered_mapum;
for(auto it:edges)
{
um[it[0]].push_back(it[1]);
um[it[1]].push_back(it[0]);
}
for(int i=0;i
One correction =?(n-count (child)-count (child);
Lol, it's funny how I just stumbled on your leetcode profile from the odd-even list question and noticed that you just solved this question, I was waiting for the explanation, and bam here it is... Thanks a lot for making these, slowly and surely I am gaining momentum. 🥹
It means a lot to me ❤️❤️❤️
Thank you so much