Magic Squares In Grid - Leetcode 840 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem magic squares in grids so with this problem there's the good news and the bad news so I'll start with the good news and that's the simple sort of Brute Force solution to this problem actually is the most optimal so that's the good thing at least in terms of Big O complexity now the bad news is that there's a second solution which is in terms of Big O just as efficient I mean it is technically more efficient in just like the raw number of operations that it uses but the bad news is that it involves quite a lot of math now I can explain it to you that's the easy part but coming up with it by yourself is the hard part I did not come up with it by myself even if somebody were to come up with it by themselves the proof is very very tedious and long to really reason about you might have the intuition I think the intuition is somewhat reasonable but really like proving it is sort of tedious I will kind of go through that though let's start with the first solution so the idea is we're given a grid which could contain numbers from 1 through 15 now immediately they tell us that we're looking only for 3x3 squares in the grid so this particular input only has two different 3x3 squares this one and this one and those are kind of shown here on the right so we want to know which one of these are magic squares the definition of that is that the grid will only contain numbers 1 through through 9 and it has to contain numbers 1 through 9 so there's no duplicates allowed and it can't be missing any of those numbers so so far both of these do satisfy that constraint but the other constraints are that every Row in each Matrix and every column and as well as both of the diagonals there's only going to be two diagonals with a 3X3 Matrix or just any kind of square Matrix all of those have to have a total sum of 15 okay in this first one you can see this is 15 this is 15 this is 15 the diagonals are also 15 both of them and then the columns are all also 15 now this second one over here does not satisfy that the row row and row are 15 this column is 15 this column is 15 and this column is 15 as well but when you get to the diagonals this one is clearly not 15 this one is not either Brute Force pretty simple just go through every single 3x3 Square in the given Matrix how do we do that though well my thought process is consider every position as the top left corner so here is the top left corner of our 3x3 like suppose it's over here so this would be this 3x3 we'd consider this one also and we probably don't need to consider anything below that because there aren't even three squares in that column so in terms of the logic of that we could do it with nested for Loops let's say for R in the number of rows for column in the number of columns but we're not going to go through all the rows we're going to go up until the total number of rows minus 2 because that will ensure that there's at least two rows below us for every starting row same thing with columns we're going to go up until column minus 2 that ensures that there's going to be at least two columns to the right of our starting point so at that point it just becomes kind of a game of coding it up and that's going to involve for a 3X3 grid just checking that every single number is distinct how do we do that probably a hash set and check that every single number is in the range 1- N9 so if this is true and they're distinct then we know that we have all the numbers 1 through n in the grid so that's the first thing to check and then it becomes just calculating all the sums there's going to be 1 2 3 4 5 6 let me get rid of this S8 different sums that we have to calculate all of them have to sum up to 15 we know that there is a possible solution at least one so we are going to have to sort of Brute Force this and this solution will work and the time complexity believe it or not is going to be roughly in terms of Big O the dimensions of the Matrix let's say the number of rows times the number of columns even though we're going to be doing a bunch of operations on each 3x3 grid and some of them are going to be overlapping the total number of operations is still going to be constant it's not going to be nine cuz we're calculating several different sums and like iterating over the input even if it was 100 operations per 3x3 Square the total number of 3x3 squares is not going to be larger than the total number of positions in the entire grid so that's where I'm getting the time complexity so let's say you you know multiply this by 100 it doesn't change the overall time complexity and we're not going to need any extra memory even though I mentioned we're using a hash set well the hash set isn't going to be greater than the length of nine cuz that's how many values are in each 3x3 so this is the Brute Force we can code it up and the space complexity will be constant let's do that so I would start by just getting the dimensions of the Matrix and I'll initialize our result which is just counting the number of magic squares and that's what we're going to return so now I'm going to go through every possible starting position like I said for R in range total number of rows minus 2 we're considering that as the top left corner we want to make sure that we have enough rows below it same thing with the column number of columns minus 2 now we could put the logic for determining if this is going to be a magic square directly here there's nothing wrong with that but like we're going to go through four steps we're going to ensure that everything is 1 through 9 we're going to then validate the rows and then we're going to validate The Columns and then we're going to do the diagonals if at any point like here for example we determine it's not valid then we want to break out of this Loop pretty much it's easier to execute a return statement because from here like we might be running a loop to detect all the columns or rows and summing them up so that's something I actually realized as I was coding this up here I guess I can even do it here and then show you why we're going to be using a function for it first we want to go through the 3X3 Square starting at row and column that's the top left position so let's say for I in range from row up until row plus three the reason I'm doing row plus three is because the last one will be non-inclusive so we're going to go from row to row plus one to row plus two and not include the last one we're going to do the same thing for the column let's say for J in range column up until column + three and we want to track the duplicat so let's have a set I'll call it values and then here we're going to check if the value at grid i j is in values then we want to break but how do we do that right like how do we break out of this nested Loop like we've already detected that this is not the case so we want to break out of this nested Loop and then stop this one so that's why it's better to just have a return here that's why I'm going to put all of this in a helper function and so just because it kind of makes things more readable anyway so here let's have a helper function I'm going to call it magic it will determine if this is Magic or not and it'll be given the top left coordinates so I'll paste all that there and so here we could return true or false so let's see how we're going to actually call this magic function we could do a true or false right we could say if magic then increment the result or it's easier in my opinion to do it sort of the C programming way where we just actually return integers from that function to indicate if it was true or false so adding to this we will get the return value of magic if it's one therefore it was true so we increment the result if it was Zero we don't do anything with the result adding zero to it is not going to change it so here I'll return zero cuz this was a not magic square so that's not the only way it'll be a not magic square what if we have a value that is not within 1 through n that actually is possible with the inputs that we have so let's check that if that or not just to make this clean I'm going to do one inequality like this if the value at the position in the grid is not in the range 1 through N9 inclusive not this inequality then we also return zero so this just checks that everything is within 1- N9 we could have had two different conditions for that but I just wanted to keep it short so here at the end if we didn't return we'll go ahead and add the value to our hash set so do add this uh value now for validating the rows we could hardcode it cuz it's only three rows anyway but it's slightly more extensible like what if we had a 4x4 grid this code that I'm about to write is going to be a little bit more extensible than if we just had a 3X3 so for here I'll say for I for every row we want to sum it up for I in range row to row plus 2 so the first three rows we're going to get the sum of them and that's not super difficult to do because that'll just be a subarray so at this row we want to get the first three values in that that row starting from the column so column all the way up until column plus it should be plus three cuz the last one is non-inclusive and actually I think this should be plus three as well for the same reasons as that but this we can get the sum of it and then we can check that the sum has to be 15 if it's not 15 once again we can return early we can return zero now we'll do the same thing for the columns so for every column let's say for I in range column up until column + three we can't like use the sum function for that I mean we could but we can't use like a array slice because you can't really get a subarray from a column the way like a matrix works so we will individually sum the values up it's not that difficult to do so get the first value in this column so at row at this column and get the second value in this column so that'll be Grid at row + one where I stays the same and the third value Grid at row + 2 where I stays the same so if this is not equal to 15 then again we can return early so let's just add the condition here now the last part is the diagonals I mean the easiest way to do it is just to hardcode it so I guess this part is the least extensible and I guess this part wasn't super extensible either here I'm just going to take the three values in the diagonal let's say starting from the top left we'll have this value and then going to the middle we'll have this value row + one column + one and then the the bottom right value which is going to be Grid at row + 2 and column + 2 so if this is not equal to 15 or I'm just going to copy this so we don't have to type it all out again or starting from the top right so this would be a row row would stay the same and then column would be plus two and then going to the middle that's going to stay the same and then going bottom left so row plus two and I think the column would just be the same as the original so if either of those is not 15 here we would will return zero as well now if none of these execute then all the way down here within the function we can return one therefore it was magic let's zoom out a bit so we can see everything so this is the helper function doing most of the work and then down here is where we're actually calling that helper function so this part is pretty straightforward let's give this a run hopefully we don't have any typos or index like edge cases that we're missing and it does look like it worked for the record the first time I ran this it was a lot more so again don't pay attention to these run times and memories now for the mathematical solution to this problem which honestly isn't even going to save us that much code I guess it will save us a decent amount but it's just so difficult to come up with so if we were to quickly just mathematically get all the equations with given the numbers 1 through n all the equations where the sums of the three numbers will be 15 cuz either we're getting like the rows the columns or the diagonals this is roughly what it would look like suppose we start at one like we want to get all combinations with one well then we're trying to look for two numbers that sum up to 14 well there's a lot of ways to do that isn't there like well we could get 1 and 13 obviously that's not going to work we can't include the same number twice and also we don't have 13 available so let's start with the biggest number we have available it's nine okay what plus 9 is going to be 14 well five okay so that's one way what's another way well let's try eight okay eight plus what six is going to be 14 let's try again um seven what plus seven well it's going to be seven so that's not going to work okay well now let's try six and we're going to get the duplicate 8 + 6 and now let's try five again we're going to get the duplicate if you try to go any lower than that four you'll need a number 10 and obviously if we make this smaller then this number is only going to get bigger so we have something like 1 + 5 + 9 also 1 + 4 + 8 so I won't kind of go through all the math to generate these but if you really wanted to brute force it you could do like a decision tree and there's a bunch of different ways to do this but the equations would look like this and I'm kind of just taking this from the leak code editorial now you don't have to like read through all of these that's not really important but let's start to try to notice some patterns from this we had that 3x3 squar so the special element is going to be the middle element because from here we're going to need one sum that gets 15 2 3 and four so this one is going to be part of four equations that sum up to 15 so the question is which number is present four times in these equations there's only a single one it is five as you can see 1 2 3 4 so what this tells us is this pretty much proves that given this set of numbers only five can be the middle element if we want to have a magic square so that's the first thing I'll put five right there now the rest of these might seem symmetrical at first but the difference is between the corner positions and the non- corner positions because a corner position as you can see is going to show up in one 2 three sums whereas like these each of these is only going to show up in two different sums each so you know all those now we ask ourselves are there four numbers that show up three times in three different equations and there has to be because we know that there's at least one solution to this problem and so that is in this case the even numbers whoops I just realized that I had a mistake in this I'm really really sorry about that I do not know how this turned out to be a four that should have been a six this whole time so I'm really sorry hopefully you caught that or hopefully it wasn't too confusing for you anyways four shows up three times so two shows up three times four shows up three times I believe eight shows up three times and the last even number I think is six so six shows up one 2 three times so the even numbers are the ones that show up three times theoretically each of these has four different choices so I don't know how to like indicate that I guess I'll just put 4 C I guess in each of these positions so there's four different choices for that and so then we're left with the numbers that only show up twice and those are going to be the odd numbers not including five so if you think of it from 1 through 9 there were nine numbers five was in the middle so we're left with eight numbers and we took half of those and put them in the corners and now we're left with the four odd numbers one shows up twice seven shows up twice and the rest of them which I won't show nine and three those ones have to be here so this also has four choices this also has four choices and same with all of them now at first you might just try to do the raw math from here like if you have four choices here that's going to be four and then you'll have three choices here and then two choices left so you might try to do the raw math like this but keep in mind that the sums still have to be 15 we kind of forgot about that constraint so when you think of it in terms of that and you remember that let's say in the even case we have choices 2 4 6 8 yes you technically have four choices for this spot but if you do that you have to ensure that the value that goes here is the value that complements the other one so if we put two over here we would have to put eight over there so we kind of don't have a choice for that guy and when you get rid of those two then we only have have two choices left for this so we have 4 * 2 choices that's eight choices and okay after you have filled in the diagonal suppose we put two over here eight over here and then four over here and six over here after you've done that the rest of the values you don't really have a choice actually cuz remember this row has to be 15 so far we've only accounted for the diagonals that they are 15 so if this row has to be 15 there's only one value that would make it that and that's seven we don't have a choice there if we put seven over here the value that goes over here has to be I think three for this and this and then again you don't really have a choice over here either it has to be the number that sums with two and four that's going to be nine and then over here it's going to be one basically I'm saying that there's only going to be eight different ways that we can create squares there's only eight possible magic squares that exist even this doesn't actually let you get to the optimal solution so I'll give you a tiny bit of intuition that will let me redraw this for a second we know that the middle value has to be five now I'm going to prove to you that that sequence of values outside of five so let's say we have two and let's say we kind of do a spiral Matrix thing like we go in this order we go in a spiral around all the values that sequence is going to be 27618 349 I'm going to prove to you that every possible sequence that goes around five has to be in that order and it can possibly be rotated what that means is let's say I just write it out 7 so this is the sequence and we can potentially rotate it meaning like we could have started here and then this part would come at the end the easiest way to do that is actually just to take this and create a copy of it and so then we'll say that any uh sub portion of this that is of length 8 technically counts and the intuition for that is basically we know that this is valid this is one valid solution and it's also true that if I took this thing and rotated it 90° and I know the numbers you know you can't really read them anymore but this is technically also valid because we didn't really change anything all we did is we took something that was a column and now it's a row so the sum should still be 15 the diagonals did not change they're still 15 this is 15 this is 15 this is 15 so this is a second solution now I'm going to find the third solution we know there's only eight Solutions total this is the third one and this is the fourth one and now you might be wondering well what about the other four well just take this Matrix flip it and again I know you can't really see the values anymore but trust that the sums of the columns and rows are still 15 the diagonals did not change they're still 15 and now you can take this and then rotate it three times so this is the fifth solution sixth seventh and eighth solution so we did a lot of you know crazy stuff here but those are the eight Solutions and since all we did was we rotated this and potentially flipped it it we know that all the spirals on the outside of it are going to be in this or in the reverse of this so if you were to take this thing and reverse it that would be the case where we flipped the Matrix cuz that will change the order of the outside so very very complicated very very mathematical but knowing all of this we can shorten the code and I'll show you that now okay I don't want to spend too much time going over this cuz this is pretty similar to the previous solution the main thing here is that we have this pattern string so that's going to be well the order of this is different from what I showed but it's pretty much still a rotation so I took like the first half and then I copied it to the second half and you actually don't need the last character um I won't go into details of why you don't but you don't and same thing on the second one this is just kind of a reversal of the other and we have the logic down here is pretty much the same except now we're not going through top left positions we're only going through the middle position so row column are going to be the middle so when we call our magic helper first we're going to check the middle position has has to be five if it's not we return and then we go through all the neighbors of that middle position we go to the top neighbor the top right neighbor uh the right neighbor the bottom right neighbor and all the other neighbors as well they kind of go in clockwise Direction so then we iterate over all the neighbors we take the value convert it to a string and then concatenate it to our sequence string and then we check is the sequence either in pattern one or pattern two if it is we return one otherwise we return zero so I would call it a magic solution but it's not magic it's just math so let's run this and as you can see it works and it is technically more efficient but not in terms of Big O complexity if you found this helpful check out n code. for a lot more thanks for watching and I'll see you soon