Flip Columns For Maximum Number of Equal Rows - Leetcode 1072 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem flip columns for maximum number of equal rows so this one is a fun one it actually took me a few minutes to figure out the main thing I'll show you the notes that I took when I was coding this one up I don't think they'll be helpful for you but I'll try to explain the thought process in a more intuitive way the idea is we're given a binary Matrix here zeros and ones we are allowed to take any column and invert it so this could be transformed into 1 1 and if you do that you look at the resulting Matrix just trying to make this clean you see okay this row has 0 01 this row has three zeros this row has three ones so both of these rows have the same value in every spot they're not the same like this is 11 one this is 0 0 0 but the row itself is all the same this row is all the same what we're trying to do is maximize the number of these rows so this is the best we can do we can get a matrix with two rows that are all equal naively you might think well I guess we could try every possible way for this column we could choose to either invert it or not invert it and so then you have two choices here two choices here and two choices here so it's going to be something like 2 the^ of n let's say we have n different columns that's not even checking like how many rows are equal in every spot that's going to itself be an M * n operation as well so that's probably not what the solution is I don't remember off the top of my head what the constraints are but I think they're over 100 I think M and N could be greater than or equal to 100 so yeah that's probably not going to be efficient so what's the observation here and it took me a while to kind of figure it out I went down some thoughts that weren't super useful but some of them kind of were so for example this Matrix is pretty much equivalent to if I just inverted the entire thing so basically taking every single column and flipping it it wouldn't do anything you'd produce a matrix that looks like this and so however many equal values you have in a row that we started with wouldn't have changed in the resulting Matrix now that doesn't necessarily solve the problem for you but still it's an observation that I made and then I just kind of kept going for observations it seems like there might be a trick here it seems that they're asking us we can flip the call colums but that doesn't mean we actually have to flip the columns maybe there's a pattern and that will allow us to count the number of maximal rows that we can make that are all equal and we can just do it that way we don't actually want to have to flip these columns cuz that's going to be pretty expensive then we're going to have to read through the entire Matrix and verify it so what's the pattern I mean I guess if you start with a matrix like this and now I'm going to kind of take the problem and simplify it rather than considering a matrix I'm going to just look at two rows at a time I want to kind of make things easier for myself I have a monkey brain I guess all of us do we're not designed to be able to just look at something and immediately know the answer to it we kind of have to do things in a more intuitive way so I'm looking at two rows at a time if they're both equal then that's good even if they uh look like this they're both the exact same even if all the values aren't the same I can just then flip this column and then make them all equal and even if they were inverted even if this column was inverted I can still make these uh the same well they're already the same but this is fine basically they don't have to necessarily be exactly equal and then you realize that this example here pretty much helps you solve the problem it's the third example that they gave us actually so I think they did us a favor I think sometimes that's expected for a medium problem they gave us an example that pretty much lets you solve the problem because you see that the reason we were able to make these two rows equivalent even though they're not equal we don't have a 11 one 0 and a 1 1 0 but the two rows are inverted so we have a 0 0 1 and then a 1 1 0 yes we can't make both of these rows exactly the same by flipping columns but we can make each row have the same values so we can flip this column and make it zero and then this one will be a one that's the pattern so just looking at two rows at a time we know immediately if these two rows can be made equal either they're already like equivalent to each other or one of them is the inverse of the other row so once you realize that you realize that you can pretty much just take each uh row convert it into some kind of key with that key mapping we can count the occurrences of that type of Row the only thing is we want both of these rows to have the exact same key first of all how exactly are we going to make a key for a given row my initial thought was maybe if the constraints allow it we can represent each row with a 32bit integer that'd be kind of nice just use a little bit of bit manipulation to do that but the constraints don't allow that I think the row could be greater than or equal to 100 something like that so we can't use an integer and so then my thought was to in Python at least I could just use a tuple because we can then convert this list into a tupal and in Python you can use a tupal as a key in a hashmap and then I was kind of scratching my head because I feel like some languages might not make this as easy as python does so I was wondering how other languages were supposed to do it and so I wasn't able to realize that we could just convert each of the rows into a string if we wanted to so if you weren't able to figure out like the trick to this problem that's okay because I for a moment today forgot that strings even existed so I guess we all kind of have those mental lapses once in a while okay so I think the last thing though is okay like I could turn this into a tupal or a string whatever I could get a key I could take this row and convert it into a key for a hash map but how do I make these two equivalent well the first idea I had was if I take this Row for example I flip it and I check this row as well and I check if this or maybe this has already been inserted into the hashmap I would just use whichever one is already inserted if neither of them are inserted then I could just use either of them it doesn't matter but there actually is a better way we know that for every single Row one of the representations of that row is going to start with a one and one of them is going to start with a zero it has to because the other row is literally the inverted version of the other one so you could kind of just go by that for example we could favor rows that start with a zero so just to summarize everything this is what we're going to do I'm going to look at this first row I'm going to convert it into a tupal or a string or whatever and I'm going to see okay the first value starts with a zero so that's fine I'm going to use this as the key in my hashmap down here I'm going to have 0 0 0 and I'm going to have the count of it be one I'm going to get the second row it's 0 01 it also starts with a zero that's good this key has not already been inserted into the hashmap now I do 0 01 the count of it is going to be one now I have my third row it starts with a one so I'm going to flip it it's going to turn into 0 0 one that key already exists in the hashmap so now I'm going to increment it and set it equal to a two now we're done with the counting so now you tell me what should we return the question is asking the maximum number of rows that can be made equal so we'll return the maximum of all of these values it happens to be two right now so that's what we return this algorithm will work on much larger matrices as well it's all about the trick I guess in this problem it's not something that'll just magically come to you by staring at a matrix you have to try examples you have to try to make observations and you have to ask the question I think if I had just asked you the question how do you know if two rows can be made the same that's a pretty good hint I think using that kind of hint a lot of people would be able to make the observation if two rows are already equal obviously that's one case is there any other case well if the two rows are inverted and that's pretty much what the third example in this problem tells you this is like the comments and this is the first solution that I had it may or may not be helpful for you but let's just start over so we know we're going to have a hash map I'm going to call it count and I'm not just going to use a regular hashmap in Python I'm going to use something called a default dictionary where the default value vales int because then we'll never get like a key out of bounds error so we could always do something like this even if the key doesn't exist we could increment it it'll get a default value of zero because we passed int here if this is unfamiliar for you you can consider checking out my python for coding interviews course it has a bunch of exercises for you to learn all these tips and tricks uh but now we're just going to go row by Row for every Row in The Matrix and I'm going to convert the row into a two and I'm just going to pass that row into the tual function and I'm going to call it the row key and so what I want to do then is say this the count of that row key is going to be incremented by one and then after I'm done with everything down here I'm just going to take all the values in my hashmap and get the max of them and then return that the only problem is that inverted rows can also be made the same so I think most people would be able to code something like this up even if you weren't able to make observation I did we at the very least know that two rows with the same representation can be made equal but the last thing here is just to add an if statement so we're going to say if the row uh the first value in that row is one we're going to flip the row so in Python it's pretty easy to do that with something called list comprehension so I'm going to say for every value in the row for n in row if it's one then I'm going to set it to be uh zero so if n is one you could make it more explicit like this but python doesn't require that um otherwise if it's zero I'm going to turn it into a one so now I have a list but we can't use a list as the key of A hashmap so I'm going to turn this into a tupal I don't believe python has tupal comprehension otherwise I would have just done that but you do have to kind of make a list and then convert it back into a tubal and so then I'll reassign this to be the row key and then this will work let me just quickly prove it to you so you can see here that this works it's pretty efficient I could have also used the string representation of every row but I think that would require more code I could be wrong maybe I can actually just do this string and then this I don't know if that'd be more efficient though because I think a tupal might be but I could be wrong let's just run it and see um so after running it it does work and it looks like this one is less efficient I'm just going by that small sample size I mean who knows if I run this again it might be 99% but I don't think this really matters you could probably do either if you found this F check out NE code IO for a lot more the time complexity of this approach as you can kind of tell is n * m I guess theoretically hashing a row no I guess we're going for n like let's say we have n rows that's the outer loop this inner loop the fact that we're converting a row into a string and then this as well and then this as well all of those are let's say an M time operation so I think this is big o n * m thanks for watching and I'll see you soon