@@codestorywithMIK Can we connect by any means, Bhaiya? Need some advice regarding tech stuffs and hiring, this year has been drastic for us with regards to internship and placement.
NOTE - The diameter of a tree or graph represents the longest path between any two nodes, and this path does NOT contain any REPEATED edges or nodes. Today's POTD Link - ua-cam.com/video/uz_WISpySFs/v-deo.html
4 minutes into the video, just saw the fact about the diameter and solved it, bro you are goated, wonder why no one ever told about that diameter fact, it blowed my mind!! thanks.
Leetcode : 3203 (using video Explaination) sol : class Solution { public: pair bfsTofindFarthestNode(int s, int v, unordered_map& adj) { vector vis(v, false); queue q; q.push(s); vis[s] = true; // Mark starting node as visited int level = 0, farthestNode = s; while (!q.empty()) { int n = q.size(); for (int i = 0; i < n; i++) { int node = q.front(); q.pop(); farthestNode = node; for (auto it : adj[node]) { if (!vis[it]) { vis[it] = true; // Mark neighbor as visited before enqueueing q.push(it); } } } if (!q.empty()) level++; } return {farthestNode, level}; } int treeDiameter(vector& edges) { int v = edges.size() + 1; // Number of nodes unordered_map adj; for (const auto& edge : edges) { int u = edge[0], v = edge[1]; adj[u].push_back(v); adj[v].push_back(u); } auto oneEndNode = bfsTofindFarthestNode(0, v, adj); auto otherEndNode = bfsTofindFarthestNode(oneEndNode.first, v, adj); return otherEndNode.second; // Diameter of the tree } int minimumDiameterAfterMerge(vector& edges1, vector& edges2) { int dia1 = treeDiameter(edges1); int dia2 = treeDiameter(edges2); int combinedDia = ceil(dia1 / 2.0) + ceil(dia2 / 2.0) + 1; return max({dia1, dia2, combinedDia}); } };
Done and crystal clear. These concepts I was not even taught in a paid course I took years ago. I wish I had found you earlier. Waiting for today's POTD now.
One small correction here: at 7:06, you say : d(u, A) d(u, B) But you could also argue that if we switch the nodes A and B in the above equation and the condition above remains true. Maybe the right wording of the statement should be: If we consider that B is always the farthest node from u, then the following condition is always True: d(u, A)
What if the node 5 has two child nodes(say 10 and 11) in the dry run? Do we get multiple options for diameters? How does this effect the diameter paths(having multiple paths with diameter k)?
MIK , plz 1 vdeo on Bridge of graph....i knw ki dfs s hoga ..time stamp discovery and finish time ka concept h but still achhe s clear nai hua h...so plz try to bring that too.. Also i am placed in campus in PSU with 21 ctc. Thankyou so much for everything .
Bhaiya mathematical proof wala ek baar firse samjha do, Aur Bhaiya d(u,a) > d(u,b) ho sakta hai aap jo diagram liye uske basis pe aagar mein u ko b se 1 distance pe rakhu, ye wala thik se samajh nhi aaya, mathematical wala ek baar aur Bhaiya please
d(A,B) < d(U,V) + d(U,B) 13:01 yeh toh ho hi sakta hai koi ek path hamesha diameter se chota hoga ya toh do paths hai u se v aur u se B correct me if i am worng
If you notice d(U,V) + d(U,B) contains one duplicate path as well. We need to exclude any path counting more than once. Diameter is the longest path between any two nodes and each path is counted only once.
Definitely it will come. But before solving today's POTD, this video is going to be very important. Do watch this one because we will directly use the code of this video to today's POTD.
Feels so honoured that He is my college alumni, absolute goated stuff Bhaiya🦾
This means a lot ❤️🙏
@@codestorywithMIK Can we connect by any means, Bhaiya? Need some advice regarding tech stuffs and hiring, this year has been drastic for us with regards to internship and placement.
NOTE - The diameter of a tree or graph represents the longest path between any two nodes, and this path does NOT contain any REPEATED edges or nodes.
Today's POTD Link - ua-cam.com/video/uz_WISpySFs/v-deo.html
SIR PLEASE SOLVE 21 DEC AND 22 DEC Problem of the day as you skipped these problems on that day
4 minutes into the video, just saw the fact about the diameter and solved it, bro you are goated, wonder why no one ever told about that diameter fact, it blowed my mind!! thanks.
Glad I could help you discover it! 🙏❤️
Leetcode : 3203 (using video Explaination)
sol :
class Solution {
public:
pair bfsTofindFarthestNode(int s, int v, unordered_map& adj) {
vector vis(v, false);
queue q;
q.push(s);
vis[s] = true; // Mark starting node as visited
int level = 0, farthestNode = s;
while (!q.empty()) {
int n = q.size();
for (int i = 0; i < n; i++) {
int node = q.front();
q.pop();
farthestNode = node;
for (auto it : adj[node]) {
if (!vis[it]) {
vis[it] = true; // Mark neighbor as visited before enqueueing
q.push(it);
}
}
}
if (!q.empty()) level++;
}
return {farthestNode, level};
}
int treeDiameter(vector& edges) {
int v = edges.size() + 1; // Number of nodes
unordered_map adj;
for (const auto& edge : edges) {
int u = edge[0], v = edge[1];
adj[u].push_back(v);
adj[v].push_back(u);
}
auto oneEndNode = bfsTofindFarthestNode(0, v, adj);
auto otherEndNode = bfsTofindFarthestNode(oneEndNode.first, v, adj);
return otherEndNode.second; // Diameter of the tree
}
int minimumDiameterAfterMerge(vector& edges1, vector& edges2) {
int dia1 = treeDiameter(edges1);
int dia2 = treeDiameter(edges2);
int combinedDia = ceil(dia1 / 2.0) + ceil(dia2 / 2.0) + 1;
return max({dia1, dia2, combinedDia});
}
};
Man you are a legend and so hard working. Thank you for clearing the concepts. Now I can understand the POTD
Done and crystal clear. These concepts I was not even taught in a paid course I took years ago. I wish I had found you earlier.
Waiting for today's POTD now.
Amazing explanation, Keep the good work
Your explanation is unbeatable.
First view😍❤
One small correction here:
at 7:06, you say : d(u, A) d(u, B)
But you could also argue that if we switch the nodes A and B in the above equation and the condition above remains true.
Maybe the right wording of the statement should be:
If we consider that B is always the farthest node from u, then the following condition is always True:
d(u, A)
Great concepts
mik sir you are so underrated!!
Bro your whole content is aroud dsa and leetcode, you should take the premium again 😅
Wow. Thanks a lot MIK. Was waiting for this one.
What if the node 5 has two child nodes(say 10 and 11) in the dry run? Do we get multiple options for diameters? How does this effect the diameter paths(having multiple paths with diameter k)?
Hello @codestorywithMIK, at 7:15 in the video, d(u, A) can be greater than d(u, B) right?
Yes yes definitely. It can be. I just took a case . There can be many cases
@@codestorywithMIK Okay, so we needed one case to prove by contradiction. Thanks for the prompt reply
I made silly mistakes during oa rounds due to stress, later I was able to solve 😭😭
20:14
MIK , plz 1 vdeo on Bridge of graph....i knw ki dfs s hoga ..time stamp discovery and finish time ka concept h but still achhe s clear nai hua h...so plz try to bring that too..
Also i am placed in campus in PSU with 21 ctc. Thankyou so much for everything .
14:24 🔔 vo yaha kisa lye karaga 😂😂🤣
SIR PLEASE SOLVE 21 DEC AND 22 DEC Problem of the day as you skipped these problems on that day @codestorywithMIK
Sir, expedia group USA ke liye refer kr skte ho kya? i am doing my masters here
Thanks sir
Bhaiya mathematical proof wala ek baar firse samjha do,
Aur Bhaiya d(u,a) > d(u,b) ho sakta hai aap jo diagram liye uske basis pe aagar mein u ko b se 1 distance pe rakhu, ye wala thik se samajh nhi aaya, mathematical wala ek baar aur Bhaiya please
MIK ek roadmap bana sakte ho ? How to get good tech job in 2025 I sometimes got distract from my path ki what how and where to do
I am not able to search for leetcode POTD section. Where is that section ?
ua-cam.com/video/uz_WISpySFs/v-deo.htmlsi=btJ8DB81bcdJITlu
Its daily challenge problems, You can find in the right side of the problem section.(Looks like calendar)
ye question CSES sheet me bhi hai
2940. Find Building Where Alice and Bob Can Meet
solution video please
coming today.
d(A,B) < d(U,V) + d(U,B) 13:01 yeh toh ho hi sakta hai koi ek path hamesha diameter se chota hoga ya toh do paths hai u se v aur u se B
correct me if i am worng
If you notice d(U,V) + d(U,B) contains one duplicate path as well. We need to exclude any path counting more than once. Diameter is the longest path between any two nodes and each path is counted only once.
Mik bhaiya perso ka video please
Sir Aaj POTD nhi solve karenge?
Definitely it will come. But before solving today's POTD, this video is going to be very important. Do watch this one because we will directly use the code of this video to today's POTD.
@codestorywithMIK yess sir
Last two days
tattoo banva lo 😂😂 3 points ko