LeetCode 1761 - Minimum Degree of a Connected Trio in a Graph - Python

hello and welcome to another video in this video we're going to be continuing down that zero track list of problems with 2K and higher rating and I will point something out really quickly that I never did so actually you can get a Chrome extension called um leak code difficulty rating and what it does is instead of the easy medium hard it actually has the halo the problem and it's really nice because like mediums can be all over the place you know like we were doing mediums that were like 2,000 there mediums that are like 1,200 1300 so you kind of get a really good idea of the difficulty of a problem quickly instead of the easy medium hards can also vary a lot so yeah okay so here end directed graph n number of nodes edges connected tree is a set of three nodes where edge between every three so I guess like this degree of a connected trio is a number of edges where one end point is in the trio and the other is not return the minimum degree of a connected trio minimum degree of a connected trio or negative one if there's none okay so let's take a look so there's exactly one trio so one two three and the edges okay so I think this basically means this is how you can calculate the in degree of a connected trio so count edges that aren't part of the trio essentially but are connected to nodes in the trio i think that's correct right so like these are part of the trio and then everything else that's connected to one to three is not so we have three here okay and this is how you get the edges for one connected trio so we do that for all them we just return the minimum that part's easy let's see if there's any other this is three trios one three four okay so there's this one this one okay so here for example okay so yeah so the connected trio of like 256 is two because there's these two edges that aren't part of it and for this one there's also two and for this one all the edges are part of it okay so I think so i think it's pretty simple to be honest i think we just make a graph and then let's take a look at the constraints okay so constraints 400 so I think we just brute force every combination so we can just pick like three edges so it'll be like 400 by 400 by 400 which is what 16 64 six zeros so that's roughly maybe round this up to this or something was that going to pass actually n cubed uh it won't it won't quite be in cube but yeah I think it might be 400 by 400 by 400 so six zeros seven zeros it'll be close yeah it'll be close okay let's give it a try i don't know if we can do anything better maybe like is there a smarter way of figuring out what I don't think so because there might be a ton of connected trios yeah so let's just try that and see if we get a T or whatever all right so let's go graph can there be duplicate edges no okay okay so yeah so uh and then I think we want to have uh a set of Yeah yeah so for every node we'll just have a set of like what nodes it's connected to when that's an edge yeah so we set here and we can do this i forget the timer again i'll do the next time uh bam so graph xy all right so result we'll make that like infinity all right all right so how do we calculate how many edges um so what if we just take like all the edges of every node so here this will be three this will be three this will be three and then so first we determine if it's a connected trio and if it is we can just take all the edges of every node and subtract so every node will have two edges that are in the trio and everything else will be without so I think we can take 1 plus two plus three edges counts and just subtract six because this will be two two two all right let's give that a go so we just do a triple loop on M and the way to avoid duplicates is well it wouldn't really matter we can go through duplicates it would be the same but the way to avoid duplicates is just have strictly increasing numbers so we would do like 1 2 3 2 3 4 and so on so we can say if we're in range I + one N J + one and so we need to check if it's a connected trio so if uh J in graph I so that means that I and J are connected and we need I and K to be connected so K in graph I and then we need J and K to be connected i mean you can check either ones fine okay so now we know it's a connected trio then we just do and then res length graph I plus J and K j okay minus six all right and let's return all right we need them all lengths all right let's take a peek at that okay work yeah see if we get a te if we get a te maybe we can do something better oh never mind we just got null uh all right so if Yeah how do we get null we never return i guess return res if res does not equal yeah this right float in else is zero is that what we want to return zero negative one yeah how do we get null we never we never return interesting so let's use this test case so 12 4142 so this is basically this is a connected trio so how do we get null Let's see what this returns now oh that's really weird okay we had negative one y one two one let's print the graph okay so 1 2 4 214 412 okay cool so this might be wrong then if I n one if J and graph I and K and graph I so let's just double check that so here like J would be two K would be uh three or four so J and graph I is true k and graph I is true j and graph K is true raz equals length graphi plus length uh so we can print like got here or something make sure this is working see we did not interesting why uh let's print JK see just make sure getting the right numbers see why do we get zero zero is not in here uh right it's just one to see no yeah so there's no zero so start there one okay now let's see it again i mean it shouldn't matter one two three okay so how do we get negative one so if J in graphi should be I mean we'll just do one at a time I guess kind of stupid but okay got that one and can graphi okay got that as well I don't know how we got there multiple times interesting oh it's because Okay so we didn't get what How let me delete uh these test cases actually I think there's a way to delete just look at this one yeah how i mean obviously there's like other ways I can write it but yeah okay so now we did get there um okay now we didn't so I J K J + one N K so K in graph I did we change I and J or something ever no yeah so K in graphite so K is three oh wait K is three that's why oh I see oh okay so So K is three uh wait what can let's see your integer n number of nodes I see so this is n so one two three oh okay yeah I see I see so we just need n plus one now I think graph I uh uh I So I and J are connected k and I are connected and now we need uh K and J right so graph J all right cool i mean technically I could have just added this yeah if if this gets T we can also have less edges but let's see if we need to do that or not okay fine oh yeah so all right see if we get T no okay so what we can um another thing we can do is we can just always add the edge to we don't need to add the edge to both because we're always doing increasing so let's just add it to the smaller one or the bigger one or Sure let's always add it to the smaller one i guess that' be fine we don't need to add it to both actually no we do need to add it to both because we need to see how many each one has yeah never mind okay so I think this is fine then let's take a look at all of them looks I can't I mean this is pretty unreadable oh we got a Russian JK same so they use a list instead of a map and I mean this is fine too same yeah dot all right well okay cool stop spending time on this this is good it's fine i think this is like the only solution so yeah i was curious if there's better n cubed n cubed okay interesting yeah i mean you can use an adjacy list just because there's less overhead or sorry matrix I guess would make sense yeah matrix with counts things like that makes sense less overhead but whatever it's fine all right uh so cubed space so for every basically storing graph every node can have every other node so I think this just n squ Yeah because there's n squed edges as well right so n squ Yeah all right so yeah going to be it for that one definitely an easier one screwed up a little with the this but whatever um yeah definitely an easier one not so bad so we'll see what happens once we get to kind of like 2500 and so we'll see and I've done a lot of these as well so we'll seeuh how it goes so far not too bad but this will be kind of fun because most of these problems should wouldn't take me like 10 minutes it would you know hopefully they take me anywhere from 20 to 40 and be kind of interesting and I think there's a lot to learn from these problems there's going to be a lot of like advanced topics and things like that and not just like the daily whatever like you know post order traversal for the 50th time so it' be more interesting but yeah stay tuned for more try this extension and also try the zero track and I'll link that as well so thanks for watching