3Sum

1. The obvious way

   Three nested loops with a set of results: O(n³).

2. The key insight

   Sort. For each first number (skipping repeats) search the numbers to its right for a pair that cancels it, using the two-pointer sweep from Two Sum II. After a hit, move both pointers inward and skip equal values so each triplet is reported once. O(n²) overall.

3. The algorithm
   1. Sort the numbers.
   2. Pick a first number. Same as the previous first number? Skip it.
   3. Put one pointer just after it, one at the end. Add the three. Too small: left pointer right. Too big: right pointer left.
   4. Zero? Record the triplet and move on, skipping equal values.

Watch it run

found: none

def three_sum(nums):
    nums.sort()
    triplets = []
    for first in range(len(nums) - 2):
        if first > 0 and nums[first] == nums[first - 1]:
            continue                                    # same first number as before
        left, right = first + 1, len(nums) - 1
        while left < right:
            total = nums[first] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                triplets.append([nums[first], nums[left], nums[right]])
                left += 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1                           # skip equal second numbers
    return triplets

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.