Count Total Number of Colored Cells - Leetcode 2579 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem count total number of colored cells very interesting problem today it's actually going to involve a little bit of math and don't worry I'm not going to like try to bust your balls or anything I know a lot of you don't like math but hopefully by the end of this video you'll realize or at least remind yourself that math isn't a bunch of numbers and equations it's actually a way of thinking so anyways idea behind this problem is pretty simple um we're just given a parameter n it's going to be a positive number between 1 through like 10 ^ of 5 so depending on what it is we want to return the total number of cells in this grid so n equals 1 is kind of the base case we have like one little square I guess I'll use this picture here on the left we have that little square and then for Nal 2 what we do is for the original Square everywhere on the perimeter of it we add another Square so we add one square to the top top to the bottom to the right and to the left and you see after we've done that this is the new uh shape that we have so this is Nal 2 and to this once again we're going to do the same thing add a square everywhere on the perimeter that we can so we can do one here do one here right side left side and then also here here here and here so that's eight new squares we could add and then we end up with this guy so this is n = 3 so in terms of the total number of squares we had one here we had five here then we had 13 here so what we want to do is given some number n some arbitrary number n it could be bigger than three we want to get the total number of cells that it will have if you haven't noticed a pattern just yet let me kind of do one more cycle so here once again we can add a square to the left to the right to the bottom to the top and obviously it's getting kind of messy and now we can add uh like four squares like this and four squares like that so to this guy it had 13 cells we added 12 cells to it and now we'll have a shape with 25 cells so I don't know about you guys but this kind of reminds me of like those little math problems or like those pattern problems from when I was like in elementary school try to predict how many uh squares the next shape is going to have I think I've seen this on like IQ tests and things like that do you notice the pattern it's some very basic math well it's not like super super trivial but I think if you're looking for it you can figure it out um from here we do a plus4 to get to five so like 1 + 4 that gives us five and then to get to 13 we added eight squares to that so 8 and then to get to 25 we added 12 and so this pattern is going to hold to generalize this formula it's going to look like this 1 + 4 * 1 + 4 * 2 + 4 * 3 etc etc so knowing that we can code up a solution basically we can start our result at one that's kind of like the starting point you could think of it as like well I guess you can't really think of it as 4 * 0 because it's a one so that's kind of like it is a little bit different than the rest of these but anyways and then like however many terms we're going to have here is going to be decided by n so we'll have uh this is like the first term so these will be the N minus one next terms so now let's use this idea to code this up that's going to be the linear time solution but there actually is a math formula we can use using this logic to solve this problem in constant time I'll show you that right after I code up this one all right so what I'm going to do is initialize my result to one I want to do is return the result and so there's multiple ways to code this up I will code this up by iterating n times and I'm going to do this for I in range n so what i is going to do is going to be every value from zero up until n minus1 so what I want to do is add to it multiples of four so I'm going to add to this 4 * I so what that's going to do is let's say n is equal to 1 this Loop is going to run a single time it's going to add four time0 to this so nothing's going to happen it's just going to return one okay well what if n was two then this is going to iterate from 0o to one on the first iteration nothing's going to happen on the second iteration 4 * 1 is going to be added to the result and if it were greater than that it would take 4 * 2 4 * 3 4 * 4 etc etc it's just going to keep going it'll stop the way python works this will last execute on nus I will be n minus1 so I'm just going to run this now you can see here it works it is a linear time solution but there is basically like a0 millisecond Solution that's just a math formula let me show you that one now so pay very close attention to what's going on over here and I guess before I even get into it this whole solution is going to rely on a very sort of simple formula called gauss's formula I guess I can show you what that formula is now now and then maybe after I show it to you you'll actually know how to solve the problem or at least you'll be able to do the math on your own but anyways gauss's formula is this it's like you take a series of numbers it doesn't always have to start at one but the simple case is when it does start at one you take a series of contiguous numbers that you're trying to sum together so we have like a simple series like this uh one through four and like if I told you to sum every number from one through 100 you'd probably run a Loop in your mind to do 1 + 2 plus 3 plus 4 all the way up until 100 but there's actually a very easy way to do that I can tell you off the top of my head I think the answer is like 5,50 and let me show you the equation to do that and then I'll show you how you can derive it or how to think about it intuitively for 1 through 100 to sum all these numbers what we would do is take And1 multiply it by 100 / 2 which is just 50 and so if you do that I do believe the answer is going to be something like 550 now how did I derive this formula am I a genius no I'm not gaus but I don't think you have to be a genius to derive this one because think about this for a second to take these numbers I know that 1 + 100 is going to be 101 I have one pair that is equal to 101 but actually I have 50 pairs that are equal to 101 that's the shortcut because consider this that was one pair now I can also do 2 + 99 it's like I'm doing a two-p pointer algorithm in my head almost think about it like that like I have a pointer over here and a pointer over here this is one pair that sums to 101 now I shift the two pointers Inward and I have another pair that sums up to 101 because I took this number I increased it by one I took this number I decreased it by one and so now I have another pair of 101 How many pairs am I going to have total well I had a total set of 100 numbers so I take that total set and I divide it by two that's what I did over here so the general formula in this case if we're starting at 1 going up until 100 you could say it's going to be n + 1 where n is 100 multiplied by n / two in this case so like even though like gaus he didn't know anything about writing programs he didn't know anything about a computer I think he was alive in like the 1800s he knew a way of thinking that was quite similar to how programmers think don't you agree that's why I think math is very beautiful but anyway so now how does this apply to this original formula that we have over here well in this case like this example I think n was equal to four so we had like four terms here you see that what's going on like ignoring the first term then we have one 2 and three and each of those is being multiplied by four so you could kind of look at this part of the formula like this down here so in other words like this inner part this can be calculated by just taking like our current term n and uh subtracting one from it so if I did nus 1 the reason for that is because like these inner terms are going to stop before we actually reach n which is four so this is how many many terms we're going to have like inside of here we can divide that by two which is going to tell us how many pairs we're going to have and then we can multiply that by what is the value of an individual pair going to be like you take this and you add these together and it's four that's not really a coincidence because we would always take the largest number that we have which is going to be n minus one add one to it and that's going to tell us what one pair is going to equal so n is going to be the value of a pair it's going to be the sum of a pair This Is How many pairs we're going to have you divide that by two and then you get this formula and we see that that only tells us what's inside of these parentheses you take that whole thing and you multiply it by this four that we had out here and you also take the one and you add it to that and this is the general solution that you get you might think well how do you know this is actually going to work because inside of here we have an odd number of terms actually that's fine as well because the like middle term if there is a middle term if there's an odd number of terms there's guaranteed to be a middle term the middle term is always going to be half of the sum of the pairs so the pair sum was four the middle term is two so it is half of the pair so that's why if this were to be an odd number if that were to be like 1.5 it still works out I'll run the formula in front of you right now to prove it let's use a different color so I have 1 + 4 * n which is 4 - 1 / 2 * 4 and there's a lot of simplification we can do here so I think this is going to be 12 / 2 that's 6 * 4 that's 24 plus the 1 and yeah we get 25 isn't that the number that we had originally yes it is like if you take all these up add them together you are going to get 25 it's not magic it's math now if you want to simplify this function further which you really don't need to to solve this problem in constant time you can I think you can simplif by it slightly more to be 1 + 2 * n -1 * N I guess that's fine as well but either way like either of these you use the time complexity will be the same let's code it up so there's not really much to watch at this point I already told you what the formula is but in case you want to keep watching go ahead uh 1 + 4 um multiplied by n * nus1 and I think we can divide either of these terms by two it doesn't really matter which one of these is going to run first whoops let's make that a two so I think this will work yes it does here on the left you can see and then we can also get rid of this divided by two and then turn this into a two just canceling out one of those factors and then that'll also work yep as you can see here it works pretty efficient I really had a lot of fun with this video I hope you did too thanks for watching I'll see you soon