Maximum Number of Points From Grid Queries - Leetcode 2503 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem number or maximum number of points from grid queries so it's definitely a hard problem but I don't think it's crazy difficult for like many hard problems at least not saying it's easy at all but let's get into it we are given here a grid we're not given three grids so just to be clear we're only given a single grid so imagine that this is the input but we're going to be given a list of query and for each of these queries we're going to have exactly one answer and that value is going to correspond to the answers array and the Order of these is going to matter so if like we have five in the first query well the output of that query has to be the first value here and I mention that because in the solution of this problem we're actually going to need to change the order of these queries so that's a little hint for you if that's what you're looking for but in terms of how to answer each query basically it's sort of like a little simulation I guess I could just go through the example here let's say these are our queries we can start with five and how we answer it is we take this grid over here we start at the origin at the top left 0 0 and then basically we are allowed to go in any direction we're basically allowed to do a traversal on this grid we are allowed to revisit the same values multiple times but but the catch is that we are only allowed to visit cells that have a value strictly less than this query not equal but less than the query so here we start at one so maybe we go down here to two we can't go right cuz that's a five but maybe we can go down to three okay then maybe we go back up because we can't really go anywhere anymore and then we come back here we go to two we go to three okay looks like can't really go anywhere else can't go to 7 five or this five so we were a ble to visit five cells so we say that that's the number of points that we were able to collect in the context of this problem and so the answer to the first query is going to be five and this picture does a good job of kind of showing which cells we're allowed to visit okay next query over here six we do the same thing except it looks like we're able to visit a five and a five and a one by like doing the traversal uh and so that's like eight points that we would get and the last query is two so it looks like only the origin is visitable from there so we only get one point and then this would be the output as you can see over here so knowing that how do we go about solving the problem well there's a lot of ways to do it the first way that you might think of is just kind of a simple graph traversal because sort of these queries are somewhat independent of each other to some extent and they're not 100% independent and that's actually what the optimization is going to be these queries are not all independent do you notice that like if the values were increasing like for example like over here I have a grid with the value eight and over here I have a grid with the value five I mean I would never expect this grid to have or or rather I guess I would never expect this grid to have any cells that are filled in that we could collect points from that cannot be collected by a bigger number I hope that at least makes sense that's kind of the hint at the optimization uh before we even do the optimization on here since even though we're allowed to visit the same cell multiple times we would probably rather not do that so I think a simple traversal that we could do from here just going in every direction that we're allowed to is probably a BFS traversal since this is a hard problem you need to have a very good understanding of BFS if you don't feel very very comfortable implementing a BFS from scratch this problem might be too difficult for you and that's perfectly fine you can keep watching the video maybe you'll learn a few things but definitely try out some easier problems where you implement this algorithm okay but now how would that uh solve the problem well basically for each query we would run a independent BFS on the input array and so in the worst case like the size of the arrays or the grid is n by m so for each query the overall time complexity is going to be Q the number of queries n * m so this isn't really that bad but I guess for this problem it's not good enough so how can we try to optimize this well that's kind of what I was talking about a little bit earlier it would be nice to eliminate some of that repeated work right that's kind of why I mentioned that this is going to have everything that the other guy has except a little bit more like some of these cells over here so probably it' be nice to answer these queries in sorted order because then we eliminate some of that repeated work so that's the intuition behind doing this a bit more optimally okay so if we did sort the input suppose I sorted my queries to be something like this um let's preserve the original indexes though uh at least in the drawing and then I sort these queries and then I actually get 2 5 6 we know that when we fill in our result array down here that since we are going through the queries now in sorted order when I answer this query over here I can't put it in the first position I know that this two was actually at index 2 so when I do answer that query I have to put it over here five I'm going to have to put over there and six I'm going to have to put over there I'll show you how to handle this in uh the code it's not too difficult just having uh converting this into like an array of pairs where the index is one of the values in that pair and then sorting that list of pairs by the value is basically how to do it but anyways even knowing this how would we solve it such that we don't have a lot of repeated work well let's say I start with this query so I'm over here right now I visit the one and that is below my value so so far so good but now I'm stuck I can't really go anywhere so I say okay my current points is equal to one and then that's like the value that I would put in the output and now I'm going to go to the next value in my list which is five and I'm going to do the same thing I'm going to continue going through this grid I guess I'll uh make it a little bit bigger right now so I'm going to keep going through the grid now but it can't just be a traditional breath first search we can't do that actually because a traditional breath first search has a cue of values and so like right now we would have these two guys added to our que and then we'd kind of go through that Que in order so like that I'd go through these and then I'd go through these and these and sort of like that but that's not how we necessarily want to do this CU that doesn't take the actual values into account so instead we're actually going to be using a different kind of q a priority Q AKA in this case a minimum Heap so you could think of it as like the minimum Heap being initialized with just this value initially so like in the Heap I'm going to have a tuple with three values in it one is going to be the value in the grid so let's say Grid at that current row uh column and the next two are are going to be the row and column themselves and so initially the the Heap would have had the uh origin value which is one and 0 Zer we saw that that value was less than two so we popped it and then we would have added the neighbors of the grid so the neighbors would have been I won't be drawing the coordinates I'll just be drawing um the values in the Heap so right now we might have a two and a two because that's what these values are and I'm actually going to kind of color code which value did what so I'm going to use purple for the values that this five query answers so right now in our Heap we have two values and the minimum is two we can pop it it could either be this one or it could be this one and then we will take uh the neighbors of that and add them to the queue we would have popped the two and then we would have added the Neighbors which are three and five now and then we'd kind of just keep going we see okay there's another two that we can pop pop that two visit that two over here and continue going now we can add a couple more neighbors this one was already added so let's add this three to the que and since we don't want to revisit the same cell multiple times we will have a way to account for that like uh for example I didn't want to add this guy to the queue multiple times I will have a visit hash set that will allow me to do that which will allow me to prevent this so keep that in mind anyways just continuing uh through these right now we see these three are uh these three values over here so we continue we see that we can in fact pop three and we can pop both of them I'll just quickly do both of them at the same time so let's say I get this one and I get this one so I just keep going my number of points at this point should be five I think and these three values here should be in my Q right now so I'll add a second five in my Heap and I'll add a seven and it looks like at this point we can't go any further because our current query value is five and we can only visit cells that have a value less than five so we stop and we answer the current query and I can put a little five in the result array now okay almost done lastly I guess I'll use orange for the six we will look at our que is there anything we can get yes the minimum five is less than six so go ahead and visit that five and we can do one more we can visit that other five as well so I get rid of those from the Heap and I would have added a couple values one and actually I think seven was already added so we only add the one to the Heap and that can actually be popped as well so I pop it I visit the one over here I can't visit the seven it's too big so now we stop the points that we ended with was eight I can add that eight to the result and now I'm done so since the fact that we used a minimum Heap this might seem like it's a Dix's algorithm D algorithm but it's actually not it's very very similar but it's not quite dyra algorithm one of the differences is the fact that we're never adding the same value to the Heap multiple times where in Dy algorithm we actually do do that um but anyways the overall time complexity of this approach is a little bit annoying uh to analyze so one is going to be the fact that we sort the queries array so let's say q log Q is the time complexity of that plus traversing the array um I think that's going to be bounded by the Heap stuff that we're doing so the size of the grid is n * m those are all the values that could be pushed and popped uh to the minimum Heap and I think the operation for pushing and popping is going to be log n * m actually I guess that wasn't so bad to analyze so yeah it's actually pretty simple so let's go ahead and code this up now okay so I'm going to go ahead and reset this now and the code is going to involve a lot of like sort of pre-processing the first thing I'm going to do is just get the dimensions of the grid that's like the first thing I usually do then we know we're going to need to do a little bit of sorting so what I'm going to do is copy the queries array I'd rather not change that so I can do this I'm going to go through the index number in the queries I can do that like this in Python this is called list comprehension I'm going to have a pair I'm not just going to get the queries I'm actually going to convert this into a pair where I put the number First and the index second because then when I run q. sort this will sort it based on the number first next I'm I'm going to get ready for my traversal which is kind of a BFS with a minimum Heap similar to Dyas so I'm going to have my Heap here and it's going to have a tupal with the origin value and the coordinates like this next I can have my result I'm going to have it initialized with all zeros like this it's going to be the same size as the length of the queries array my number of points will initially be zero and then I'm going to start going query by query kind of like how I did in the drawing explanation I'm going to go unpack the two values in each query the limit and the index so that's what I'm calling the value because we know in the context of this traversal that's pretty much like the limit the max value and then um while the Min Heap is nonempty but even more importantly while the Top Value in the Min Heap so we can get the tupal like this and then from that tupal we want the value which is going to be at index zero while that is less than the limit so this is just saying that the smallest value that we have available to us is actually possible that we can visit it so then we do exactly that we visit it so I'm going to do Heap pop uh from the Min Heap I can unpack these values the value row and column and then I'm going to increment my number of points because now I was just able to visit a new value and now I'm going to go to my neighbors potentially and add them to the Min Heap so I can get the the neighbor coordinates like this this is kind of tedious but this is how I usually do it row minus one column and then over here we will update the column so row column + one and row column minus one then I'm going to go through the neighbor coordinates neighbor row neighbor column what I'd like to do here is say Okay Heap push this coordinate to the Min Heap this uh Tuple with the value of the neighbor row neighbor column and the coordinates of it as well and then I would like to be able to mark it as visited but remember we don't want to visit the same cell twice so let's guard this like this if a neighbor row neighbor column is not in visit but also that it's not out of bounds and we can do that like this in Python F0 is greater than or equal to the neighbor row but it's also less than the number of rows and that it's less than or equal to the number of columns and like this so I'll just fix the syntax here and then indent this but this should go through the four neighbors and just add them to the Heap and then maybe while the Heap is not empty and there are still values in there that are less than the limit we'll continue to process them when we're done processing all of them we will just say that in the result array don't append to it but for the specific index of the query over here we're going to set the number of points and then at the end we can go ahead and return the result so you can take a look at the entire code here like I said I don't think there's anything crazy going on here so this is a really solid problem just to kind of practice the fundamentals oh whoops I can't believe I forgot to initialize my visit hashset so okay sorry so let's do that now up here I'm going to create a visit hash set like this but also I'm going to mark this cell as visited because we see that in our code every time we push to the Heap which we're only doing once for each cell we're marking it as visited but we never mark the origin as visited so we can uh just pass that in initially I'll pass in a little Tuple uh with zero uh zero so now on the left you can see this code works it's pretty efficient if you found this helpful check out NE code. for a lot more thanks for watching and I'll see you soon