bro maine first try me kar liya using bfs for each node in a component and summing up max groups for each component and used dfs for component sepration and stored elements in map according to their component thnx ❣❣❤
Maine bhi similar soncha tha, lekin thode testcases pass nahi ho rahe the, aapka video dekhne k baad maine chote mote tweaks kiye and mera code bhi chal gaya. Thanks bhai
Ah yes yes. My bad for the silly but later in the video, i have covered the fix ❤❤❤ And hence that’s the proof that we will have to try BFS from each node. Only trying BFS from 0 will not give best result. ❤❤ Thanks 😇🙏
thanks for this great video, I stuck on how to know which node to start BFS from in order to find maximum grouping didn't know brute force was the way lol. Grouped nodes together using Disjoint Set, then took maximum from each group
Hi Mik I am using diameter of graph concept but it's giving error. Can we use this concept for finding maximum distance for each group rather than finding distance from each node
Awesome video. But having a doubt, after bipartite validation, to find the total number of groups can't we use the diameter of graph concept for each connected components and summing up them, should result in the answer. I have tried that code, but 51/55 testcases passed. Not sure, why this will not work?
@@gui-codes Not able to put link because of youtube restriction. class Solution { public int magnificentSets(int n, int[][] edges) { Map graph = buildGraph(edges); int[] coloring = new int[n]; boolean[] visited = new boolean[n]; // not possible scenario for(int i = 0; i < n; i++) { if (!visited[i] && !isBiPartite(graph, i, coloring, visited)) { return -1; } } visited = new boolean[n]; int totalGroup = 0; for(int i = 0; i < n; i++) { if (!visited[i]) { totalGroup += findDiameterOfGraph(graph, i, n, visited); } } return totalGroup; } private Map buildGraph(int[][] edges) { Map map = new HashMap(); for(int[] edge: edges) { int u = edge[0] - 1; int v = edge[1] - 1; map.putIfAbsent(u, new ArrayList()); map.get(u).add(v); map.putIfAbsent(v, new ArrayList()); map.get(v).add(u); } return map; } private boolean isBiPartite(Map graph, int start, int[] coloring, boolean[] visited) { Queue q = new LinkedList(); q.add(start); visited[start] = true; coloring[start] = 0; while(!q.isEmpty()) { int node = q.poll(); for(int neigh: graph.getOrDefault(node, new ArrayList())) { if (!visited[neigh]) { coloring[neigh] = 1 - coloring[node]; // 0 or 1 visited[neigh] = true; q.add(neigh); } else if (coloring[neigh] != 1 - coloring[node]) { return false; } } } return true; } private int findDiameterOfGraph(Map graph, int start, int n, boolean[] visited) { int[] pair = traverseTillLast(graph, start, visited); int oneEndNode = pair[0]; pair = traverseTillLast(graph, oneEndNode, new boolean[n]);
return pair[1]; // final distance from oneEndNode to last node } private int[] traverseTillLast(Map graph, int start, boolean[] visited) { Queue q = new LinkedList(); q.add(start); int level = 0; visited[start] = true; int lastNode = start; while(!q.isEmpty()) { int n = q.size();
while(n-- > 0) { int node = q.poll(); lastNode = node; for(int neigh: graph.getOrDefault(node, new ArrayList())) { if (visited[neigh]) continue; visited[neigh] = true; q.add(neigh); } } level++; } return new int[]{lastNode, level}; } }
Same😢😢, I don't know why the diameter code is not working. When we find diameter from another graph, we always get farthest node in first bfs and get diameter in second bfs, But in this 52nd test case, we are not able to find the farthest node which is 11 and 17. That is why the diameter is also coming out wrong. I tried the whole day but I am not able to understand why this is happening😢😢
Hi MIK just one doubt. For finding maximum level in group can't we find the end node of each group(and find the level using bfs) rather than doing bfs/dfs for all node and then sum of all distance for each group.
It's important to find bfs of every node bcoz if you observe the answer is highest when you start from the node having the least no of children or connection
example 1 me 5 group-3 me hi gaya tha with 2 and 4. but it will reduce the number of groups to 3. we can increase the group number, if we were able to put 5 in a separate group without breaking any rule, we did that and hence groups count increased to 4
Unfortunately college professors skip such important topics. I remember i was taught Bipartite topic in Graph Theory subject. But no worries, I hope my Bipartite video will help you 🙏❤️ see the link in the video description
I actually got a wrong answer as I mentioned in the video. Then I realised that doing BFS from only one node will not guarantee best solution. So we have to try with every node. I felt bad to have missed this case when I was solving it but it was a good learning experience ❤️
I think is tarah k to definitely aa sakte hain. Video description me dekho, jo jo concepts use hue hain all are simple, but un sab ko combine karke ek Qn bana diya gaya hai islie hard lagta hai. Google usually yahi check karta hai ki aapko foundation kitne strong hai. For example is problem me dekho, bipartite check, bfs and dfs hi likha hai bas zyada se zyada bas starting intuition lagane ki deri hai.
@ just focus on intuition and approach ,,, har ek person ka usko code mai convert krne ka tarika alag hota hai,, jab bhi intuition and logic clear haii tab coding part dekho ignore kro aur khud se hi code likhna start kro ,,,then compare ur code with mik's code mai har bar aaisa hi krta hu
Ohhho, aaj fir ek Hard problem Halwa banega . Legend MIK.
Thanks a lot for putting details ❣❣❣
bro maine first try me kar liya using bfs for each node in a component and summing up max groups for each component and used dfs for component sepration and stored elements in map according to their component thnx ❣❣❤
Legend Mik's video >>>>>>>>>> Netflix, Prime
Means a lot ❤❤❤
Maine bhi similar soncha tha, lekin thode testcases pass nahi ho rahe the, aapka video dekhne k baad maine chote mote tweaks kiye and mera code bhi chal gaya. Thanks bhai
Same here
Levels sabke nikelenge! THe OG is here.!!
all cleared...smooth explanation mik👏
at 32:35, it is possible to make 4 groups.
group 1 : 1
group 2 : 0
group 3 : 2
group 4 : 3,4
Ah yes yes. My bad for the silly but later in the video, i have covered the fix ❤❤❤
And hence that’s the proof that we will have to try BFS from each node. Only trying BFS from 0 will not give best result. ❤❤
Thanks 😇🙏
your comment is also slightly incorrect, group 3 mein 2 hoga
Mai bipartitte bhool gaya tha. Aaj revision kiya ache se.
aapka graph concepts fir se revise karunga is weekend.
Same bhai😂
Sir, I want you to put daily questions like this continuously, this helps a lot to me. Thank you for these detailed explanations.
Legend ho aap 🙏🏻🙏🏻🙏🏻
explanation is amazing
thanks for this great video, I stuck on how to know which node to start BFS from in order to find maximum grouping didn't know brute force was the way lol. Grouped nodes together using Disjoint Set, then took maximum from each group
correct me if I am wrong but at 57:48 shouldn't the TC be O(V+E) as each node would be visited once same for 58:17
the quote you shared today is from Sir Alex Ferguson , former coach of Manchester United Football club
Thank you for sharing! 🙏❤️
@@codestorywithMIK And consistency beats hard work if the hard work isn't consistent.
Hi Mik I am using diameter of graph concept but it's giving error. Can we use this concept for finding maximum distance for each group rather than finding distance from each node
Everything was looking formal until Sir said khandani tareeka....Sir your way of teaching is amazing
Haha yes, "khandani tareeka" 😅🙏
Thank you ❤️❤️🙏🙏
Awesome video. But having a doubt, after bipartite validation, to find the total number of groups can't we use the diameter of graph concept for each connected components and summing up them, should result in the answer. I have tried that code, but 51/55 testcases passed. Not sure, why this will not work?
sounds like a good idea can you share your code i want to see what is failing.
@@gui-codes Not able to put link because of youtube restriction.
class Solution {
public int magnificentSets(int n, int[][] edges) {
Map graph = buildGraph(edges);
int[] coloring = new int[n];
boolean[] visited = new boolean[n];
// not possible scenario
for(int i = 0; i < n; i++) {
if (!visited[i] && !isBiPartite(graph, i, coloring, visited)) {
return -1;
}
}
visited = new boolean[n];
int totalGroup = 0;
for(int i = 0; i < n; i++) {
if (!visited[i]) {
totalGroup += findDiameterOfGraph(graph, i, n, visited);
}
}
return totalGroup;
}
private Map buildGraph(int[][] edges) {
Map map = new HashMap();
for(int[] edge: edges) {
int u = edge[0] - 1;
int v = edge[1] - 1;
map.putIfAbsent(u, new ArrayList());
map.get(u).add(v);
map.putIfAbsent(v, new ArrayList());
map.get(v).add(u);
}
return map;
}
private boolean isBiPartite(Map graph, int start, int[] coloring, boolean[] visited) {
Queue q = new LinkedList();
q.add(start);
visited[start] = true;
coloring[start] = 0;
while(!q.isEmpty()) {
int node = q.poll();
for(int neigh: graph.getOrDefault(node, new ArrayList())) {
if (!visited[neigh]) {
coloring[neigh] = 1 - coloring[node]; // 0 or 1
visited[neigh] = true;
q.add(neigh);
} else if (coloring[neigh] != 1 - coloring[node]) {
return false;
}
}
}
return true;
}
private int findDiameterOfGraph(Map graph, int start, int n, boolean[] visited) {
int[] pair = traverseTillLast(graph, start, visited);
int oneEndNode = pair[0];
pair = traverseTillLast(graph, oneEndNode, new boolean[n]);
return pair[1]; // final distance from oneEndNode to last node
}
private int[] traverseTillLast(Map graph, int start, boolean[] visited) {
Queue q = new LinkedList();
q.add(start);
int level = 0;
visited[start] = true;
int lastNode = start;
while(!q.isEmpty()) {
int n = q.size();
while(n-- > 0) {
int node = q.poll();
lastNode = node;
for(int neigh: graph.getOrDefault(node, new ArrayList())) {
if (visited[neigh]) continue;
visited[neigh] = true;
q.add(neigh);
}
}
level++;
}
return new int[]{lastNode, level};
}
}
Same😢😢, I don't know why the diameter code is not working. When we find diameter from another graph, we always get farthest node in first bfs and get diameter in second bfs, But in this 52nd test case, we are not able to find the farthest node which is 11 and 17. That is why the diameter is also coming out wrong. I tried the whole day but I am not able to understand why this is happening😢😢
Does anyone found why it didn't work. since morning I am not able to figure why it failed
@@tanmaypal2003 true
Fist view 🎉❤
Hi MIK just one doubt. For finding maximum level in group can't we find the end node of each group(and find the level using bfs) rather than doing bfs/dfs for all node and then sum of all distance for each group.
It's important to find bfs of every node bcoz if you observe the answer is highest when you start from the node having the least no of children or connection
in example 1, why dont we put 5 in group 3 with 2 and 4 nodes?
example 1 me 5 group-3 me hi gaya tha with 2 and 4. but it will reduce the number of groups to 3. we can increase the group number, if we were able to put 5 in a separate group without breaking any rule, we did that and hence groups count increased to 4
@@gui-codes ok, got it. rules+ maximising factor need to be keep in hand.
Hey mik 👋🏻 , when will you upload 2D dp concepts video in your dp concept and question playlist....
Soon uploading more ❤❤❤
Vai please make a vdo on this 2 leetcode problems please
Serialize And Deserialize Binary Tree and
Design Twitter
what if a graph contains a cycle with even no of nodes?, it seems to be bipartite but will we be able to break it into groups?
It always will be bipartite
bhaiya please upload videos on weekly contest as well
Bhaiya bipartite word hi college mein kabhi nhi bola, to bipartite graph kyese parayenge
Unfortunately college professors skip such important topics. I remember i was taught Bipartite topic in Graph Theory subject.
But no worries, I hope my Bipartite video will help you 🙏❤️ see the link in the video description
bro add some outro to your video, i was tryna pause it at the end, and it restarted
You are absolutely right! 🙏❤️ I'll add an outro to my videos in the future!
@@codestorywithMIK yeah thanks for considering
10:00
15:00
27:00
44:00
❤🦸Superhero🦸of dsa coders❤
Means a lot Sandeep ❤️❤️🙏🙏
pichle 2 ghante se preshaan tha mai ek '&' k wajah se
Bilkul bhi logic khud se nhi bana 😔...i need more practice in these types of questions
Same bhai. But koi nai, practice karenge aur 🔥🔥
ye dsu se bnaya jaa sakta hai ?
Yes it can be ❤️
Not a single video where the low battery notification is not there😅😂
sir when u reveal a face😁
I am not enough , I need to break my comfort zone ....
mik sir bipartite click hi nhi hua , feeling demotivated
Hi Bhupendra,
Please refer to Bipartite video -
ruclips.net/video/NeU-C1PTWB8/видео.htmlsi=e848CsDdohc5VWEe
I am sure it will help ❤️🙏
level sbke nikelenge
Mujhe apka tution join karna hai 😢
Use whiteboard....Please
bro apna avtar change krega kya
how did u get intution of multi node bfs
I actually got a wrong answer as I mentioned in the video. Then I realised that doing BFS from only one node will not guarantee best solution. So we have to try with every node. I felt bad to have missed this case when I was solving it but it was a good learning experience ❤️
Google me aise Q aa skte h kya ? For experience candidate.?
haa
I think is tarah k to definitely aa sakte hain. Video description me dekho, jo jo concepts use hue hain all are simple, but un sab ko combine karke ek Qn bana diya gaya hai islie hard lagta hai. Google usually yahi check karta hai ki aapko foundation kitne strong hai. For example is problem me dekho, bipartite check, bfs and dfs hi likha hai bas zyada se zyada bas starting intuition lagane ki deri hai.
Yes ❤
@@gui-codes wahi to ni ho rha h starting ka thinking ...but yes bipartite sun k I got some idea, going to implement, BFS implementation
@ just focus on intuition and approach ,,, har ek person ka usko code mai convert krne ka tarika alag hota hai,, jab bhi intuition and logic clear haii tab coding part dekho ignore kro aur khud se hi code likhna start kro ,,,then compare ur code with mik's code mai har bar aaisa hi krta hu
bhaiya please upload videos on weekly contest as well
bhaiya please upload videos on weekly contest as well