> For the complete documentation index, see [llms.txt](https://programming.arora-aditya.com/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://programming.arora-aditya.com/leetcode/array/15.-3sum.md).

# 15. 3Sum

https\://leetcode.com/problems/3sum/

The problem requires us to find all the set of 3 numbers such that they all add up to 0

### Approach 1: Nested Loops

The most naive solution is to try every combination of 3 numbers to see if they add up to zero, and store them in `res` if they do, else continue looping. In the end, `res` will have all the numbers that add up to 0 i.e. our answer

```python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # https://leetcode.com/problems/3sum/
        res = set()
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                for k in range(j+1, len(nums)):
                    if nums[i] + nums[j] + nums[k] == 0:
                        res.add(tuple(sorted([nums[i], nums[j], nums[k]])))
        return list(map(list, res))
```

Since we are using three nested loops to iterate over all the combinations, we are going to have a time complexity of n\*n\*n which will blow up for large arrays, and that is what the leetcode submission results in too (**TimeLimitExceeded**: passes 311/313 test cases, and fails on the large testcases) 

> **Time Complexity:** *O(n^3) where n is the length of the array* 
>
> **Space Complexity:** *O(1)*

### Approach 2: Target method

The strategy is to basically iterate over the entire array, and basically treat each number as a target for the other numbers to add and cancel out.

We can use linear search to find the target pair of numbers, and to simplify this search we can sort the array first.

To avoid duplicate targets, we will only treat the first copy of every number as a target and if a number equals the one at the previous index, then we can simply continue iterating over the array till we get a new target.

```python
class Solution(object):
    def threeSum(self, nums):
        res = []
        nums.sort()
        length = len(nums)
        for i in range(length-2):
            if nums[i] > 0: 
                break
            if i > 0 and nums[i] == nums[i-1]: 
                continue 

            l, r = i+1, length-1 
            while l < r:
                total = nums[i]+nums[l]+nums[r]

                if total < 0:
                    l += 1
                elif total > 0:
                    r -= 1
                else: 
                    res.append([nums[i], nums[l], nums[r]])
                    while l < r and nums[l] == nums[l+1]:
                        l += 1
                    while l < r and nums[r] == nums[r-1]:
                        r -= 1
                    l +=1
                    r -= 1
        return res
```

We can keep track of 2 indices, `l` and `r` if the `total = nums[i] + nums[l] + nums[r]` is greater than 0 we know we have to reduce our total so reduce the upper bound `nums[r]` by decrementing `r`, and if our total is less than 0 we increment the lower bound `l`&#x20;

> **Time Complexity:** *O(nlogn + n^2) where n is the length of the array*&#x20;
>
> **Space Complexity:** *O(1) \[no extra space except res used]*