# 3Sum | LeetCode | Solution Explained

LeetCode 15. 3Sum is a very popular interview question. I explain the brute-force solution, binary search optimization and the two pointer approach. Problem Link.

## 0. 3Sum: Brute-force

### 0.0. Observations

We do exactly as directed.

### 0.1. Code

class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: n = len(nums) ans = set() for i in range(n): for j in range(i+1, n): for k in range(j+1, n): if nums[i]+nums[j]+nums[k] == 0: ans.add(tuple(sorted([nums[i],nums[j],nums[k]]))) return ans

### 0.2. Complexity

- Time: O(N
^{3}) for i, j, k all iterating in range of O(N) - Space: O(1). Note that we do not consider
`ans`

in space complexity as it is a requirement of the answer.

## 1. 3Sum: Optimization 1: Binary Search

### 1.0. Observations

Yes, the title says binary search. But, how do we think about it?

In the 3 Sum problem, our goal is to return triples. However, it does not matter in what *ordering* we return the answer. The only constraint is, it should be a set.

Now, since the ordering of the answer does not matter, does the ordering of the input matter? No again! Whatever be the order of nums, we can always get the set of answers.

This hints at one possible path: *sorting*. Sorting unlocks some nice properties that we can exploit – like, you guessed it, binary search.

### 1.1. Code

Reference for binary search: https://docs.python.org/3/library/bisect.html

from bisect import bisect_left class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: nums.sort() n = len(nums) ans = set() for i in range(n): for j in range(i+1, n): x = -nums[i]-nums[j] k = bisect_left(nums, x, lo=j+1) if k != len(nums) and nums[k] == x: ans.add(tuple(sorted([nums[i],nums[j],nums[k]]))) return ans

### 1.2. Complexity Analysis

Python uses Timsort to sort internally. The worst case space time complexities are given as such:

- Time: O(NlogN+ N
^{2}logN) = O(N^{2}logN)- N
^{2}as before, the last O(N) becomes O(logN)

- N
- Space: O(N)

## 2. 3Sum: Optimization 2: Two pointers

### 2.0. Observations

Finally we come to two pointers. Two pointers is a famous technique. It can be understood well in comparison to binary search. Just like how binary search exploits the properties of *sorted* array, two pointers does the same.

The big differences are in the goals – binary search searches for a single element and two pointers approach finds a *pair* of elements.

I go over an example case in my video solution (links above). Here is an intuitive proof: Proving that two pointer approach works(Pair sum ques.).

### 2.1. Code

class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: nums.sort() n = len(nums) ans = set() for i in range(n): l, r = i+1, n-1 target = -nums[i] while l < r: if nums[l]+nums[r] < target: l += 1 elif nums[l]+nums[r] > target: r -= 1 else: ans.add(tuple(sorted([nums[i],nums[l],nums[r]]))) l += 1 r -= 1 return ans

### 2.2. Complexity

Sorting again done using Timsort.

- Time: O(N
^{2}).`i`

takes O(N) time and the nested`while l < r`

takes O(N) time. - Space: O(N)

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Reverse integer | InterviewBit | LeetCode | Solution Explained

January 24, 2022