let's all leak code one to some the most popular leak code question so we're given an input array and some target in this case 9 and we want to find the two values in this input array that sum to 9 so in this case it's 2 & 7 now we want to return the indices of these two values so the index of zero of the index of two is zero the index of 7 is 1 so we return 0 & 1 we're guaranteed that there's exactly one solution so we don't have to worry about not finding a solution and we don't have to worry about multiple solutions now the most intuitive way to solve this problem is basically just check every combination of two values and see if they can sum up to our target so we start at 2 we check every combination we can make that includes 2 so we scan through the remainder of the array 1 5 3 and check if any of those numbers added to 2 some store target for in this case none of them do so next we can repeat the process let's check every combination including one that sums up the target for so we scan through every element that comes after at 5 & 3 and we find that one added with 3 sums up to our target 4 notice that we didn't have to check the values that came before 1 because we already checked the combination 2 & 1 when we were up over here remember when we checked every combination with 2 so we didn't have to repeat that work down here we only had to check the numbers that came after 1 so the runtime of this algorithm isn't super efficient this is basically brute force we're going through the entire array of length and and we're gonna do that worst case n times for each number this means that over all worst case time complexity will be O of N squared so can we do better now the thing to notice is that for each number for example 1 the value we're looking for is the difference between the target and this value 1 so we're looking for 4 minus 1 which is equal to 3 so that means this is the only value we can add to one that'll equal the target so we don't have to check every number we just want to know if resist s-- now the easiest way we can do this the most efficient is by making a hash map of every value in our input array so we can instantly check if the value 3 exists now let's try the same problem except let's use a hash map this time now in our hash map we're going to be mapping each value to the index of each value so the index of 2 is 0 the index of 1 is 1 the index of 5 is 2 the index of 3 is 3 so let's so in our hash map we're going to be mapping the value to the index now we could add every value in this array into the hash map before we start iterating through it but there's actually an easier way to do it if we added the entire array into the hash map initially then we would get to the value 2 first right we would want to checked as the difference between target 4 minus this value 2 which is equal to 2 exists in our hash map and we would find that 2 does exist in our hash map but we're not allowed to reuse the same one right because they're both at the same index we can't use the same value twice so we would have to compare the index of our current 2 with the index of the 2 that's in our hash map there's actually an easier way to do this though and it's a little clever and let me show you how to do it that way so doing it this clever way initially we say our hash map is empty so we get to the value 2 first of all right and we want to look for the difference 4 minus 2 in our hash map our hash map is empty so we don't find 2 so then after we visited this element then we can add it to our hash map so now that I'm done visiting it I'm gonna move to the second element 1 and before I do that I'm gonna add this value 2 to our hash map and the index of this value is gonna be 0 now I'm at 1 I'm looking for 4 minus 1 which is 3 I see 3 isn't in our hash map but it actually is in our array so what's the problem well for now we're going to say we don't find our find three so we add one to our hash map the index of this one is one and now we move to the next element five we check does four minus five it's four minus five exists in our hash map that's negative one so no it does not then we add this five to our hash map and it's index which is two and we move to the last value in the array three we checked this four minus three e exists in our hash map now that's one so we see it does exist right right over here it exists the value exists and it's index is one so now we found our two values that sum to the target and we want to return their indexes their indices which are going to be one and three so with this algorithm we don't have to initialize our hash map it can be initially empty and then we can just iterate through this array in one pass now the reason the algorithm can work in that way with just one pass is this so let's say we had a giant array right we know for sure that there are two elements in this array that sum to our target right we don't know where they are they're at some arbitrary location when we visit the first one of those elements our hash map is only going to be this portion of the array it's only going to have the values that came before the first value so we're gonna we're gonna notice that the second value that can sum to the target is no is not going to be in our hash map yet but once we get to the second value our hash map is going to be this portion so every value that comes before this right so we're gonna be guaranteed that once we visit the second element that sums up to the target we're gonna be guaranteed that the first one is already in our hash map so we're guaranteed to find the solution now since we only have to iterate through the array once and we're adding each value to our hash map which is a constant time operation and we're checking if a value exists in our hash which is also a constant time operation the time complexity is going to be Big O of n we are using extra memory right that hash map isn't free so the memory complexity is also going to be O of n because we could potentially add every value to the hash map so now let's code the solution so remember we need a hash map right I'm going to call this previous map because it's basically every element that comes before the current home that every previous element is going to be stored in this map where it can be mapping the value to the index of that value so now let's iterate through every value in this array we need the index as well as the actual number so let's do it like this and Python before we add this to our map let's check if the difference which is equal to target minus n now let's check if this difference is already in the hash map if it is then we can return the solution which is going to be a pair of the indices so I can get the first index like this and the second index is just AI now if we don't find the solution then we have to update our hash map so for this value n I'm gonna say the index is I and then we're going to continue since we're guaranteed that a solution exists we don't have to return anything out here right but I'll just put a return for no reason now let's see if it works and it works perfectly so with this kind of neat little trick but just doing it in one pass you can reduce the amount of code you have to write and not have to worry about like edge cases and comparisons and things like that