First Completely Painted Row or Column - Leetcode 2661 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem first completely painted row or column so I'm back in the lab and in this video we're actually going to be solving a pretty reasonable problem even though the last two daily leak codes were very very hard in my opinion this one is pretty reasonable for a medium problem I think now I could go through the description but I think it's easier just to start with the examples to be honest we are given two parameters here one is the Matrix so that's what you kind of see over here the first row in The Matrix is going to be 1 4 and then second row is going to be 2 3 and so the guarantee that we have is well first of all we're given a parameter which is an array and this isn't necessarily going to be equivalent to this one like the order of elements in here could be completely different than the order of elements here but the guarantee that is given is that the size of both of them is going to be equal so if the Matrix is M by n then we guarant that the array is going to have exactly M * n elements so the number of elements is going to be equal and the elements themselves are going to be equivalent in that this um The Matrix will have numbers in the range from one up until M * n in this case now in this case that's 2 * 2 so what we're saying is that it will have all the numbers between 1 and four present in The Matrix if all of those numbers are present well then we can guarantee that each is present only exactly a single time because that's how many slots we have I think this is like the pigeon hole principle and every element in the array is also going to be the same so it's also going to have numbers one through M byn I'll blow up the example even more just so we can really focus on the numbers so what this problem is asking us to do is relatively simple conceptually implementing it and making it efficient is not super difficult but that's kind of where the complexity of the problem comes because what we're doing here is this we're going to go through element by element from left to right in the array and then we want to be able to find that exact same element in the Matrix and then we want to color it and coloring it doesn't really mean anything you could say something else you could say we're marking this maybe we're marking it as visited or something else it doesn't matter but we color that element in The Matrix so we will have to do some kind of mapping we will have to figure out which position that element is actually at because it's not necessarily going to be the same as in the array even though right now the first element here is the first element here that's not always going to be the case with the second element it's three we already marked one now we Mark three so then we end up with something like this and then lastly we go to four we Mark that as well and then we end up with a matrix like this and at that that point we actually stop we can stop going through this array and we can then return the index of the last element that we visited which in this case we went through 1 3 and four which have indexes of 0 1 and two so the last element had an index of two so that's what we return now you're probably wondering why did we stop here why didn't we go through the entire um array and the answer is really simple we stop once an entire row or an entire column is fully painted so you can see that initially we had nothing painted and then we painted this guy so the row and the column is not fully painted next we paint this one and then so we have two painted this row is not uh the column and this column not fully painted same thing with the rows to very quickly go through this example first we will paint two that's this one then eight that's over here then seven over there a four this state and this column is fully painted so we can immediately stop and we can return I think here four was the last element which had an index of three so now we kind of know what we're trying to do how exactly would you do it if you even tried to go with a Brute Force approach you could probably get a working solution it just wouldn't be super efficient this is the most I think Brute Force way to implement it would be for every single element that we see here we would then find the position of that element in the Matrix and then we would mark it somehow maybe we would modify the Matrix that were given or maybe we would create our own Matrix and call it something else but it would have the same dimensions as this and then we would somehow mark it which that itself would be an O of n * m operation you'd have to scan through the whole Matrix potentially and then after each modification we might want to check has any row or has any column been fully filled and that's also not a super efficient operation and we're doing that for every element here so this would be like an n^2 M2 solution thankfully it's not super difficult to optimize this all we really need to do is think about that inefficient operation and how we can possibly optimize it I'll give you a hint a data structure is going to be useful I think in this problem you might be able to use uh an array but I think it's also fine to use a hashmap and that's what I'm specifically going to be doing well I guess there's going to be a couple things there's two main things that we need to speed up one is the lookup so from the array we want to find the element in the Matrix so we need to do the lookup efficiently the second thing is we need to be able to verify the Matrix we need to know immediately once a a column or row has been fully filled and both of these are actually not super difficult to accomplish we'll be using data structures for each of these so this one is I think relatively simple all you pretty much do is hashmap Jutsu just create a mapping for every single element in this array which we already know is equivalent to all the elements in this array except the positions are different so what we do is not Traverse the array all we really have to do is Traverse The Matrix this literally tells us where each element is we go through the first element okay well the coordinates of that are 0 0 the next element two is at 01 the X element 5 is at 02 and it just kind of keeps going from left to right and just keep going down so it's very easy to build the Matrix which will map an element to the coordinate so what I'm specifically going to be doing is for every a number n I'm going to map it to a pair the row coordinate pair and so I think this is easier to do with a hash map you might be able to do this with arrays as well one array or like two separate arrays but doesn't really matter too much how you do it you just need some way to map the number to its coordinates second is how can we know like when we went from here to this state how do we know that by coloring the four we were able to either get this entire row filled or the entire column field how could you know and how could you know efficiently possibly even in constant time well first things first we don't have to check every single row because we only add an an element here we added this element so how is it possible that we filled this row or how is it possible that we filled this column this row and this column weren't previously filled or we would have returned when we were here we didn't so all we need to do when we add this for is to verify this row and this column and you actually don't need to scan through the entire row or the entire column if you use a couple data structures I'm going to use a couple one is going to be called row count and the other is going to be called column count you could use a hashmap for each of these or you could use an array as well but either way what each of these is going to do is map a particular row so this is row zero Row one row two map a particular row to the number of filled cells in that specific row and we're going to do the same thing for every column as well so when we're here we find that this column had a fill of one and this row now has a fill of one as well before uh everything else was Zero eventually we get to here and we find that this column has two and this row has two and then eventually we get here and we find that this column has three and so we can return because three is equal to the total number of columns that we have but anyways if we can do these optimizations we can basically do both of these in constant time giving us a overall time complexity of M * n we will have to Traverse the entire Matrix I think a couple times but that's still this time complexity and space complexity I think with these data structures is also going to be M * N I think mainly because of this first hashmap anyways now let's code it up so I usually just like to start by getting like the dimensions of the Matrix and then put them in a couple variables and so the next thing I'm going to do is uh the Matrix to position so this is going to be the hash map I was talking about it's going to map a given number to the row column coordinates so I'm going to go through every uh Row in the rows every column as well and then simply I want to map the value at these coordinates so Matrix row column this value should be mapped to the coordinates row column and this should be the key in my hashmap so that's exactly what I'm going to do put the hashmap use this as the key so Step One is complete the First Data structure the second data structures are going to be filled as we go I'm going to call them row count it's going to be an array of all zeros right now same thing with column count so each of these is just going to store the count of every column and every row and so now we can start traversing we're not going to Traverse The Matrix we're going to Traverse the array like this I in range length of array because now we want to take elements from the array and then fill them in the Matrix and now it's easy to do that we are going to first get the coordinates that we want to fill so Matrix to position which value am I looking at currently I'm at index I in the array so I say array at whoops I really got to disable my caps lock but array at index I will give us the row column coordinates and then all we do is increment the number of filled rows or filled cells at this given row and same thing with the column and now if either of the following conditions are true we are going to return and what we're supposed to return is the index I so that's what I'll put down here so either the column count that we just updated has now reached the value that we wanted it to be which is columns tells us how many columns that we have but it doesn't tell us how many elements are in a given column that is actually determined by the number of rows so that's why the column count once it's equal to the number of rows we know that that column is fully filled or the opposite if the row count at this given row is equal to the total number of columns if either of these is true for these ones that we updated then we can return and we're guaranteed to return eventually so we don't need to put a return statement out here unless you're using like a I think statically typed language or something but let's go ahead and run this and I must have gotten lucky with the leite code Gods because I'm at like 97% but earlier I don't think I was anyways if you found this helpful check out n code. for a lot more thanks for watching and I'll see you soon