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³) 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²logN) = O(N²logN)
  • N² as before, the last O(N) becomes O(logN)
• 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²). i takes O(N) time and the nested while l < r takes O(N) time.
• Space: O(N)

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.