# 15. 3 Sum

## Description

See <https://leetcode.com/problems/3sum/>

## Solution

This builds off of the [Two Sum](/cs-theory-and-problems/problems/leetcode/1.-two-sum.md) problem that uses the two pointer solution. I found these posts helpful to understand 3Sum:&#x20;

* <https://en.wikipedia.org/wiki/3SUM>
* <https://fizzbuzzed.com/top-interview-questions-1/>

Below are two implementations. The first uses a set to handle duplicates results. The other handles duplicates results by skipping them using the two pointer trick.

### Set solution

The first step is to sort the array. This will let us skip duplicate numbers in the nums array. We don't need to process duplicate numbers as we already found the solution(s) for that number. The sorted array will also allow us to look for solution items.

We want to find three numbers that sum to zero: a + b + c = 0. We can set 'a' to be the current item when iterating through the array.  Then we need to find b,c that when added with 'a' will equal zero. Since 'a' is fixed for the iteration, we can then use a start and an end pointer to scan the rest of the array to see if there are b,c values that will satisfy the condition.

If the result of a + b + c > 0 then the end pointer will be decremented in an attempt to find zero in the next iteration. If the sum in less than zero then the start pointer will be incremented.

When a solution is found, a + b + c = 0, then we add it to the set. We continue looking in that iteration for other b,c that may satisfy the condition.

**Example**:

nums = \[-1,0,1,2,-1,-4]

nums sorted = \[-4, -1, -1, 0, 1, 2]

The below table shows the first two iterations. The first iteration does not find a solution. The second iteration finds a solution.

| iteration | a  | start index | end index | b  | c |
| --------- | -- | ----------- | --------- | -- | - |
| 0         | -4 | 1           | 5         | -1 | 2 |
|           |    | 2           | 5         | -1 | 2 |
|           |    | 3           | 5         | 0  | 2 |
|           |    | 4           | 5         | 1  | 2 |
| 1         | -1 | 2           | 5         | -1 | 2 |

```python
 class Solution:   
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = set()
        for i in range(len(nums) - 2):
            a = nums[i]
            # skip duplicate numbers
            if i > 0 and a == nums[i - 1]:
                continue
            start = i + 1
            end = len(nums) - 1
            while start < end:
                b = nums[start]
                c = nums[end]
                if a + b + c == 0:
                    result.add((a, b, c))
                    start += 1
                    end -= 1
                elif a + b + c > 0:
                    end -= 1
                else:
                    start += 1
        return list(map(list, result))

```

### Skipping "Two pointer trick" Solution

The main algorithm is the same as above. However, instead of using a set to store the result, an array is used to store the result. Duplicate results are avoided by skipping duplicate numbers. In the outer loop we skip duplicate numbers. But in the inner while loop we can skip duplicate numbers as well. We do this by incrementing the start pointer past any duplicates. We also decrement the end pointer before any duplicates as well.

**Example**

nums = \[-1,0,1,2,-1,-&#x34;**,** 2]

nums sorted = \[-4, -1, -1, 0, 1, 2, 2]

In the second iteration, when the index is 1, and a = -1, the algorithm will find a solution of \[-1, -1, 2]. In order to not get a duplicate result, start will increment past the second -1. The start index will be 3. The end pointer will decrement to before the first 2.The end index will be 4.

```python
class Solution:

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        for i in range(len(nums) - 2):
            a = nums[i]
            # skip duplicate numbers
            if i > 0 and a == nums[i - 1]:
                continue
            start = i + 1
            end = len(nums) - 1
            while start < end:
                b = nums[start]
                c = nums[end]
                summ = a + b + c
                if summ == 0:
                    result.append([a, b, c])
                    # the while loops below are what lets us use an array rather than a set to store the result (since
                    # duplicates are not allowed). Here duplicate numbers are skipped by.
                     while start < end and b == nums[start]:
                        start += 1
                    while start < end and c == nums[end]:
                        end -= 1
                elif summ > 0:
                    end -= 1
                else:
                    start += 1

        return result

```

## Test Cases

| input                            | result                       |
| -------------------------------- | ---------------------------- |
| \[-1, 0, 1, 2, -1, -4]           | \[\[-1, -1, 2], \[-1, 0, 1]] |
| \[]                              | \[]                          |
| \[0]                             | \[]                          |
| \[-25, -10, -7, -3, 2, 4, 8, 10] | \[-10, 2, 8], \[-7, -3, 10]  |


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://monica-granbois.gitbook.io/cs-theory-and-problems/problems/leetcode/15.-3-sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.