3-sum

3-Sum Problem

https://leetcode.com/problems/3sum extended version of 2-sum.

”Enlightened” Brute Force

table = defaultdict(list)
for i, x in enumerate(nums):
    for j, y in enumerate(nums[i + 1:]):
        j = j + i + 1
        table[x + y].append((i, j))
result = set()
for k, z in enumerate(nums):
    for i, j in table[-z]:
        if j < k:
            result.add(tuple(sorted([nums[i], nums[j], z])))
return list(result)

Still takes too long!

Two-Pointer

• Use sorting and iteration to ensure that duplicates (both in terms of indices and values) are avoided.
• Two-pointer utilized the extra information that the sum is fixed. We may utilize the tricks in 2-sum to further speed up. Alternatively, instead of a linear search, do a binary-search instead.
• Make sure all the info are used in your solution! In this case, we ensured no duplicate indices my enforcing that i < j < k.

Don't Go Too Far

Declarative and Pythonic programming is great, but procedural programming gives you control over details in each step of the iteration!

2-pointer

nums.sort()  # step 1: sort the array
result = []
n = len(nums)
for i in range(n):
    # skip duplicate elements to avoid duplicate triplets
    if i > 0 and nums[i] == nums[i-1]:
        continue
    # use two-pointer technique to find the remaining two elements
    left, right = i + 1, n - 1
    while left < right:
        total = nums[i] + nums[left] + nums[right]
        if total == 0:
            result.append([nums[i], nums[left], nums[right]])
            # Skip duplicate elements
            while left < right and nums[left] == nums[left + 1]:
                left += 1
            while left < right and nums[right] == nums[right - 1]:
                right -= 1
            left += 1
            right -= 1
        elif total < 0:
            left += 1
        else:
            right -= 1
return result