Twosome is actually one of the first problems on the infamous lead code website. It originated from fang, but I've had colleagues interviewed for this in upcoming startups even in the past year. So in this lesson, we will look at the problem statement along with its naive solution as well as an efficient implementation. So let's go. Your mission to choose to accept it is to take an array of numbers and a target value and then return the indices of the two numbers within that array that add up to that target value. The problem statement also comes with some assumptions that there will always be exactly one solution

and you shouldn't use the same element and therefore the same index twice. And we've talked about this in other coding interview questions as well. The first thing that you should do is to come up with some examples and verify that you are on the right track. So with this array 2 7 11 15, we are searching for two numbers that add up to the target value of nine. The two numbers are two and seven, and the indices for these numbers is what we return, which is zero and one. The next step of course will be to write a function that has the signature of our desired inputs and outputs. We have the twosome function that takes a number array

and a target number value, and then returns a couple of the two indices that are found. Now. Right now we are getting an error because we're not returning anything, but we can fix that by throwing an error in case nothing is found. And this is something that we can leave in the function indefinitely, but it really shouldn't happen based on our assumption that exactly one solution does exist. Now let's look at a simple correct solution for this problem. Fundamentally, we will loop through all of the elements except for the last one and for every loop iteration, we will loop through all of the remaining elements in the array

and see if this particular element and any of those elements add up to the target value. This satisfies the constraint that we don't end up returning the same index twice as index two starts after index one. This plus one is also the reason why we stop with length minus one, and our final condition is pretty simple. If one plus two is equal to the target, then we return the double of index one and index two. Now, as mentioned, this is a correct solution to the given problem statement and would be perfectly fine for most real world use cases, however, it's not the optimal solution in terms

of time complexity. Fundamentally, we are looping through the array twice, resulting in a time complexity of OFN squared. So let's look at a solution where we only need to loop through the array once. And we've seen this secret to removing double loops in previous coding interview questions as well. And that is to use a hash based data structure like map. With this particular map, we are going to maintain the inva that for any number that we have seen, what is the index for that number in the input array. And then we will loop through the input array only once. And for any number,

we will see if we have already seen the complement of that number that gets us that target value. If the map already contains the complement, then we will return the complement index as well as the index for this number, and that'll be our solution. Otherwise, we will Continue with the next number. But before we do that, we need to maintain that in variant, that NUM two index contains the index for this particular number. So now we have a single loop with the time complexity of O one thanks to the magical property of hash maps to store and get values in constant time. So now the time complexity of the overall algorithm is OFN.

Now, just to hammer the correctness of this algorithm home, we will look at numbers one by one and store them into NUM two index. And if at any point we have seen a number known as a compliment that combined with the current number gives us the target value, we have found our answer and that is what we return.