Approach #1: Brute Force [Time Limit Exceeded]
Intuition
We try every triple of elements in the array. If it sums to zero, we record the answer.
Algorithm
For every triple of indices i < j < k
, let's look at if A[i] + A[j] + A[k]
. If it does, then sorted([A[i], A[j], A[k]])
occurs somewhere in the answer.
We keep a set of our answers, then sort the answers at the end.
Python
class Solution(object):
def threeSum(self, A):
ans = set()
for i in range(len(A)):
for j in range(i+1, len(A)):
for k in range(j+1, len(A)):
if A[i] + A[j] + A[k] == 0:
ans.add(tuple(sorted([A[i], A[j], A[k]])))
return sorted(ans)
Complexity Analysis

Time Complexity: $$O(N^3 + N^2 \log N)$$, where $$N$$ is the length of the array. We do $$O(N^3)$$ work looking for triples to add to our answer, but our answer (which may have size $$O(N^2)$$) still needs to be sorted, which takes $$O(N^2 \log N^2) = O(N^2 \log N)$$ work.

To justify that our output may have size $$O(N^2)$$, notice after choosing an unordered pair of integers in the array, there is at most one solution. So the number of solutions is bounded above by the number of unordered pairs of integers.

For a more concrete example, say we have
1, 2, ..., K
,K+1, K+2, ..., 2*K
, and3*K, 3*K+1, ..., K2
. Then there are order $$O( (\frac{N}{4})^2 ) = O(N^2)$$ ways to choose a positive number from $$[1, K]$$ and another one from $$[K+1, 2K]$$, and all of these choices have a corresponding negative number so that the sum of these values is zero.


Space Complexity: $$O(N^2)$$. The answer could be up to $$O(N^2)$$ in size, as justified above.
Approach 2: Reduction to TwoSum, Pointer Variation [Accepted]
Intuition
Say the given array is A
. For each A[i]
, we have an instance of the twosum problem on A[i+1:]
with target A[i]
, where the twosum problem is the problem of finding unique unordered pairs in an array that sum to a given target.
Algorithm
Sort A
. For each A[i]
, we'll solve the corresponding twosum problem, and take the combined answer at the end.
To solve twosum, we use a twopointer approach. We'll ask for every j
, what is the largest k
that makes our sum A[i] + A[j] + A[k]
equal to zero? If our sum is too big, then we will reduce k
. If our sum is too small, then we know there was no such k
that could have made this zero, so we'll increment j
. Then, since A[j+1] >= A[j]
, we do not need to check any k
larger than the one we have now.
One annoying detail for those familiar with the basics of twopointer approaches, is that we didn't want to take repeats into our answer. A straightforward way to handle this is to take the answer in a Settype data structure, then sort it at the end. However, this sorting introduces a $$O(N^2 \log N)$$ factor which is less desirable.
A more efficient way is to have our pointer skip repeated values. If we group the sorted array into groups of the same value, then we will only consider the leftmost value in each group (rightmost for the k
pointer.) This is the motivation behind code that checks for A[i1] == A[i]
, or while j < k and A[j] == A[j+1]
, etc.
Python
class Solution(object):
def threeSum(self, A):
A.sort()
ans = []
N = len(A)
for i in range(N):
if i > 0 and A[i1] == A[i]:
continue
j, k = i+1, N1
while j < k:
if A[i] + A[j] + A[k] < 0:
j += 1
elif A[i] + A[j] + A[k] > 0:
k = 1
else:
ans.append((A[i], A[j], A[k]))
while j < k and A[j] == A[j+1]:
j += 1
j += 1
while j < k and A[k] == A[k1]:
k = 1
k = 1
return ans
Complexity Analysis

Time Complexity: $$O(N^2)$$. The outer loop (
for i = 0..N1
) is $$O(N)$$. At every step in thewhile j < k
loop,kj
decreases by at least one, which corresponds to an inner loop of $$O(N)$$. 
Space Complexity: $$O(N^2)$$. The answer could be up to $$O(N^2)$$ in size, as justified in our answer to Approach #1.
Approach 3: Reduction to TwoSum, Multiplicity Variation [Accepted]
Intuition
What makes this problem hard is having to deal with repeated values in the input and output. This suggests that we instead work with unique values, and keep a count of their multiplicity on the side. For example, instead of working with an array where 19 occurs 4 times, we will work with a structure where 19 appears once, and we also know it has a count of 4 in the initial array.
The benefit of this approach is that every candidate answer under consideration is unique. The drawback is that our logic and casework becomes more complicated.
Algorithm
Let A
be the given array, count[x]
be the number of times x
appears in A
, and keys
be a sorted list of unique values in A
.
As before, for each unique value x = keys[i]
in A
, we would like to know all pairs (y, z)
(y = keys[j], z = keys[k]
) with x <= y <= z
so that x + y + z == 0
. What makes this tricky is that x
, y
, and z
could be the same value. That means, instead of $$i < j < k$$, we are considering $$i \leq j \leq k$$.
Whenever we have keys[i] + keys[j] + keys[k] == 0
, we need to check whether there were enough elements in A
to actually make this sum. For example, if we have A = [2, 1]
, then keys = [2, 1]
, but we can't make zero. However, A = [2, 1, 1]
with keys = [2, 1]
can make zero. So we have to look at our count
carefully.
When say, i == j
or j == k
, then we used keys[j]
twice, and we need count[keys[j]] >= 2
. When i == j == k
, then we use keys[j]
three times, and we need count[keys[j]] >= 3
. It's impossible to have i != j
and i == k
, so these are all the cases.
Python
class Solution(object):
def threeSum(self, A):
count = collections.Counter(A)
keys = sorted(count)
def twosum(i, target):
#all twoelements in keys[i:] summing to target
j, k = i, len(keys)  1
while j <= k:
if keys[j] + keys[k] < target:
j += 1
elif keys[j] + keys[k] > target:
k = 1
else:
if count[keys[j]] >= 1 + (i==j) + (j==k):
yield keys[j], keys[k]
j += 1
k = 1
ans = []
for i, x in enumerate(keys):
for y, z in twosum(i, x):
ans.append((x, y, z))
return ans
Complexity Analysis
 $$O(N^2)$$ time and space complexity. The analysis is the same as in Approach #2.