Hi all, sorry for the delay in upload as you all know I have not been well for a few days. I am sure you all will understand. I want to thank all of you for consistently solving problems with me and today we have earned 2023 Leetcode April Badge. Congratulations to all of you for being consistent. Keep it going. My Respect and Love to all of you who have trusted my channel and shown support. ❤❤❤❤
Dear MIK, I just want to give a huge shoutout to you for the incredible work you do on your channel! Your videos are always so well-researched, engaging, and easy to understand, no matter how complex the topic. You have a unique talent for breaking down complicated concepts and making them accessible and enjoyable for everyone. The passion and dedication you bring to each video are truly inspiring, and it's clear how much effort you put into helping others learn and grow. Keep up the fantastic work-you're making a real difference in the world of education, one video at a time! myself kallu kaliya
Great video MIK❤ I did it by myself. Just because of ur teachings i was able to do many questions in this playlist by my own without even looking. I did the same in first go by sorting. Then i thought that instead of sorting we can just do 1 traversal where we deal with type 3 edges firstly.Then another traversal to deal with type 1 and type 2 edges.O(N) complexity only❤
thanks , jab poori graph playlist dekhunga tab aur samjh aayega btw we should use cameCase while naming variables... (fyi -- this is a sonar code smell as well)
Without Making Structure !! class Solution { public: vectorbob; vectoralice; int find_bob(int i) { if(bob[i]==i) return i; return bob[i]=find_bob(bob[i]); } int find_alice(int i) { if(alice[i]==i) return i; return alice[i]=find_alice(alice[i]); } int maxNumEdgesToRemove(int n, vector&edges) { int count_bob=0; int count_alice=0; for(int i=0;i
Java Solution: class Solution { public int maxNumEdgesToRemove(int n, int[][] edges) { DSU Alice = new DSU(n); DSU Bob = new DSU(n); // sort the array on basis of type in order to reduce no. of edgesRequired Arrays.sort(edges, (a, b) -> b[0] - a[0]); int edgesRequired = 0; // Perform union for edges of type = 3, for both Alice and Bob. for (int[] edge : edges) { int type = edge[0]; int u = edge[1]; int v = edge[2]; boolean isEdgeAdded = false; if (type == 3) { // Alice if(Alice.find(u) != Alice.find(v)) { Alice.union(u, v); isEdgeAdded = true; } if(Bob.find(u) != Bob.find(v)) { Bob.union(u, v); isEdgeAdded = true; } if(isEdgeAdded) edgesRequired++; } else if (type == 2) { //Bob if(Bob.find(u) != Bob.find(v)) { Bob.union(u, v); edgesRequired++; } } else { // Alice if(Alice.find(u) != Alice.find(v)) { Alice.union(u, v); edgesRequired++; } } } // Check if the component is reduced to a single component for both Alice & Bob. if (Alice.areAllConnected() && Bob.areAllConnected()) return edges.length - edgesRequired; return -1; } private class DSU { int[] parent; int[] rank; // Number of distinct components in the graph. int noOfComponents; public DSU(int n) { noOfComponents = n; parent = new int[n + 1]; rank = new int[n + 1]; for (int i = 0; i rank[yParent]) { parent[yParent] = xParent; } else if (rank[xParent] < rank[yParent]) { parent[xParent] = yParent; } else { parent[xParent] = yParent; rank[yParent]++; } noOfComponents--; } // Returns true if all nodes get merged to one. private boolean areAllConnected() { return noOfComponents == 1; } } }
Hi , thanks a lot for the video, one query that, if I go with the approach where i count the edges which can be removed, instead of added edges. So, i am thinking like, for type-3, i will union the vertices if they are not in same parent set. For type-1 and type-2, if i check that they belong to same set i.e alice.find(u)==alice.find(v) then that edge can be removed and similarly for bob. But this gives wrong answer for larger test case--- Could you pls correct my approach where i am thinking wrong ? int maxNumEdgesToRemove(int n, vector& edges) { sort(edges.begin(),edges.end(), cmp); UnionFind alice(n+1); UnionFind bob(n+1); int count=0, a=n, b=n; for(int i=0;i
Sure definitely. Apologies for the delay since few days as I have been suffering from throat infection. Will take 3-4 days to recover and I will upload early like before. I want to thank you for watching my videos and trusting me
Definitely Uday. Actually the reason for delay since few days is because i have been suffering from throat infection and will take 3-4 days to recover. But i will start early as soon as I recover. Just give me this week time ❤️❤️❤️
Hi all, sorry for the delay in upload as you all know I have not been well for a few days. I am sure you all will understand.
I want to thank all of you for consistently solving problems with me and today we have earned 2023 Leetcode April Badge.
Congratulations to all of you for being consistent. Keep it going.
My Respect and Love to all of you who have trusted my channel and shown support.
❤❤❤❤
pls change the name of video its wrong
yess sir we alwys wait for your explanation video , we don't watch anyone's else
Done Avneet. Thank you ❤️
Thanks a lot Sidharth ❤️
get well Soon sir,, our blessings are always with you
This is why people call this guy DSA legend 🙏🏻
I suggest people to study graph from this channel. Never seen clarity and simplicity on this level
Dear MIK,
I just want to give a huge shoutout to you for the incredible work you do on your channel! Your videos are always so well-researched, engaging, and easy to understand, no matter how complex the topic. You have a unique talent for breaking down complicated concepts and making them accessible and enjoyable for everyone. The passion and dedication you bring to each video are truly inspiring, and it's clear how much effort you put into helping others learn and grow. Keep up the fantastic work-you're making a real difference in the world of education, one video at a time!
myself
kallu kaliya
Thankyou bhaiya , because of you I am able to make logic on my own and have earned 2 badges monthly June and 50days leetcode badge
I also earned June Badge, 50 Days Badge & 100 Days Badge with the help & guidance provided by MIK bhaiya :))
Great video MIK❤
I did it by myself. Just because of ur teachings i was able to do many questions in this playlist by my own without even looking.
I did the same in first go by sorting. Then i thought that instead of sorting we can just do 1 traversal where we deal with type 3 edges firstly.Then another traversal to deal with type 1 and type 2 edges.O(N) complexity only❤
So happy to read this comment. 🙏😇
one of the best explaination
Thank you sir, we wait for your video to get uploaded :)
Thank you so so so much . It means a lot to me
I can't thank you enough sir, earning badges every month wouldn't have been possible without ur efforts💓. Plz take care sirr...
Thank you so so much
It means a lot to me
you are one of my favourite tutors on youtube
You made my day. Thank you so much Utkarsh ❤️❤️❤️
Damn!!! The Solution was not initally easy you made it easy
thanks , jab poori graph playlist dekhunga tab aur samjh aayega
btw we should use cameCase while naming variables...
(fyi -- this is a sonar code smell as well)
This was one of the questions which I could solve using your previous posted video solution.
So glad to hear that Manoj.
Thank you ❤️❤️
Thank you!!!
Thanq bhaiya for solving this problem
Without Making Structure !!
class Solution
{
public:
vectorbob;
vectoralice;
int find_bob(int i)
{
if(bob[i]==i)
return i;
return bob[i]=find_bob(bob[i]);
}
int find_alice(int i)
{
if(alice[i]==i)
return i;
return alice[i]=find_alice(alice[i]);
}
int maxNumEdgesToRemove(int n, vector&edges)
{
int count_bob=0;
int count_alice=0;
for(int i=0;i
Class DSU{ int[]parents;
int[]rank;
Public DSU(int n){ parent =new int(n);
rank=new int(n);
for(int i=0; i interger. compare (b[0],a[0]));
DSU dsu_alice=new Dsu(n+1);
DSU dsu_bob= new DSU(n+1);
int Remove _edges =0 Alice _edges =0 bob_edges =0
for(int[]edge:edges){
if(edge (0)==3){
if(dsu_alice.union (edge [1],edge[2])){
dsu_bob union (edge [1],edge [2]);
alice Edges ++ bob_edges ++;
}else {
Remove _edges++
}
}else if(edge (0)==2){
if(dsu_bob union (edge [1].edge [2])){
bob_edges ++
}else
Remove _edges ++;
}
}else {
if(dsu.alice. union (edge [1].edge [2])){
alice _edges ++
}
else {
Remove _edges ++
}
}
return [bob_edges ==n-1&&alice edges ==n-1)?Remove _edges:-1;
}
}
Thanks
legend for a reason
I got April Badge. Thanks to you
good job brother
@@JJ-tp2dd Thanks to your JAVA solutions too
I got the April badge. Thanks to you 😇❤
I am so close to passing the solution, but 79/85 test cases are only passing. Ofcourse came back here to understand the intuition !
best explanation
Thanks a lot ❤️❤️❤️
Great Video ❤
Thanks a lot ❤️❤️
You are the best 💪
❤
🎉🎉🎉🎉
Java Solution:
class Solution {
public int maxNumEdgesToRemove(int n, int[][] edges) {
DSU Alice = new DSU(n);
DSU Bob = new DSU(n);
// sort the array on basis of type in order to reduce no. of edgesRequired
Arrays.sort(edges, (a, b) -> b[0] - a[0]);
int edgesRequired = 0;
// Perform union for edges of type = 3, for both Alice and Bob.
for (int[] edge : edges) {
int type = edge[0];
int u = edge[1];
int v = edge[2];
boolean isEdgeAdded = false;
if (type == 3) {
// Alice
if(Alice.find(u) != Alice.find(v)) {
Alice.union(u, v);
isEdgeAdded = true;
}
if(Bob.find(u) != Bob.find(v)) {
Bob.union(u, v);
isEdgeAdded = true;
}
if(isEdgeAdded)
edgesRequired++;
}
else if (type == 2) { //Bob
if(Bob.find(u) != Bob.find(v)) {
Bob.union(u, v);
edgesRequired++;
}
}
else { // Alice
if(Alice.find(u) != Alice.find(v)) {
Alice.union(u, v);
edgesRequired++;
}
}
}
// Check if the component is reduced to a single component for both Alice & Bob.
if (Alice.areAllConnected() && Bob.areAllConnected())
return edges.length - edgesRequired;
return -1;
}
private class DSU {
int[] parent;
int[] rank;
// Number of distinct components in the graph.
int noOfComponents;
public DSU(int n) {
noOfComponents = n;
parent = new int[n + 1];
rank = new int[n + 1];
for (int i = 0; i rank[yParent]) {
parent[yParent] = xParent;
} else if (rank[xParent] < rank[yParent]) {
parent[xParent] = yParent;
} else {
parent[xParent] = yParent;
rank[yParent]++;
}
noOfComponents--;
}
// Returns true if all nodes get merged to one.
private boolean areAllConnected() {
return noOfComponents == 1;
}
}
}
Thanks a lot bhaiya ❤❤
Hi , thanks a lot for the video, one query that, if I go with the approach where i count the edges which can be removed, instead of added edges. So, i am thinking like, for type-3, i will union the vertices if they are not in same parent set. For type-1 and type-2, if i check that they belong to same set i.e alice.find(u)==alice.find(v) then that edge can be removed and similarly for bob.
But this gives wrong answer for larger test case--- Could you pls correct my approach where i am thinking wrong ?
int maxNumEdgesToRemove(int n, vector& edges) {
sort(edges.begin(),edges.end(), cmp);
UnionFind alice(n+1);
UnionFind bob(n+1);
int count=0, a=n, b=n;
for(int i=0;i
Bhaiya thoda graph OA level questions bhi Kara dena
Sure brother. Let me try to find some OA qns.
Can you share some OA qns if you have already ? I can make videos on them
@@codestorywithMIK ok. Sure
One question I know that juspay asked in OA. Question name is largest sum cycle. You will find this in gfg
@@codestorywithMIK one more question detonate the maximum bomb. Asked in Google pay swe intern.
April Badge 🎉🎉🎉🎉🎉
My solution:
class DSU {
private:
vector link, sze;
public:
int path;
DSU(int n){
link.resize(n);
sze.resize(n);
path = 0;
for(int i=0; ibool{
if(a[0] > b[0]) return true;
return false;
});
DSU dsua(n+1), dsub(n+1);
bool f = false;
int count = 0;
for(auto u: edges){
if(u[0] == 3){ // both alice and bob
f = false;
if(!dsua.same(u[1], u[2])){
dsua.unite(u[1], u[2]);
f = true;
dsua.path ++;
}
if(!dsub.same(u[1], u[2])){
dsub.unite(u[1], u[2]);
f = true;
dsub.path++;
}
if(f) count++;
}
else if(u[0] == 1){ // alice
if(!dsua.same(u[1], u[2])){
dsua.unite(u[1], u[2]);
count++;
dsua.path++;
}
}
else{ //bob
if(!dsub.same(u[1], u[2])){
dsub.unite(u[1], u[2]);
count++;
dsub.path++;
}
}
}
if(dsua.path < n-1 || dsub.path < n-1) return -1;
return edges.size() - count;
}
};
🎉🎉
Thank you so much
BEST
Java Solution:
class DSU{
int[] parent;
int[] rank;
int components;
DSU(int n){
parent=new int[n+1];
for(int i=1;irank[y_parent]){
parent[y_parent]=x_parent;
}
else if(rank[x_parent]Integer.compare(b[0],a[0]));
int edgeCount=0;
for(int i=0;i
Thanks bro
BESt!
aaj ka sol to copy karke dalna padega, dsu padne ke lia playlist ki sari video dhakni padegi ky??
for bob and alice ke liye hum alag alag variable of components .. substract kar skte hai and then check in the end if that is 1??
bhaiya ap video thora aage upload kar sakte ho kya ??
Sure definitely. Apologies for the delay since few days as I have been suffering from throat infection. Will take 3-4 days to recover and I will upload early like before.
I want to thank you for watching my videos and trusting me
@@codestorywithMIK ❤️
@@codestorywithMIK take care bro
bhaiya aaj ka contest ka 3rd ka video bna do plzzz
weekly 404
Thank you helping me get the April badge bhai ♥💙♥ Java Solution:
class DSU {
int[] parent;
int[] rank;
int components;
DSU(int n) {
this.parent = new int[n+1];
this.rank = new int[n+1];
components = n;
for(int i=1; i rank[y_parent]) {
parent[y_parent] = x_parent;
}
else if (rank[y_parent] > rank[x_parent]) {
parent[x_parent] = y_parent;
}
else {
parent[x_parent] = y_parent;
rank[y_parent]++;
}
}
components--;
}
boolean isSingleComponent() {
return components == 1;
}
}
class Solution {
public int maxNumEdgesToRemove(int n, int[][] edges) {
DSU Alice = new DSU(n);
DSU Bob = new DSU(n);
Arrays.sort(edges, (a,b)->b[0]-a[0]);
int edgeCount = 0;
for(int[] edge : edges) {
int type = edge[0];
int u = edge[1];
int v = edge[2];
if(type == 3){
boolean edgeKraYaNi = false;
//Alice
if(Alice.find(u) != Alice.find(v)) {
Alice.Union(u,v);
edgeKraYaNi = true;
}
//Bob
if(Bob.find(u) != Bob.find(v)) {
Bob.Union(u,v);
edgeKraYaNi = true;
}
if(edgeKraYaNi) edgeCount++;
}
else if(type == 2) {
if(Bob.find(u) != Bob.find(v)) {
Bob.Union(u,v);
edgeCount++;
}
}
else {
if(Alice.find(u) != Alice.find(v)) {
Alice.Union(u,v);
edgeCount++;
}
}
}
if(Alice.isSingleComponent() && Bob.isSingleComponent()) {
return edges.length - edgeCount;
}
return -1;
}
}
I want to thank you guys. For being with me and trusting me. I can’t believe how far we all have come together ❤️
Let’s keep it rolling
@@codestorywithMIK love you bhai..full trust and support to you always ❤
Also, give me 3-4 days, I am recovering from throat infection.
I will be uploading multiple videos on Graph Concepts with continuity.
@@codestorywithMIK Couldn't be more excited bhai Thank youu😄but please take your time to recover completely first
Hello sir, can you provide the link for how you constructed DSU class?
th-cam.com/video/AsAdKHkITBQ/w-d-xo.htmlsi=XdHB-vmfh7_a6Gz8
You can watch this and 2 more after this. That will help ❤️
@@codestorywithMIK Thankyou sir🙏
Bro, Change the video title
Thank you so much for pointing out.
Corrected
@@codestorywithMIK Can u pls upload videos by everyday evening?
Definitely Uday. Actually the reason for delay since few days is because i have been suffering from throat infection and will take 3-4 days to recover.
But i will start early as soon as I recover. Just give me this week time ❤️❤️❤️
@@codestorywithMIK Ok bro take care