Build a Matrix With Conditions - Leetcode 2392 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem build a matrix with conditions okay so since we all got things to do in places to be I'm going to try to make this quick don't hold me to that though so the first thing I'm going to do is just go through the problem description because to be honest it's kind of long and pretty complicated second I'm going to show you that the intuition to solve this problem is actually very similar to yesterday's problem while at least trying to figure out the general idea third I'm going to explain the core algorithms you're going to need because even if you're a genius and you kind of know how to solve the problem the algorithms themselves are actually kind of complicated that's why I always say that you should know algorithms like DFS very very well because when you get to a problem like this DFS is only a small part of this problem finally we're going to code it up in Python lastly when I'm done with that I'm probably going to take a break because to be honest it's been a long week and I'm sure you might feel the same so let's get into it the idea is let's focus on the example we're given K so tells us the dimensions of the output Matrix that we want so it's going to be K by K it's going to be a square Matrix next we're given these two input arrays this is kind of the complexity of the problem what the first array is saying is that these two numbers are going to well first of all let me just say that the only values in this are going to be the numbers 1 through K the only values in column conditions are going to be the numbers 1 through K and we want to take the numbers 1 through k and put them in this Square Matrix now that might sound confusing because if we have a k byk Matrix how can we fill it with just K elements well the remaining elements are going to be zero so only K elements are going to be populated 1 through K obviously in this example K is three so what the first array row conditions tells us is that one will be in a row above the value two so theoretically we could have had one over here and two over here or we could have had one over here and two over here or we could have had one over here and two over here and that's what we ended up with now there's a second condition 32 so three has to be above two two could have been here or it could have been here or maybe three could have been here and then two could have been down there so it's a little bit ambiguous isn't it right now the ordering is three one 2 for the rows we could have I think had 1 3 2 because all we need is one to be above two and three to be above two and I think both of these satisfy that condition when they say above it needs to be strictly above so they can never share the same row the second array column conditions is pretty much the exact same thing except for column so if we have 2 one we say two has to be to the left of one it could have been like this or it could have been you know like this or it could have been like this now once you realize that these are saying it needs to be strictly different like it needs to be above or with the columns it needs to be to the left you kind of realize that every single element in the Matrix is going to have its own row and its own column that's kind of an important observation to make right like here you can see everything has its own row and own a column so this kind of makes the problem seem like it's not the end of the world doesn't mean it's easy but I'm about to show you how you can actually make it easy for yourself look I'm not going to lie to you I still don't know how to solve this problem so what can we do let's just try to simplify it for a second forget about the columns let's take this two-dimensional problem and turn it into a one-dimensional problem if we only had to deal with rows how would you solve the problem well I don't know about you but this is kind of giving me vibes from the problem course schedule if that's not enough maybe you've solved that crazy hard problem alien dictionary is it giving you similar Vibes because it is for me if we only have one array it's basically saying that one is a prerequisite of two like one is like a directed Edge kind of right like one is going to be above two and we're also saying three is going to be above two as well so if we were actually to draw it as an entire graph we'd have a graph that looks like this and this is only for the rows by the way so now it kind of becomes clear well it becomes clear if you've heard of the algorithm topological I I don't know how to spell today I'm really sorry topological sort if you don't know what this algorithm is I'll try to teach it to you because it's not super bad but at the very least I hope you do have a decent understanding of DFS if not I have plenty of other videos you can check out n cod. but definitely get a good understanding of DFS before attempting this because what topological sort says is what is a valid way that we could order the values in this graph so that they're actually visited in the order that the edges are represented such that basically for us to visit to we visit all of its prerequisites first so basically one valid ordering would be 1 3 and then two or 3 1 and then two so like those two orderings I said would work now we've kind of solved the problem in one Dimensions if we didn't have to worry about a matrix if we were just ordering the values on which like row each element is going to go in we've pretty much solved the problem haven't we okay but that's not enough because if we say okay we have 3 1 2 well we got to put these in different columns well can we just take the exact same technique and apply it to the columns why not I'm going to do exactly that and let's just try it and see what happens so down here I'm going to have the columns graph I'm going to take these edges build a graph in ter terms of code we generally use something called an adjacency list so that's what I would do but visually it's going to be looking something like this so two goes into one and three goes into two okay so this time it's actually very straightforward there is not a choice here it has to be in this order meaning the columns the First Column has to be three the second column has to be two and the First Column has to be one okay so that makes sense so far and we've pretty much solved the problem if you don't understand it let me kind of draw it out for you suppose I took one of those valid orderings from the row let's just represent it in terms of a list and I'll kind of do it consistent with this example so let's say we did three first and then one and then two these are the orderings of the rows and then same thing for this we got 3 2 1 this is the ordering of the columns now what does this tell us it might not seem obvious but if three is in the first position it's going to go in the first row meaning it's going to go in row zero one is in the second it's going to go in row one two is in the last position it's going to go in row two three is going to go in column zero this is going to go in column one this is going to go in column two so basically the index that each element shows up in is going to be the like coordinate it's going to be assigned so three you can see three is at row Zer and column Zer so it's going to go obviously at 0 0 one is at Row one and column 2 so it's going to go at Row one and column index two so right over there lastly two is at row two column one so it's going to go at row two column 1 and that's exactly it look we just did it conceptually it's not super crazy even this by the way like I drew this out like it's so simple but even this in terms of code how do you think you'd code this up because the way I filled this in was number by number so the way we're going to code this up is actually by converting this into a hashmap but that's a minor detail I think can be explained more easily in the code explanation we're actually not quite done with the drawing explanation yet there's a couple other things we have to cover one is going to be how does topological sort work how am I going to implement it it's very similar to DFS with a couple differences second there is an edge case that we do have to consider because it's Poss possible that the Matrix is not valid let me actually start with that can you think of what would have to happen for the Matrix to not be valid well we need a contradiction right so what if I said okay Row one is above row two this is a one Edge row two is above Row three and then I tell you well Row three is above Row one do you see the contradiction like if I put one here and then I put two down here and and then 2 is above three how can three be above 1 it's a contradiction so how would the graph for this look like let's say something like this 1 to 2 2 to 3 and then 3 to 1 now you might see we know it's invalid if either of the graphs either the row graph or the column graph has a cycle then it's invalid we'll get stuck in like an infinite Loop now how would you detect that there is a cycle because consider this for a second just consider like a random looking graph that looks something like this uh one maybe goes into two and three and then both of these go into something called four like imagine we have a graph that looks something like this this does not count as a cycle it doesn't count as a cycle because from one we can go to three and then we go to four that's it then we go back to three we go back to one and then from there we go to two and we get back to four yes we visited the same one twice but that doesn't mean there's a cycle a cycle would mean that you know along the same path we keep going and then we get back to a previously visited node this is not a cycle because we go here and then that's the dead end then we go all the way back and then we go down here and then we go all the way back I don't see the cycle here because there isn't a cycle in this graph so the way I'm going to detect Cycles is by having one hash set for visit did because we don't want to have repeated work we don't want to end up visiting the same node twice consider if this one had some descendants and we wouldn't want to have to Traverse them multiple times so that's going to be one hash set but the hash set that's going to detect Cycles I'm going to call it the path hash set and I'm always going to add every node that's along the current path in that hash set if we pop back I'm going to remove that node from the hash set but nothing is ever going to be removed from the visit hashset so that's the small distinction and that's pretty much the main distinction the only other point that you need to know in terms of like how I'm going to implement topological sort there are a couple ways to do it but I'll show you why I prefer doing it the way I'm going to show you consider pretty much the same graph actually and then uh maybe like we have some choices here like we have a five here and believe it or not topological sort works on a disjointed graph so you can see these are all connected but imagine I had six and it connects to seven and imagine I had like eight to nine so imagine a graph like this how is topological sort going to work well basically these ones are pretty straightforward the topological sword of this would just be 8 9 the topological sword of this would just be 67 the topological sword of this would be more interesting there'd be more choices here so we definitely have to start with one and then we have a choice of either three or two let's pick three we can't go to four yet because we haven't met the prerequisite so we have to also have two here now that we have one we have 3 two we can either pick four or five the order of these doesn't really matter we could have it either way I'll just write it like this with topological sort it's non-deterministic there could be multiple correct Solutions well I don't know if non-deterministic is the best word to describe it but it could have multiple orderings so how would we actually arrive at this in terms of code well the way I prefer to do it and you might have a different opinion I run a dep first search I run the depth for search until we get to the base case so this is what I would do I would have my output array which is going to be the topological sort ordering I'm going to get to one I'm not going to add it yet I might add this to the visit hashset but I'm not going to add it to the output yet I'm going to do it in reverse order I'm going to get to one I'm going to get to two then I'm going to get to five okay five is the one that doesn't have any more descendants it's kind of the base case so I'm going to add it at the beginning I'm going to go back up to two I can't add two yet I'm not going to add two to the output yet I'm going to wait until I do all of its descendants so four is one of The Descendants now I'm going to add four to it and now that I've done both of its descendants now I'm going to add two to the topological sort output and then I'm going to pop back up to one and I haven't done all of one's descendants yet so now I'm going to go to three and then I'm going to do all of its descendants its descendants have already been visited so I'm going to go back now three all of its neighbors have been finished so I'm going to add three to the output ordering and then I'm going to pop back up to one everything's been finished so we can go ahead and add one to the output the only thing about this is It's not what we want but it's an easy thing for us to fix just take this and reverse it that's it because with topological sort what we're trying to do is visit each node before we do all of its descendants it seems like it might be easy to do but this example will show you it's not if I tried to do okay add one then add two then add five okay it seems like it's working so far then add four and then we go back up to one and then we add three well do you see the contradiction how did we have four before we added the three that's why it's easier to code up if you do it in reverse order you add these the nodes that don't have any more descendants you add them first and then you can just reverse the output so that's pretty much everything you need to know to solve this problem and in terms of a Time complexity I assume that there's not going to be any duplicates in here so it's basically going to be bottlenecked based on the traversal which we're going to run two times but that's a constant so it doesn't matter so how big could one of these graphs possibly be I guess in the worst case each value could be connected to every other value so I think in the worst case that's k^ squ so this is like the literal worst case I don't think it'll actually be that much so I guess um it's either k^ s or the maximum of either of these two it's going to be the minimum of those so I guess you know just take the length of either of these actually now that I think if we're going to be creating a matrix like this I think k^ squ is probably the most appropriate way to put it so I'll be leaving it at that so now let's code it up uh I don't know how helpful this is but this is the train of thought that I had um you can see it's going to be kind of a lot of code so I'll try to keep it relatively organized so the way this is going to work is we're going to run topological sort but remember the example I showed you where we had a disjointed graph where the graph isn't connected we can't just pick one random node in the graph and then run top logical sort on it we might have to run top logical sort from literally every node in the graph and we can mark them visited as we go so that's why we're actually going to split this up into two different helper functions I'm going to have one helper function for topological sort it's just going to take in the list of edges either this or this and we're also going to have a function for depth for search that's the one where kind of the bulk of the work is going to be done so let's just think about it abstracted for a second let's think about it from a high level the way I'm going to be calling topological sort is like this I'm going to call it twice passing in row conditions the first time and I'm going to be passing in column conditions the second time and what we expect this to return is pretty much what I had in the drawing this is going to return the row order of the numbers the order that the numbers should appear in in terms of the row the other one is of course going to do the column order so these are going to be arrays these are going to be lists the way I'm going to code up the topological store is if there's a cycle I'm going to detect that by returning an empty array so if either of these is an empty array if not row order or not column order then we're going to return an empty array because that's what they pretty much told us to do in the problem description if that's not the case assume that you already have these two maybe in your real interview you don't know the implementation details of either DFS or topological sort but you know that those are required to solve the problem I think it's better to actually start with this part of the code because then at least you know where you're going if you can Implement these you can solve the problem so here what I'm going to say is we have these but what we're trying to do is populate the result Matrix so I'm actually going to initialize that down here in pyth on it's pretty straightforward to do it's going to be K by K so something like this and now I want to go through every number from 1 to K num in range 1 through K and I want to say that at some row column position I want to assign this numb but we don't know which row that this number belongs to or which column it belongs to but the fact that we have the column and row ordering we can get that with these data structures we wouldn't be able to get it in constant time so I'm going to convert convert these two lists into hashmaps or dictionaries in Python so I'm going to say before this over here I'm going to say value to row hashmap and you know you could probably code this part up like in your language of choice in Python I'm going to try to keep it concise because this is going to be a long enough solution as it is so I'm going to use something called dictionary comprehension right now I'm also going to enumerate I'm going to say for i n in enumerate row order so this will give us the index and the number in that array of course we want the number to be mapped to the index which tells us the row so I'm going to say n maps to I I'm going to copy this and just update it slightly by renaming this to Value to column and renaming this column order so it's going to do the exact same thing for column order so then down here I'm going to look up the row and column with these two data structures just just like that and assuming we do that we should have the result and we can guarantee that row order and column order if they're non-empty are going to include every number from 1 through K because even if the graph is not connected even if it's a disjointed graph we're going to visit every Edge and I'm going to show you that part right now I just happen to know it off the top of my head because I know how topological sort works at a pretty decent level this is like an advanced algorithm which is why I cover it in my Advanced algorithms course I don't expect you to like be an expert on this so if we're passing in the list of lists generally that's not how we want to run a DFS so the first thing we're actually going to do in here is convert it into an adjacency list so I'm going to call it adjacent default deck and I'm going to pass in list and so that will make it easy for us to do this for Source destination in edges because we know we're dealing with directed edges here so I'm going to say that for this Source node I'm going to append to its neighbors this destination note so that's just initializing the adjacency list the next thing we would want to do over here is go through every Source from one through K so I'm going to say 1 through k + 1 and then run a DFS on it now of course we're going to have to pass in the source node to run the DFS but there's a few other things we're going to have to pass in as well another thing will be the adjacency list obviously another thing is going to be the two hash sets that I talked about we want them Mark positions visited we don't want to get stuck in an infinite Loop and we also want to be able to detect a cycle so we're going to create two hash sets for those I'm going to just copy that right there there is one last parameter we're going to pass in it's going to actually be an array I'm going to call it order because remember ultimately what we're trying to do is collect the order so that's kind of what I showed in the drawing explanation when we reach the base case in DFS that's when we will append a node or not even a base case but once we visited all the neighbors of a given node so um here I will create an array for the order and then remember before you return the order you definitely want to make sure to reverse it in Python you can do that pretty easily like this and here I'm just going to make a comment that that's reversing it now what about cycle detection the way I'm going to detect a cycle is like this that's actually the first thing I'm going to do in the DFS other than I guess assign what parameters we're going to have for it so all these parameters so if source is in path and the other one is if source is in a visit I very specifically put this one first because if a source node is along the path that we're already on then we detected a cycle if that's true though this is also going to be true we want to know if this one is true more because this is the case where we've detected a cycle and that's when we're going to return false in the other case down here I'm going to return true this might make more sense when I finish the rest of the function because as you'll see when we get to a node we're going to mark it as visited immediately add this to visit so Source also I'm going to say add it to the path just like that and then I'm going to run my DFS somewhere over here and then when I'm done with that I'm going to say okay now path. remove this node but we're never going to remove a node from visit once a node is visited it should never be visited multiple times Okay so so now the actual DFS part it's not super crazy let's go through every neighbor of the current node that's exactly why we have the adjacency list so uh Source now we run DFS on the neighbor so passing in the same adjacency list same visit hashset same path hash set in same order array now what if we returned false from one of the base cases like what if we returned false from here what should we do in this case well probably return false immediately because once you detect a cycle there's no point in continuing so as soon as we see it if not this then just return false no need to visit the remaining neighbors if we never detect a cycle though down here let's just go ahead and return true there's only a couple things left first of all the order variable we haven't really used it anywhere and that's because we're saving it once we go through all the neighbors of a given node at the end after all that is when we append the current node so that's just the DFS portion okay I actually did have a typo so this is going to be Source sorry and I think we're actually nearly done I'm just going to quickly read through the rest of the code so I think the DFS looks good it's very easy to make a bug in a solution like this where there's so much code so that's another challenging part about this here if the DFS returns false so if not DFS here then we should return an empty array there's no need to continue running DFS and we definitely don't want to return the values that have already been added here at this point we return an empty array so that here we can detect that and then return an empty array now before you call DFS you could check if Source has already been visited but that's literally a base case in the DFS so it'll execute immediately anyway so I don't think it's necessary to have that line here um but here we're calling topological sort getting the output orderings um this is the case where we detected the cycle then we otherwise we convert it into the hashset down here we ize The Matrix we get the row and column here actually I think I messed this up these are hash Maps um we want to look up this number we want to map it to its row so I'm going to fix that and here we want to map that to its column so I'm going to do that as well now I think this is pretty much correct but it's hard to fit it all on one screen yeah I don't think it's possible to fit it all on one screen I'm really sorry I'm trying my best it's just really it's it's 40 lines of code we should be able to get it so that's a best I can do you might have to zoom in but I'm going to run it and it does look like it works and it's pretty efficient if you made it this far good job give yourself a pat on the back I'm going to go take a break thanks for watching and I'll see you soon