3Sum

Related: Two Sum Two Sum II- Input Array Is Sorted

TARGET DECK: Leetcode FILE TAGS:

Intuition

• The main trick in this problem is that you use Two Sum II- Input Array Is Sorted with a fixed i going from left to right.
• If the sum of the j and the k pointer == -nums[i], then we’re in business since that is the same sum to 0.
• Additionally, to skip duplicates, you can simply not add those results that are already in your result, or you can skip those duplicate indices.

Card

START Basic Front: 3Sum - LeetCode Back: Skip duplicates by moving pointer, and start with a fixed pointer on the left, using Two Sum II- Input Array Is Sorted for the next 2 pointers.

END

Complexity

Runtime

$O(N^2)$, which is better than brute force $N^3$ since you eliminate the need to have to check every possible combination of the three pointers which is N choose 3 == $N^3$.

Space

$O(N)$ if including the res array.

Code

Less Messy

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        res = set()
 
        for i in range(n):
            j, k = i + 1, n - 1
            target = -nums[i]
            while j < k:
                guess = nums[j] + nums[k]
                if guess == target:
                    insertion = tuple([nums[i], nums[j], nums[k]])
                    res.add(insertion)
                    j += 1
                    k -= 1
                elif guess < target:
                    j += 1
                else:
                    k -= 1
 
        return [list(arr) for arr in res]

Messy

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        i = 0
        j = 1
        k = n - 1
        res = []
        while i < n:
	        # Don't have to compute positive i's
            if nums[i] > 0:
                break
                
            j = i + 1
            k = n - 1
            while j < k:
                cur_sum = nums[j] + nums[k]
                if cur_sum == -nums[i]:
                    valid = [nums[i], nums[j], nums[k]]
                    res.append(valid)
                    tmp = nums[j]
                    while j < k and nums[j] == tmp:
                        j += 1
                elif cur_sum < -nums[i]:
                    j += 1
                else:
                    k -= 1
                    
            tmp = nums[i]
            while i < n and nums[i] == tmp:
                i += 1
 
        return res

TLE

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        n = len(nums)
        for i in range(n):
            j = i + 1
            k = n - 1
            while j < k:
                cs = nums[j] + nums[k]
                if cs == -nums[i]:
                    t = [nums[i], nums[j], nums[k]]
                    if t not in res:
                        res.append(t)
                    j += 1
                    k -= 1
                elif cs < -nums[i]:
                    j += 1
                else:
                    k -= 1
 
        return res

Notes

---

References

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