Two-Sum Problem - Swift Tutorial - iOS Interview Coding Challenge

what's up guys we're back with another video in my iOS interview question series it's focusing on coding challenges today's challenge is going to be what's known as the twosome problem now the premise of this problem is that you have an array of numbers and you need to find out if there's two numbers in that array that add up to a certain sum for example if my son is 21 you need to return a boolean whether there's two numbers in this array that equal 21 sounds like a simple problem right but the beauty of the to sum problem is that there are multiple ways to solve it all with varying degrees of efficiency and that's where the tricky part comes in finding the most efficient solution for this fairly simple problem I'm gonna walk you through and explain each of those solutions in Swift all right let's go all right so let's restate the problem real quick here on line four we want to return a boolean value if there are two numbers in the array that equal a sum and then here on line five I have my numbers array which is some random sorted numbers and as you can see here there was gonna be three different ways we're gonna solve this problem but we're gonna start with brute-force here on line nine now if you've never heard the term brute-force before that's usually the most basic solution however it's almost never the most efficient solution it's usually a bad solution but it is a solution so we always try to find that first and then improve upon it with future solutions so what we're gonna do is we're just going to compare each number to every other number so for example we're gonna use a nested for loop we're gonna compare one two three and see if that equals our sum and then 1 2 6 and then 1 2 7 and then 1 2 7 and then once we've gone through comparing 1 2 everything we're gonna go to 3 and compare 3 to everything and then go to 6 compare 6 to everything I'm going to keep going and as you can see that takes a very long time and like I said that's probably not the most efficient elegant way to solve this problem however when solving these interview problems is highly recommended to find the brute force solution first that way you get at least a solution and then improve upon it later so let's build our brute force solution so our function signature is gonna be func it's call it brute force to some and it's gonna take in an array which is going to be an array of int and then it's also going to take in the sum which is again the value we're gonna be looking for and it's going to return a bool and let's go and just put that return in there so echo doesn't yell at us I'll just do it false for now and let's go ahead and call the function here real quick so it's gonna take in numbers and then sum just a 23 to start okay so that's just our basic function set up and like I mentioned it's just going to be a nested for loop and what a nested for loop is is basically a for loop inside a for loop so let's create our outside for loop first okay so this is our outside for loop and this is just gonna iterate through every object in the array so it's going to go 1 3 6 7 and then at each object we want to do another for loop where we add these two together and check to see if they equal our sum let me write it out and I'll explain it ok so here on line 43 16 is our nested for loop so we're gonna iterate through the array again however this where statement so where J not equal to I basically what that is saying is don't count where we're currently at in the iteration let me walk you through a real example so up here in line five in our numbers array let's say we're starting with one so we want to compare 1 2 3 6 7 7 12 and 14 however we want to do it where J is not equal to I so for example I don't want to compare 1 to 1 and the reason being let's say my son was the number 2 down here now nothing here added together equals 2 however if I didn't have this where clause on line 14 it would compare 1 and 1 in both 4 loops and then I would get a sum of 2 which really isn't the case so this where Clause makes it so that I'm not adding the same number to the number I'm comparing ok now we need to type out that addition logic I'll type it out and explain it ok so let's talk about what's going on here on line 16 to 21 so I'm adding the value 4 object at index J to the value 4 object at index I and seeing if it equals our sum and if those do equal our sum I'm gonna print true print the two values and return true if it doesn't equal or sum I'm just gonna print false with the two values and I'm printing these out just to show you how this is actually working so let's actually walk through it let me move my console up a little bit and scroll down so you can see we'll start from the beginning so the very beginning of this for loop is going to start at one up here on line five and then the J for loop is going to also compare everything in the array however because of this where Clause we're gonna skip the first one because we don't want to compare one to one and that's what you see is happening down in the console the first one is 1 plus 3 so 1 plus 3 does not equal our some of to remember to what we have in there so that's gonna be false and it's going to keep going so now it's going to compare 1 to 6 you know as you can see down here in the console 1 to 7 and then we move on through the array so 3 8 plus 1 and then we're doing 3 plus 6 3 plus 7 so this is just comparing everything to each other in the array again this is called brute force this brute force solution and pretty much anytime you have a nested for loop is going to be N squared in Big O notation let me take a step back and do Big O notation real quick it's basically just how you measure the efficiency of an algorithm so as you can see in this chart if you look at the pink line that is the O of N squared line as you add more elements to the array you can see that line just take off and it takes longer and longer and longer so this type of algorithm gets much worse the bigger the array is and that's the key thing so yes sure if you have an array of 10 objects it doesn't really matter what kind of algorithm you're going to do because it's going to be relatively the same however in real life you can be dealing with arrays that have millions millions of values in it so that's when efficiency really comes into play and as you can see with oav N squared here the pink line the more items you add into it the longer and longer it takes and it can get out of hand real fast okay so that's our brute force solution like I said it's not the best solution but it is a solution to start from and again we're just using a nested for loop and we're comparing each number to every other number in the array all right let's move on to our next solution go ahead and comment out line 29 so we're only running one solution at a time okay the next one we're gonna talk about is using binary search for the complement and actually let me go ahead and copy this array down here so I can see it visually in each one of these solutions okay so binary search for the compliment now if you watch my previous video you should be familiar with binary search and I have my binary search helper method way down here at the bottom which is the exact same method I did in that video check it out if you haven't seen it so now for this solution instead of comparing every number to every other number we want to be a little smarter about it we know that each value has to have a complement to our sum so here on line 33 let's say our sum is 10 so the complement for 1 is going to be 9 because 1 plus 9 is 10 the complement for 3 is going to be 7 because 3 plus 7 is 10 the complement for 6 is gonna be 4 etc etc so what we can do in this solution is iterate through our array and for each value figure out the complement and then do a binary search for that complement now this is going to be more efficient than our brute force solution let's talk about that real quick so looking at this chart binary search by itself is log n which is this orange line down near the bottom that's pretty good we like that so as you can see as the array gets bigger not much increases this is asymptotic if you have a login algorithm that's usually a very good thing that means you've done well however we have to run binary search for each of our values so we have to run binary search n times where n is the number of values in the array so doing a binary search for the complement is actually going to be n log n which if you look at this chart is this red line in the middle so you see it's better than N squared the pink line but it can still get away from you're pretty quick as the size of the array grows so this solution is an improvement over brute-force but it's not the best but we're still gonna walk through it real quick anyway all right so again this solution is what's known as n log n as you saw in the previous chart I'm just going to write our function signature ok the function signature is basically the same as before I mean I change the name but we're still taking in an array and then also taking in a sum that we're looking for just return false for now and then I'm calling it down here when we're looking for the number-10 okay so let's go and write this out so first thing we want to do is write our for loop all right now that we're iterating over our array let's go and find our complement for each value so it's fairly straightforward here on line 44 we're just taking the sum and subtracting the value at index I so for example to start off at 1 we're looking for 6 here in line 50 so 6 minus 1 is gonna be 5 so 5 is the complement to 1 that's what we're gonna look for in binary search ok now that we have our complement we need to adjust our array a little bit and the reason we need to do that is because our complement could be the number we're looking at let me explain so again here in line 50 we're looking for two numbers that add up to 6 so as we iterate through the array once we get to the number 3 the complement of 3 is also 3 so when we do binary search and we search through this whole array again we're going to be looking for the number 3 well 3 is going to be in there but it's also the same number we're trying to evaluate against so we don't want that so we need to adjust our array a little bit to remove the object we're looking at so we don't run into this situation so let's code that up okay all we're doing here on line 46 and 47 is we're creating a var because we need to mutate this array so we don't want to use let call temporary and we're saving that equal to our array and then here on 47 we're just removing the object at index I so again that's just removing the object we're evaluating against so when we pass this array into our binary search we're not looking for that same object going back to our example we're looking for the number 6 when we get to the number 3 and we look for the complement for 3 we're gonna remove 3 from the array so we don't find the same number we're looking at now looking at my binary search helper method down here here on line 86 you see it returns a boolean so let's go ahead and back up here and set a boolean variable so let has complement equal binary search in the array we're gonna pass it is temporary because remember this is one we just created and the key we're going to look for is complement and let me go and create a print statement okay let me run through lines 49 to 54 real quick so again this has complement variable is a boolean and that is a return value of our binary search which again down here on line 86 we were in binary search on the array it returns a boolean and if you're not familiar with binary search again check out my video I released yesterday on it back up here so if has complement is equal to true meaning we did our binary search we found the complement we're to go ahead and print that out and then return true so in our first example we're looking for two numbers that sum up to six and you see it's returning false and you can see here down in the console that it went through each of the numbers and there is no complement so let's change this to a number we know is in there so 26 because 12 and 14 equal 26 so you can see it goes through all the numbers no complement no complement no complement and then finally true number 12 and then the complement is 14 and that equals 26 let's try 14 and then we should get seven and seven down here in the console so yep false false false true number seven compliment seven let's try four we should get a very shorter list here so yep it found the numbers 1 and then the complement is 3 so again to recap up here in line 35 we're just iterating through this array and then getting the complement for each of these numbers and then doing binary search on this array to see if that complement exists within the array and again this is an N log n function which if you look at this chart here not the greatest but still better than the brute-force one so let's keep improving on this and do one more ok down here let's highlight out line 61 so we're not continuing to run that all the time all right let me take a step back and show you a quick rundown of how this solution works ok so a quick overview of this solution what we do here is we put pointers at the very low end of the array and at the high end of the array and then what we do is we add those up in this case is 15 and if that is greater than the sum we're looking for and right now our sum is 10 then we adjust the pointers accordingly so let me illustrate that to show you using 10 as an example so again 14 + 1 is 15 that is higher than 10 so we do is we move our high pointer down one place so now it goes from 14 to 12 now we do that again we add them up 12 plus 1 is 13 that is still greater than 10 so we're gonna keep moving this pointer down so now we're at the 7 now we add 7 + 1 that is 8 ah now here's where it's different 8 is less than 10 so now we move our low pointer up 1 to the 3 so now when we add them together 7 plus three equals ten and we found the value we're looking for everything's good to go and as you can probably tell these pointers keep getting closer and closer to each other and the way we can find out if the value is not in the array is if these values cross okay so as you just saw our pointers are going to start off at 1 and 14 and then we're gonna have to adjust them accordingly let's go ahead and write that out first we're going to start off with the function signature and it's gonna be pretty much the same as the other ones okay just like the previous examples I have my function name it takes in the array which is gonna be our numbers array and then takes in the sum which is what we're gonna find two numbers that add up to and then it returns a boolean and then down here on line 75 I'm just calling that function for the playground so as you saw in that previous clip we need two pointers and they start off at the lowest index and the highest index so let's get those so you see we have our low index equals zero and then var high index equals array count minus one and these are both the ends of the array and they need to be VARs because we are going to be adjusting these as we go so for this solution we're going to use a while loop if you're unfamiliar with a while loop it's kind of like a for loop except a while loop is it going to continue to run until it meets a condition when it stops let me write that out and it'll make more sense so my condition is while the low index is less than the high index I'm gonna keep executing this code the minute the low index is not less than the high index we're gonna stop and return false in the previous clip remember when I explain when the two pointers crossed that's how we know we don't have the values we're looking for well this is them crossing when the low index is no longer less than the high index they must have crossed so we stop our loop okay so the first thing we have to do on our loop is get the sum of the two pointers remember our pointers are starting out at up here on line 67 they're starting out at 1 in 14 so we have to get those values and add them together so let's do that so that's pretty straightforward so let's sum of items equal the object at low index which again is going to start at 0 which is going to be 1 and then we're gonna add it to the object of high index which is going to be 14 to start and we're gonna compare that sum to the sum we're looking for which in this case is 30 and then we're gonna do other stuff now if you look over here you can see this has been run almost 60,000 times this brings up a good point of infinite loops and I had to stop it if I didn't hit stop this would have been going up into the million and millions and millions the reason that happens is because this condition never stops so I need to make sure in my loop to be updating my low index and high index so that this condition will stop eventually that's the big thing to remember with while loop if you're writing a while loop make sure that you don't get stuck in what's called an infinite loop alright so from here on out it's just an if statement let me type it out and I'll explain it okay let me explain the line 79 to 88 again the first check in the if statement is if some of items is equal to the sum we're looking for then let's go ahead and print that out and then we'll return true we're good to go we found it however if it's not equal to the sum now we check if the sum is less than the sum we're looking for because remember if it's less than the sum we won't want to move the lower pointer up one so that's what we're doing here low index we're incrementing it by one and then the third check like I mentioned the explanation we're checking if it's higher than the sum and if it is higher than the sum we're gonna move the high index down one and again those pointers are going to get closer and closer to the middle either until we find two values that add up to the sum are looking for or if they cross and we don't have the value so down here let's go and make a print statement there that they have crossed and because we're looking for 30 and then you can tell easily that none of these add up to 30 the pointers cross and we return false now let's pick a sum we know is in there let's do 13 because that's 6 and 7 and it looks like I missed them high print statement a little but you get the idea so sum of 1 and 12 equals 13 so let's walk through what happened real quick our pointers start off at 1 and 14 we went through the loop that some of the items is 15 it didn't equal 13 so we don't go into here if the sum of the items is less than the sum that's not the case because our sum currently between 1 and 14 is 15 so we go into this bottom else if statement if some of the items which again is 15 is greater than the sum which is 13 let's move our high index down 1 so instead of the high index being at 14 now the high index is at 12 so now we're at 1 in 12 then we go back in the loop we add those two together and it equals our sum this time if this example only happen to take one step and then we go ahead and return true and print out the sum of 1 and 12 is 13 then the clean on my print statement and we can do just a bunch of different examples so like I said 99 you can see it's going to print out pointers have crossed let's go ahead and do see I know 19 in there 19 say some of seven and twelve equals 19 we have a 712 so you get the idea and looking at the efficiency this algorithm this is a linear solution the reason it's linear is because we're not gonna have to go through the array more than once at each value in the array we're moving the pointers so worst case scenario we're gonna have to iterate through there very once to get our pointers to where that need to be whether they either cross or they find the values so looking at our Big O chart this is what's called a linear solution meaning it's o of N and a linear solution is a pretty good solution let me throw out a huge disclaimer I'm speaking as a general rule of thumb obviously the efficiency you need is going to be very specific to your situation but in general if your linear login or constant you're doing pretty good anything above linear putting into the Exponential's like the O of 2n o of N squared of n log n where you can see they start taking off on you that's when you have a pretty bad algorithm so you want to be linear or below as a very general rule of thumb so there's a to some problem and it's a great example of how a very simple question can have many different solutions and I didn't even cover all the solutions but it can have many different solutions with many different efficiencies and you can see how complex it can get and like I said this is a pretty simple problem but it is a small example of what you can expect during the coding challenge portion of your interviews so there's a few different solutions to the to some problem written and Swift and if you didn't follow all that or you found some parts confusing don't worry go and leave a comment I'll jump in there and answer any questions I can all right if you found this at all useful go and hit subscribe I got more coding challenge videos on the way

Channel: Sean Allen

Views: 22,385

Keywords: two sum, two sum swift, two sum problem explained, two sum explained, two-sum, two-sum problem swift, two-sum problem explained, two sum solution, 2 sum problem, 2 sum problem explained, 2 sum problem swift, 2 sum problem solution, two-sum solution, Swift, Swift Tutorial, iOS Interview Questions and Answers, iOS Coding Question, Swift coding challenges, swift interview questions, iOS intervew questions, Xcode, iOS Developer, iOS Development

Id: cUmGngurKXo

Length: 17min 32sec (1052 seconds)

Published: Tue Jun 27 2017