Three 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.

Three 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 a @param nums array
* @returns all the triplets `[nums[i], nums[j], nums[k]]` such that
* - nums[i] + nums[j] + nums[k] == 0
* - i != j, i != k, and j != k (don't reuse members at the same index)
* - the solution set must not contain duplicate triplets.
*
* @example
* - threeSum([-1, 0, 1, 2, -1, -4]) => ([ [-1,-1,2], [-1,0,1] ])
*/
export function threeSum(nums: number[]): [number, number, number][] {

}

Solution

/**
* Given a @param nums array
* @returns all the triplets `[nums[i], nums[j], nums[k]]` such that
* - nums[i] + nums[j] + nums[k] == 0
* - i != j, i != k, and j != k (don't reuse members at the same index)
* - the solution set must not contain duplicate triplets.
*
* @example
* - threeSum([-1, 0, 1, 2, -1, -4]) => ([ [-1,-1,2], [-1,0,1] ])
*/
export function threeSum(nums: number[]): [number, number, number][] {
const result: [number, number, number][] = [];
nums = nums.slice().sort((a, b) => a - b);

for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue;

let left = i + 1;
let right = nums.length - 1;

while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum < 0) {
left++;
} else if (sum > 0) {
right--;
} else {
result.push([nums[i], nums[left], nums[right]]);
left++;
while (nums[left] === nums[left - 1] && left < right) {
left++;
}
}
}
}

return result;
}

Origin

Original Problem Statement

Transcript

00:00 In our previous lesson we looked at to some sorted,

00:02 which I think is a hard problem

00:04 because you need some divine intuition in order to solve it.

00:06 However, I think once you've seen the solution

00:08 it's pretty easy to remember.

00:10 Now, today's problem known as threesome is something

00:12 that actually depends upon that for its optimal solution.

00:14 So it's definitely harder.

00:16 However, I actually got tested

00:17 for this when I interviewed at Google,

00:19 so this is not something that you want to skip.

00:21 And in this tutorial we will look at the problem statement,

00:24 it's nice solution as well as its optimal solution.

00:27 So let's go. Here's the threesome problem statement.

00:31 You will be provided with the number array

00:33 and our objective is to return triplets such

00:36 that they add up to the value of zero.

00:38 There are two additional conditions.

00:40 One is that we cannot reuse members at the same index.

00:43 As an example, if one of the values is zero,

00:46 we cannot just return 0, 0 0

00:48 because we will be reusing the zero member.

00:51 The second additional condition is

00:53 that the solution set must not contain duplicate triplets.

00:56 For example, if our input contains multiple threes,

00:59 multiple zeros and multiple minus threes,

01:01 we can only return the triplet minus three zero

01:04 and three once.

01:06 Now as always, if you're not

01:07 provided any examples, it's good

01:08 to come up with a few of your own.

01:10 This particular problem does come with this example

01:12 and you can see that we have triplets minus one,

01:15 minus one two that add up to zero

01:17 and the triplet minus 1 0 1, that adds up to zero.

01:20 Now we can flesh out the function definition so

01:23 that we know the kind of inputs

01:24 and the outputs that we are dealing with.

01:26 We are dealing with the number array

01:27 and we will be returning an array of couples.

01:29 Each couple will contain three numbers

01:32 and within the function body we have our result initialized

01:35 and that is what we will return.

01:36 And our objective is to fill this up with as many doubles

01:39 that add up to the value zero.

01:41 Now let's think through the simplest solution

01:43 that we can come up with.

01:44 We are looking for sets of threes within the input array

01:46 such that they add up to zero

01:48 and we can find all sets of threes

01:50 with the simple triple loop.

01:52 So let's code that up.

01:53 We loop through the input array three times

01:55 and terminate at minus two

01:57 and minus one for INJ so that we have values to use for J

02:01 and K, which we initialize at I plus one and J plus one.

02:05 This ensures that at any given point I, J

02:07 and K do not overlap

02:09 and they're not equal to each other,

02:11 which was one of our requirements.

02:13 And within the core of the triple loop, we checked

02:15 that the sum of numbers i, J and K is equal to zero.

02:19 And if it is, we add that to our result array.

02:22 Now at this point you might think

02:23 that we have a correct solution,

02:25 however, there is actually one more requirement

02:26 that is the solution set must not contain duplicates

02:29 and we haven't done anything for that right now

02:32 and we can actually see that play out with a simple example

02:35 that contains multiple duplicate answers.

02:38 And if we run this you can see that it pretty much blows up.

02:41 Now there are lots of ways to solve this,

02:43 but the key realization over here is

02:44 that the time complexity of the algorithm right now is cubic

02:47 because of those triple loops, which means

02:49 that we can sort the input array in

02:51 and log in without affecting this time complexity.

02:54 And this will greatly help us in finding these duplicates.

02:57 We first create a copy of the input NUMs with NUMs dot slice

03:00 and then sort them by using a custom comparer function.

03:03 Now this custom comparer function A minus B is actually

03:07 required if you want to sort numbers

03:08 and I have a lesson dedicated to

03:10 that within the video description.

03:11 Now with the input number sorted, it's pretty easy

03:13 to check if the current number is a

03:15 duplicate of the previous one.

03:17 The only word of caution over here is

03:18 that we can only do it in the second iteration of the loop

03:21 because the first iteration there is no previous number

03:24 to look at, which means for I we make sure

03:26 that it is greater than zero.

03:27 For J, we make sure that it is greater than I plus one.

03:30 And for K it is greater than j plus one.

03:33 Other than that, we simply check if the current value is the

03:35 same as the previous value

03:37 and if so, we continue on to the next iteration

03:39 of that particular loop.

03:41 And now with these changes in place, if we run a code again,

03:44 you can see that we only get one answer

03:46 and this is actually a correct implementation

03:48 of the problem statement.

03:50 Well, the question is can we make this solution perform

03:52 better than cubic time?

03:54 And the answer is yes.

03:55 The optimal solution is actually in quadratic time.

03:57 So let's look at how we can achieve that.

03:59 The key realization over here is

04:01 that once we have the first number

04:03 and the remainder of the array is already sorted,

04:05 we are essentially dealing with a twosome sorted problem.

04:08 Now I do have a lesson dedicated to that particular problem

04:10 that I believe in the video description,

04:13 but let's look at how we can implement that over here.

04:16 Consider this particular input array which

04:18 we already have sorted.

04:19 Now at the point when I is looking at minus 20,

04:22 the remainder of the array is essentially a twosome sorted

04:25 problem where we want to find something that as up

04:28 to the target value of 20 so

04:30 that it cancels out the minus 20

04:32 to give us a threesome of zero.

04:34 And the smart solution to

04:35 that particular problem is using two pointers

04:38 and looping through the remainder of the array.

04:40 Only once we maintain a left pointer initialized

04:43 to the first element and a right pointer initialized

04:45 to the last element, and then we sum these two numbers.

04:48 And if they are two big, for example, they are in this case

04:52 'cause the sum is 23, we decrement the right pointer

04:55 and then do the same check again.

04:57 And this time the value is too small.

04:59 So we increment the left pointer to increase the value

05:02 and this time the sum is a perfect 20

05:05 and we have found our solution.

05:07 So let's look at how we can implement this in code.

05:10 And in my opinion, understanding the mechanics

05:13 of this problem is hard.

05:14 However, writing the code is actually easy once you

05:17 understand those mechanics.

05:19 As you mentioned, we initialized the left

05:20 to the first element, which is I plus one in this case

05:23 and the right to the last element,

05:25 which is numbs length minus one.

05:28 And then we loop as long as left is smaller than right,

05:31 that is we haven't run out of elements.

05:33 We calculate the sum of NUMs I left and right

05:36 and if they are less than zero,

05:38 the value is too small, we increment left.

05:41 If it is greater than zero than the value is too big,

05:44 we decrement right?

05:45 Otherwise the sum is zero, which is just perfect.

05:48 So we add the nus, I left and right into our solution set

05:52 and this is almost a complete solution.

05:54 One final thing that we have to remove

05:56 Duplicates, duplicates

05:58 of I are already being filtered out.

06:00 So let's look at what we need to do

06:01 for duplicates of left and right.

06:04 We only care about duplicates when we actually find a

06:06 solution because that is the case when duplicates will

06:09 actually end up in our solution when the values are not

06:11 right, they're going to be skipped over multiple times

06:14 and that will be fine.

06:15 And that is actually a key observation.

06:18 We only need to skip over the duplicate of left or right

06:21 and its corresponding pair will automatically get skipped

06:24 because it'll never be the right value.

06:26 Let's look at an example.

06:28 We have eye pointing at minus two and left

06:30 and right pointing to solution points which are

06:33 surrounded by duplicates.

06:34 If we successfully skip over the duplicates of left,

06:37 then the duplicates

06:38 of right will never be the right answer anyways

06:41 and they will get skipped

06:42 by the other conditions in our wide loop.

06:44 And with this observation in place,

06:46 we can code up the skipping portion of our twosome problem.

06:49 We increment left and then we make sure

06:51 that the new left is not the same as the previous left.

06:54 And if it is the same, then we increment left

06:57 to jump to the next value.

06:58 And if you're going to be incrementing left in this loop,

07:00 we also need to make sure that left has not become equal

07:03 to right and this is the entire

07:06 optimal solution for the threesome problem.

07:07 It has time complexity of O of N squared

07:10 because there is one loop going through I

07:12 and a second loop, which is incrementing left

07:15 and right for the remainder of the array.

07:17 And the O of N log N

07:18 provided by sort will collapse into this O of N squared

07:21 as well.