Two Sum

Pro Members Only

This lesson is available if you have an active subscription.

Alternatively, some member might be able to gift it to you.

If you already have a subscription, you can sign in.

Two Sum

Subscription Required

You must have an active subscription to access this content.
If you already have a subscription, you can sign in.

Problem

/**
* Given an array of @param nums and a @param target
* @returns indices of the two numbers such that they add up to target
*
* You may assume:
* - each input would have exactly one solution
* - and you may not use the same element twice.
*
* @example
* twoSum([2, 7, 11, 15], 9) => ([0,1])
*/
export function twoSum(nums: number[], target: number): [number, number] {

}

Solution

/**
* Given an array of @param nums and a @param target
* @returns indices of the two numbers such that they add up to target
*
* You may assume:
* - each input would have exactly one solution
* - and you may not use the same element twice.
*
* @example
* twoSum([2, 7, 11, 15], 9) => ([0,1])
*/
export function twoSum(nums: number[], target: number): [number, number] {
const numToIndex = new Map<number, number>();

for (let index = 0; index < nums.length; index++) {
const num = nums[index];

const complement = target - num;
const complementIndex = numToIndex.get(complement);
if (complementIndex != null) {
return [complementIndex, index];
}

numToIndex.set(num, index);
}

throw new Error('Invalid Input: No match found');
}

Origin

Original Problem Statement

Transcript

00:00 Twosome is actually one

00:01 of the first problems on the infamous lead code website.

00:04 It originated from fang,

00:05 but I've had colleagues interviewed

00:07 for this in upcoming startups even in the past year.

00:10 So in this lesson, we will look at the problem statement

00:12 along with its naive solution as well

00:14 as an efficient implementation.

00:16 So let's go. Your mission to choose to accept it is

00:20 to take an array of numbers and a target value

00:23 and then return the indices of the two numbers within

00:26 that array that add up to that target value.

00:29 The problem statement also comes with some assumptions

00:31 that there will always be exactly one solution

00:33 and you shouldn't use the same element and

00:35 therefore the same index twice.

00:37 And we've talked about this in other coding

00:39 interview questions as well.

00:40 The first thing that you should do is to come up

00:42 with some examples and verify

00:44 that you are on the right track.

00:45 So with this array 2 7 11 15, we are searching

00:49 for two numbers that add up to the target value of nine.

00:52 The two numbers are two and seven,

00:55 and the indices for these numbers is what we return,

00:57 which is zero and one.

00:59 The next step of course will be to write a function

01:02 that has the signature of our desired inputs and outputs.

01:05 We have the twosome function that takes a number array

01:08 and a target number value,

01:10 and then returns a couple of the two indices that are found.

01:13 Now. Right now we are getting an error

01:15 because we're not returning anything,

01:17 but we can fix that by throwing an error

01:19 in case nothing is found.

01:20 And this is something that we can leave in the function

01:22 indefinitely, but it really shouldn't happen based on our

01:25 assumption that exactly one solution does exist.

01:28 Now let's look at a simple

01:29 correct solution for this problem.

01:31 Fundamentally, we will loop through all

01:33 of the elements except for the last one

01:36 and for every loop iteration, we will loop through all

01:38 of the remaining elements in the array

01:40 and see if this particular element

01:42 and any of those elements add up to the target value.

01:46 This satisfies the constraint

01:47 that we don't end up returning the same index twice

01:50 as index two starts after index one.

01:53 This plus one is also the reason why we stop

01:56 with length minus one,

01:57 and our final condition is pretty simple.

01:59 If one plus two is equal to the target,

02:02 then we return the double of index one and index two.

02:05 Now, as mentioned, this is a correct solution

02:07 to the given problem statement

02:08 and would be perfectly fine for most real world use cases,

02:11 however, it's not the optimal solution in terms

02:13 of time complexity.

02:14 Fundamentally, we are looping through the array twice,

02:17 resulting in a time complexity of OFN squared.

02:20 So let's look at a solution where we only need to loop

02:23 through the array once.

02:24 And we've seen this secret

02:25 to removing double loops in previous coding

02:27 interview questions as well.

02:29 And that is to use a hash based data structure like map.

02:32 With this particular map, we are going to maintain the inva

02:35 that for any number that we have seen, what is the index for

02:38 that number in the input array.

02:39 And then we will loop through the input array only once.

02:43 And for any number,

02:44 we will see if we have already seen the complement of

02:47 that number that gets us that target value.

02:50 If the map already contains the complement,

02:52 then we will return the complement index as well

02:54 as the index for this number,

02:56 and that'll be our solution. Otherwise, we will

02:58 Continue with the next number.

02:59 But before we do that, we need to maintain that in variant,

03:02 that NUM two index contains the index

03:05 for this particular number.

03:06 So now we have a single loop with the time complexity

03:09 of O one thanks to the magical property of hash maps

03:12 to store and get values in constant time.

03:15 So now the time complexity of the overall algorithm is OFN.

03:19 Now, just to hammer the correctness of this algorithm home,

03:22 we will look at numbers one by one

03:24 and store them into NUM two index.

03:26 And if at any point we have seen a number known

03:28 as a compliment that combined

03:30 with the current number gives us the target value,

03:32 we have found our answer and that is what we return.