Week 1 · Two Pointers

3Sum

Return all unique triplets whose values sum to zero. This is Two Sum with an outer anchor and duplicate control.

Medium Two Pointers Week 1 Practice runner

Frame the problem

Triplets must be unique by value.
Output order is not important.
The same index cannot be reused within a triplet.

1. Reveal example inputs and outputs

Example 1

Input:

three_sum([
  -1,
  0,
  1,
  2,
  -1,
  -4
])

Output:

[
  [
    -1,
    -1,
    2
  ],
  [
    -1,
    0,
    1
  ]
]

Example 2

Input:

three_sum([
  1,
  2,
  -2,
  -1
])

Output:

[]

2. Brute force first

What is the O(n^3) enumeration? After sorting, how can the inner two values become a two-pointer problem?

3. Reveal the insight ladder

Sort the array.
Fix one anchor value.
Use left and right pointers to find pairs summing to -anchor.
Skip duplicate anchors and duplicate pointer values after recording an answer.

4. Dry run before code

nums = [-1, 0, 1, 2, -1, -4] sorts to [-4, -1, -1, 0, 1, 2].
Anchor -1 can pair with -1 and 2, then 0 and 1.
Duplicate anchor -1 is skipped the second time.

5. Reveal final Python solution

def three_sum(nums):
    nums.sort()
    result = []
    for i, value in enumerate(nums):
        if i > 0 and value == nums[i - 1]:
            continue
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = value + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                result.append([value, nums[left], nums[right]])
                left += 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
    return result

Complexity: Time O(n^2), space O(1) beyond sorting/output depending on sort implementation.

Interview narration

Sorting gives duplicate control and monotonic pointer movement.
For each anchor, the inner problem is a two-sum search for the negated anchor.
Skipping duplicates after recording prevents repeated triplets.

Common traps

Forgetting to skip duplicate anchors.
Returning duplicate triplets for repeated values.
Moving both pointers on every comparison instead of only the side dictated by the sum.

Follow-up drills

1. How would you adapt this to 4Sum?

Sort, fix two anchors, and run the same two-pointer search for the remaining target while skipping duplicates at each anchor level.

2. Why not use a hash set for each anchor?

You can, but sorting makes uniqueness and duplicate skipping easier to explain and usually cleaner in interviews.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.