How to Solve LeetCode Two Sum | Understanding Algorithms

well hello there my friend it's nice to see you again today we're going to take a look at lead code problem number one it's called twosome now this is a very popular interview question so this is actually really good one to know let's get started by reading the problem description given an array of integers nums and an integer target return indices of the two numbers such that they add up to the target you may assume that each input would have exactly one solution and you may not use the same element twice and you can return the answer in any order so if we take a look here in example number one we can see our input array nums and we have 2 7 11 15 as our integers and we're given a target of 9. so essentially what we want to do is we want to find the two numbers in this array which when added together will give us the target number and we can see that our output is 0 and 1. note that what we want to return actually is the indices at which those numbers reside in the array and we can see just that here in the output that we're given 0 and 1 because if we look at index zero in this array we have the number two if we look at index one in this array we have the number seven and two plus seven of course equal to target number nine and just to clarify even further we can look at the next two examples so in example two we're given the nums array with three two and four and we see our target is six and so we can go through the array and we can say well does three plus two equals six the target no does three plus four equal the target no does two plus four equal the target yes 2 plus 4 equals 6. and since 2 and 4 are at the indices 1 and 2 in this array that's what we return we return an array with those indices 1 and 2. and then in the third example we're given a nums array of 3 and three so in this case we have the same number at both indices and both of those numbers add up to the target of six so we can return their indices zero and one and i think they're giving us this example because if we look in the description they point out that we may not use the same element twice so i believe that even though we have the same numbers here they're at different indices so we can return those indices now we're about to get going solving this problem but one thing i want to point out before we do so is that if you've ever been to something like the county fair or a water park or even a rodeo well you know those things are fun but this is actually going to be way more fun than that because we're going to solve this problem in three different ways and the reason that we're going to solve the problem in three different ways is because we're going to show how we can start with more of a brute force approach and then go ahead and optimize our solution so we can improve our time complexity so let's get going so let's get started here with the first approach this will be the brute force approach let's go ahead and define our function function to sum and it's going to take that array the array of integers and it's also going to take a target which is going to be an integer and then let's go ahead and define that array of numbers that we're going to pass in we'll say const nums 1 is going to equal this array here 2 7 11 and 15. and i'm getting these numbers from the first example that they gave us and the way that we're going to call this function is like sale so we'll call two sum and we'll pass in that array num1 and we'll pass in the target that they give us as well for this example the target was 9. we can make a little comment here for ourselves to help us remember what this should return so in this case we're looking for the indices 0 and 1. ultimately we're going to want to see a result so we'll wrap this in a console.log statement now a lot of times when you're getting started with a problem it's actually a good idea to just take a look at the brute force approach because this will allow you to spend a little time with the problem and to get your feet wet if you're not familiar with the term brute force basically the brute force approach is an approach that's not really optimized it tends not to be optimized in terms of big o and it also tends to be the first solution that you would probably come up with at first glance so the first approach that you could take to a problem would be to kind of figure out how you would do this by hand before you even necessarily thought strictly in terms of code so if we wanted to find the two numbers in this array that added up equal the target of nine an obvious way to do it would be simply to start with the first number and then go through each successive number in the array when you get to each one of those numbers you add it to this first number the two and see if it equals the target so we would say okay 2 is our first number we go to the next number 7 does 2 plus 7 equal 9 well in this case it does right away we found our answer so we could just return these two indices let's say if we were looking for a target of seventeen well in that case we would start with two seven plus two doesn't equal seventeen eleven plus two doesn't equal seventeen fifteen plus two does equal seventeen so we would return those indices zero and 3. now in these cases we were able to find our answer simply through one pass of the array however what if we had something like this let's just change up our numbers a little bit we'll start this array with a 1 and then we'll have a 2 and then let's put a seven here and now let's say that we were looking for the target of nine well using the same approach that we've been talking about so far we would start with the one and we would go through each number we would say one plus two that doesn't equal nine one plus seven that doesn't equal nine one plus fifteen that doesn't equal nine either so at this point we've done one pass through the array so now we would have to go to the next index in the array and again we'd have to iterate through the rest of the array at least up until the point where we find our answer so we'd say 2 plus 7 does that equal 9 yes it does so now we've found our answer and even though we found our answer you could see what the potential problem is here imagine if this array had a million elements in it or thousands and thousands of elements well this would be very bad in terms of time complexity because we wouldn't only be doing one pass through the array but for each index in the array in the worst case scenario we would have to add each successive number to that index and then kind of start over again going to the next index and adding these successive numbers to that and on and on and on so we can see that this is not going to be the optimal solution however let's go ahead and implement it in code because it'll in fact work even though it won't be optimal so the way that we'd do it is we'd start out by creating a for loop we could say let i equal zero i is less than the array.length and then i plus plus and then what we're going to do is actually we're going to make another loop so we're going to have nested loops and this is kind of a dead giveaway for a quadratic runtime and quadratic runtimes are usually not optimal so here we're going to create another for loop i'm going to say for let j equals i plus 1 j is less than array.length and then j plus plus so here as we start the looping process we're going to start with the index 0 which is going to be the number 1 and then we're going to be looping over the remainder of the array and that's why we have j equals i plus 1 because we want to start adding to this number here starting at the next index so i plus 1 which in this case would be index 1. in order to tell if the numbers that those indexes equal the target we'll say if the array at i plus the array at j if those two numbers equal the target well then we can return right away and we'll return an array with those indices so i and j and in the leap code description of the problem they tell us that there is going to be exactly one solution so if our algorithm is correct we should have something to return here so let's save this and let's open up the terminal okay here's my terminal on the right side we'll go ahead and run the code and actually what i just noticed here is that we had changed the array around before when we were experimenting so we were in fact looking for those indices that we got 1 and 2. because at into c1 we have a 2 into c2 we have a seven two plus seven equals nine the original array that we were given from leak code was two seven eleven and fifteen in that case we were expected to return an array with zero and one so let's save and rerun the code and we can see that we get 0 and 1. so with this brute force approach we definitely have a solution working but now the question is can we do better in terms of our run time so now we're going to see how we can improve that time complexity by looking at a different solution for this problem and that solution we can call the two pass hash map solution oh snap let's go ahead and get rid of everything inside of the body of this function we're still going to pass in the array in the target actually let's go ahead and rename this first parameter to nums just to make what's going on inside of our function a little bit more obvious and explicit now oftentimes for these kind of problems what you can do is you can utilize another data structure called a hashmap in order to improve the time complexity now just note there is going to be a space time complexity trade-off here because we're going to be creating another data structure which is going to hold key value pairs and that data structure is the hash map but if a better time complexity is what we're after this is a better solution than the first one that we saw so if you're not familiar with the concept of a hashmap in javascript a map is actually an object where we can store key value pairs and what are the key value pairs that we're going to be storing in this hash map well as we iterate over the nums array we're going to store the integer at each particular index as the key and we're going to store the index itself as the value so we're going to go ahead and create a hash map here we'll call it hashmap consthash map and we'll set that equal to an empty object and then like i said we're going to iterate over the array so i have four let i equal zero i is less than nums.length and then i plus plus okay and here is where we want to set up those key value pairs so we're going to say hash map at the nums at i is going to equal i so nums at i is going to be each one of these integers in the array the 2 7 11 15. what we're doing here is we're storing each one of those as keys in the hash map and we're setting those keys equal to the value of i and i is the index so key of 2 will have a value of 0 index 0 key of 7 will have a value of 1 for index 1 and so on actually why don't we go ahead and console.log out the hashmap at that point to see what we're getting i'll save and i'll open up the terminal here and let's run our code and here like i said you can see key of 2 index 0 which is the value key of 7 value of index 1 and so on 11 and 15 at indexes 2 and 3 for the values so that's the first step here in the solution setting up the hashmap now remember we called this solution the two pass hash map solution so we're going to be doing two passes through the array we're going to do the second pass now and in this pass this is where we're going to find out if our hash map has the complement of the number in other words the target minus that number that's the numbers complement the number that we're looking for if we find that complement number in the hashmap since we have all the numbers stored in that hash map along with their indices we can return an array with the current index that we're on along with the complements index so let's go ahead and let's say 4 let i equal 0 we're going to create another for loop here i is less than nums.length once again and then i plus plus just like we did in the for loop before and just to make things nice we can actually get our complement first so we say let complement equal the target minus nums oops target minus nums at i so in other words as we're going through the array since our target is nine nine minus two is going to equal seven and that's the complement of the number that's the number that we're looking for now that we have it stored in a variable we can perform a lookup on our hashmap to see if it exists in the hashmap so we'll say if hashmap at complement so if that complement exists in the hashmap and in here we're also going to use the logical and operator i'm going to say and hash map a complement doesn't equal i because we want to make sure that we're not returning the same index that we're at well if it exists in the hash map then we found our answer we can now return an array with i which is the current index that we're at and hashmap at the complement whose value is its index so let's go ahead and save that let's open up the terminal we'll clear this and we'll run our code and there we go we get 0 and 1 again just like before the difference now though is that we no longer have that quadratic runtime if you're saying well what about these for loops here we're running two for loops well the thing is this would actually be considered o of two times n because we're doing two passes through the array one after the other and this is better than quadratic time with big o notation we just dropped the coefficient so we would drop the number two and we're really left with of n runtime or linear runtime now coming from this solution we can actually optimize our solution even a little bit further in this solution we'll call the one pass hash table solution and all it's going to require is a slight tweak from the two pass hash table solution so as the name suggests we're only going to have one pass through the array so we're going to get rid of this for loop here we're going to keep this and we'll paste that line down here after the if statement what we're going to do here with this solution is actually we're going to be checking the hashmap for the complement while we're iterating through the array at the same time we're going to be storing the number in the hashmap along with its index if it doesn't yet exist and actually with this slight tweak here we're almost there the only thing we're going to change actually now is this if statement inside of this if statement here we're just going to say if complement in hash map so as we're going along if we find the numbers complement in the hashmap if it's already in there then we're going to return the current index and we're going to return the value that we get from hashmap at the complement which is going to be the index of the complement now if it's not in the hash map we're going to store it in the hash map and just like before we're going to store it along with its index and now so with this solution we have a linear runtime or o n let's save it and run it in the terminal and here we can see we have 1 and 0 or 0 and 1 and actually we can switch these numbers around so we get the same order as here zero and one so we can have hash map at complement and then i will save and run it again in the terminal and here we have zero and one so now why don't we do the ultimate check let's copy our code and let's go over to leap code so i'll go ahead and paste it in and let's run our code and here you can see accepted let's submit our code and here you can see success run time 76 milliseconds faster than 85.10 of javascript online submissions so in this video we looked at three different ways to solve the two-sum problem first we started out with the brute force solution which had a quadratic run time and then we saw how we could optimize it with the usage of a hash table first with a two pass solution and then with a one pass solution which was even better so thanks for checking out this video if you enjoyed the video if you feel like you got something out of it please give it a like and subscribe to the channel so you can be alerted to new videos to come see you next time

Channel: The Code Creative

Views: 658

Rating: 4.891892 out of 5

Keywords: leetcode, leetcode two sum, leetcode twosum, leet code two sum, leetcode 66, 1 leetcode two sum, how to solve leetcode two sum, how to solve two sum, leetcode javascript, two sum javascript, leetcode solutions, help with leetcode problems, leetcode problems two sum, google interview questions, google two sum, cracking the coding interview, javascript algorithms, coding interview preparation, coding interviews, the code creative, code creative, gregg fine

Id: J0U1obg5BEM

Length: 17min 1sec (1021 seconds)

Published: Tue Sep 22 2020