Sum of Square Numbers - Leetcode 633 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so to Let's solve the problem sum of square numbers this is actually a really good one and we're going to go through a few Solutions so the idea is that we're given some non- negative integer C and we want to satisfy this equation a 2 + b^ 2 is equal to C we want to find if there are two integers A and B that satisfy this now A and B don't have to be different they could be the same so for example if we had something like two 2 + 2^ 2 that's going to be equal to 8 so in other words given the parameter C which is 8 we do have two integers that satisfy this equation so we would return true in this case if we don't for something like nine I don't think there are going to be two integers that satisfy it so in that case we would return false so how do we solve this problem well the simplest is going to be with the Brute Force now how would you even try the Brute Force though like if you were going to try every combination of A and B to solve this problem what are going to be the constraints On A and B well at the very least if we're trying to build some non- negative integer C we can assume that A and B are definitely going to be greater than or equal to zero it could technically be equal to zero because a non- negative integer what if C is equal to zero well a and b^ squared are each going to be zero in that case they do satisfy that equation so A and B are allowed to be zero but they're never going to exceed the result C so I'm also going to put a less than or equal here because technically even in that example previously where C is equal to zero these two are going to be equal to zero so they could be equal to C but they're never going to be greater than C because if you had two numbers greater than C well the sum of those is probably also going to be greater than C so why would you need to check those numbers in our Brute Force solution this is going to work now the time complexity of like a nested Loop solution checking if Rec combination of A and B this way is going to be let's say c^ squ where C is obviously just C itself we can actually get this solution down to Big O of C you might be wondering how but it's actually very basic math we don't actually want to check that A and B are less than or equal to C we want to make sure that A sared and B squared each of those is less than or equal to C in other words if we take the square root of both we find that we just Want A and B to be less than or equal to the square root of c and the reason for that is if a was equal to the square root of c a s is literally equal to C and so obviously in that case a 2 + B squ is either going to be equal to C or it's going to be greater than C so at that point we know we can stop so this is a closer terminating condition for our loop with this inequality we get the time complexity of Big O of C but we can actually do even better than that consider this for a second we have an outer loop where a is going to iterate from zero up until the square root of C inclusive we'll have a nested Loop in The Brute Force for B in that exact same range right so this is like a square root of c and this is also square root of C so you multiply those together and you get the Big O time complexity of just a big O of C so how can we optimize this a little bit more well the idea is this we're going to be Computing we're going to be going through every number from 0 to theare < TK of c and then in here what we're going to check is something like this a * B+ B * B is equal to C this is like the equation we're going to check so in other words a is already sort of fixed right a is fixed and with this inner loop we're going to try every possible B and check if the equation is satisfied a better way to do this would be to go through this Loop move it somewhere outside so we can literally compute every single number from 0 to square < TK of c and get the square of it and throw all of those into something like a hash set and then once we've done that a single time then we can solve this equation here for B itself which is going to look something like this c - a^ 2 that's what B is going to be equal to and then we take the square root of this side and then that's what B is so in other words we're looking for this target number and if this number exists in our hash set which we can check very efficiently then we have the like solution we will know that we sa aside the equation if it doesn't exist then we know it it doesn't so then we can move to the next iteration of a we don't have to check every single possible B we just have to solve the equation and then check the hash set so this way actually we can get the time complexity of this just down to one Loop over here and replace this with a hash set and then the overall time complexity will actually be the square root of C now that is going to require some extra space so we're going to need to take every number from zero to the square root of C Square it and then add it to a hash set so the space complexity of this solution is going to be this I'm going to code this solution up for you right now you're going to realize there's actually just one problem with this solution so like I said the first thing I want to do is just get the square of every number from zero up until the square root of it we're going to go for I in range from zero and then we're going to take math I think I actually can just do square root of c and I'm going to add one to it because with python this is not inclusive necessarily so with this way we'll actually go up until the square root of c and we also just want to make sure we're dealing with integer so I'm actually going to wrap this in an INT conversion okay now we're ready so now now we're just going to take every single candidate I we're going to square it so I * I and then we're going to take that and add it to the square root set like this now we've computed all the squares from zero up until the square root of c and now we can do the loop solution more efficiently so I'm going to start with a here and for the looping this is actually the easiest way to write the loop instead of computing the square root of a and making sure that like square root of a is less than C we can actually just take the square of a a * a and check that that is less than or equal to C so it's the same inequality like if I were to square root this side we'd have a here and we'd have the square root of C it's just that it's a little bit easier and more precise to compute this without actually calling square root because then we get into like decimal territory so now we want B we want to know what B is and we're going to call that the target we can compute that by taking C B minus a * a and so this is actually not B this is b^ 2 and that's fine because that's what we want to check it does that exist in the hash set this is the number and we want to know if it's in the hash set like this square roots and if it is we can return true we're done at that point if it is not then we're going to check the next candidate for a so we're going to do a + one and then out here we're going to return false so now let's try this and and I had a typo so this should there should not be an S here I'm sorry that's square root not square roots okay and that solution actually does work last time I tried it it actually did not it gave me a memory limit exceeded error so the motivation I guess is still the same because it shows that we're pretty low on the memory for this solution and the idea is that we can actually Implement a solution with the same time complexity just more memory efficient let me show that to you now so the motivation for this solution is actually going to be Elite code 167 it's 2 sum2 and that is a very very good problem for two pointers it teaches you a lot and so that's what we're going to use for this problem just like how we kind of pre-computed all the squares from zero up until the square root of C we're going to do that once again actually so let's consider if C was 10 for example we're going to go through every number from zero up until the square root of C in this case the square root of C is something like 3 something something so we want to stop at three so we're going to compute the square root of every number from zero or not the square root the Square from 0 to three so we're going to have 0 squar we're going to have 1 squar we're going to have 2 squar and we're going to have 3 squar so that looks like an array of 0 1 4 and 9 think of this array as like x² if we can find two numbers in this array they could be the same number or they could be different numbers and if those two numbers sum up to the value C we have solved the problem so in other words this is literally the problem to sum 2 leak code 167 it's the exact same problem now so it's going to have the exact same solution which is a two-pointer solution this is pretty much what we were running the brute force on when we were trying every possible pair but there is an optimal solution to this which starts pointer on one side and the other pointer on the other side so now either these two numbers summed up together are going to be the target this time they're not so what should we do should we take this pointer and move it down here that would make the sum smaller cuz we're taking a nine and turning it into a four or should we take this pointer and move it to the right it would make the sum bigger it might make it too big who knows but it would move us closer to the Target so we're going to do that so that's the solution to this problem if our sum is too small we're going to take the left pointer and increase it it's going to be shifted over here and so now we have actually found the solution 1 + 9 is equal to 10 so there is a solution and we can return true it could have been possible though that our let's say our sum was actually equal to 11 our Target is equal to 11 so in that case this would have still been too small we would have tried to shift this pointer again and we would now be over here 4 + 9 now it's too big so we're going to try to make it smaller we're going to try to take this pointer and then shift it the other way now it's going to be too small and the pointers have met each other so we've exhausted every possibility the time complexity of this solution is also going to be square root of C cuz that's the length of this array and we're not actually going to have this array in memory so that is a very important point we're going to have the indexes of this array it's going to look something like this 0 1 2 3 we're going to have left pointer initially be zero we're going to have right pointer initi be three obviously we can take an index and compute the value the square of it very easily that's why we don't need this array in memory when we shift the pointer we're just either going to be incrementing the left pointer or decrementing the right pointer so this solution works if that's all you care about you can jump to the coding part but let me just briefly explain why it works a little bit of the intuition suppose this is our remaining set of elements it could have been possible that there were more elements over here and more elements on the other side but let's say this is our remaining set of elements we want to find the two elements that sum up to C well like we learned earlier if these two elements do not sum up to C obviously we want to increase the sum to get closer to C we know for sure that no matter where we move this right pointer whether we pick this one this one or this one no matter where we move it if we have this left element it's never going to sum up to C because this is the largest element we have from these pool of elements so obviously if 9 + 0 is not C then none of the other elements is going to be C so that tells us that we do not need to consider this element anymore so that's why we take this pointer and then shift it to the right we guaranteed we do not need that element now suppose this instead of being a one it was actually a two just to make this example more interesting we would try these two numbers 9 + 2 sum them together and they are actually larger than the target larger than C so at this point we know for sure there's never going to be an element that matches with nine because we just saw an element that was too small and now we found an element that was too big if an element actually existed it would have been in between those two numbers because as you kind of have noticed this array is sorted that's important that's the only reason we can run this two-pointer technique this array is sorted So since neither of those numbers summed up with nine we can rule about n as well so that's a little bit of the intuition of why this works it's kind of a proof by contradiction but I think we've spent enough time on this that now let's code it up so I'm going to have two pointers left and right left is going to be at zero right is going to be at the square root of C so we're going to take the square root of it and we're going to convert it into an integer so that will round it down if it is not an integer so now let's check while left has not met or crossed the right pointer or rather like they haven't crossed each other because if they've met we can continue then we want to know does left squared plus right squared equal the Target that we're looking for so I'm going to set this equal to total and I'm going to check if the total is greater than C else if the total is less than C else the total is equal to C that's when we return true otherwise we can return false outside of the loop now here if the total is too big then we want to make the total smaller we can take our right pointer and shift it the other way because the right pointer has the maximal element so if we shift it to the left we are decreasing that and here we can take the left pointer and actually increment that so that we can make our sum a little bit bigger so that's the general idea let's run this now and as you can see it's definitely the most optimal and space efficient solution if you found this helpful check out NE code. iio thanks for watching and I'll see you soon