Crack Leetcode 15: 3Sum

There is a way to make it easy.

Published in

The Startup

5 min readNov 6, 2020

Sometimes they make it look hard, while in fact, there’s always a way you can easily understand. Today, we’ll crack leetcode 15 —Three Sum — together. Without further ado, let’s get started.

Problem Description:

(Photo taken from Leetcode: https://leetcode.com/problems/3sum/)

Solution:

Solution #1: taking use of dict{ } and set( )

Ideation:

The problem wants to find all ABC so that A+B+C=0. We can use two for-loop to find out all the combinations of A, B. In each combination, we look for C.

If we again use a for-loop to find C, the time complexity would be O(N3). Therefore we need to reduce the time to find C.

It’s natural to think of dictionary, because it has a O(1) time for lookup a value. However, how can we make sure we don’t find duplicates?

# Avoid duplicates:

There are several cases that duplicates could happen:

(1) multiple A:

Then we can just skip the other As.

(2) other cases:

For case#1 above, since it’s the second for-loop, we can either skip the other Bs, or leave it there, and use Set( ) when adding a new answer. So that (A, B2, C) can’t be added in when (A, B1, C) already exist.

For case#2 above, we already have (A, B, C), and now we are getting (A, C, B), as the dictionary will find us B. Set( ) won’t help in this case.

For case#3 above, we are getting (D, B, D) when there’s only one D. However the dictionary finds us D.

We can solve case #2 and #3 together. If we build a dictionary like this:

key = A, value = largest index of A.

then we can rule out the values occurred before the second pointer, or itself.

Python Code for Solution #1:

Complexity Analysis for Solution #1:

Time complexity:

python built-in sort method is using timSort. Therefore bestcase time complexity is O(N), otherwise O(NlogN).

building the dictionary takes O(N) time.

The rest of the algorithm takes O(N square).

=> Time complexity = O(N2)

Space complexity:

python built-in sort method is using timSort. Therefore the space complexity is O(N).

The dictionary takes O(N) space in the worst case where there are no dups in nums.

The res takes at most (N-2)*(N-1)-> N2.

=> Space complexity is O(N2).

Solution #2: two pointers

Ideation:
Step <1>: Back to twoSum brute force:

Let’s assume no duplicates in input array for now.

We want to get A+B+C=0. That is also A+B=(-C). If we get all the (A, B) for each C, then we get the answer.

So it went back to a TwoSum problem. We can use “two pointers” solution for this problem.

Brute force is one way, where pointer1 loops the first number, from index 0 to n-1, while pointer2 loops the second number, from index n to (i+1).

Optimization #1: Skip the impossible combinations:

or one step further, taking advantage of the fact that now input array is sorted in non-decreasing order, we can skip those impossible ones:

Optimization #2: Further elimination of impossible combinations:

In the above situation, we are done with V1, and now checking V2. Is it necessary for the second pointer to go back to the end?

The answer is NO. Because we already know v2 plus any one (Vk+2 to Vn) will be larger than Target.

Instead, we can just start from current position, or Vk+1:

And that changes the pseudo code:

and here are the python code for this modified version, implemented in two ways:

(above two implementations are essentially the same process, just different ways of writing)

Once we understand the logic, we can just memorize the template for future usage.

Step <2>. Avoid duplicates:

In this problem A+B + C = 0, we are for-looping A, and for each A, we are looking for B+C = -A.

So first of all, we make sure A is always different, like what’s shown as the hollow pointer:

Then, for each A, when we are looking for B, C using TwoPointer method, we have to make sure C is always different, as shown by the right most pointer.

Now we are safe. Why not checking B? Because for each A, when C changed value, B can’t stay the same.

So here’s the python code:

Python Code for Solution #2:

Complexity analysis for Solution #2: