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
We do exactly as directed.
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
- Time: O(N3) for i, j, k all iterating in range of O(N)
- Space: O(1). Note that we do not consider
ansin space complexity as it is a requirement of the answer.
1. 3Sum: Optimization 1: Binary Search
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.
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+ N2logN) = O(N2logN)
- N2 as before, the last O(N) becomes O(logN)
- Space: O(N)
2. 3Sum: Optimization 2: Two pointers
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.).
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
Sorting again done using Timsort.
- Time: O(N2).
itakes O(N) time and the nested
while l < rtakes O(N) time.
- Space: O(N)
January 24, 2022
January 20, 2022
January 15, 2022