Interview
Interview Guide
Coding Problems List
Problems

# 3Sum

## Problem

Given an array `S` of `n` integers, are there elements `a`, `b`, `c` in `S` such that `a + b + c = 0`? Find all unique triplets in the array which gives the sum of zero.

### Example

For example, given array `S = {-1 0 1 2 -1 -4}`, A solution set is:

``````(-1, 0, 1)
(-1, -1, 2)
``````

### Note

Elements in a triplet `(a,b,c)` must be in non-descending order. (ie, `a ≤ b ≤ c`)

The solution set must not contain duplicate triplets.

## Solution

Use 3 pointers:

• Sort the array.
• for each position `i` in the array:
• skip if it is the same as the previous value (`num[i] == num[i - 1]`) to make sure the triplets are unique.
• create a `left` pointer at `i + 1` and a `right` pointer at `n - 1`.
• if the sum of `i`, `left` and `right` is `0`, add the triplet to the result.
• if the sum is less than `0`, move the `left` pointer to the right; otherwise move the `right` pointer to the left.
• return the result.

Complexity: The sort takes `O(n log n)` and the loop takes `O(n^2)`, so the overall is `O(n^2)`. Extra space is constant `O(1)`.