3Sum

Table of Contents +

3Sum is a favorite interview question. It builds right on top of Two Sum. The new twist is finding three numbers instead of two. And you must skip duplicate answers. The interviewer wants to see if you can mix sorting with the two-pointer trick and handle the messy edge cases cleanly.

🎯 The Problem

You get an array of numbers. Find every group of three numbers that adds up to zero. The rules:

  • A group of three values is called a triplet.
  • Return all triplets whose sum is zero.
  • Every triplet must be unique. No triplet may repeat.
  • The order of the triplets does not matter.

In the array [-1, 0, 1, 2, -1, -4], the triplets that add to zero are [-1, -1, 2] and [-1, 0, 1]. Notice -1 appears twice, so we have to be careful not to print the same triplet again.

Input:  nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]


Explanation: -1 + -1 + 2 = 0
             -1 +  0 + 1 = 0

Here is the array before we sort it. The numbers are in a random order.

-1

0

1

2

-1

-4

🐢 Approach 1: Triple Loop (Brute Force)

Try every group of three.

The idea:

  • Pick a first number, a second after it, a third after that.
  • Add the three. If they make zero, you found a triplet.

How it works:

  • Three nested loops over the array.
  • After collecting triplets, remove the duplicates.

Why it is weak:

  • Three loops mean about n times n times n steps. Time is O(n³).
  • Removing duplicate triplets costs even more.
  • Far too slow for an interview. Drop it fast.

Here is the brute-force code for that idea:

three_sum_brute_force.py
def three_sum(nums):
    result = set()
    n = len(nums)
    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:
                    result.add(tuple(sorted((nums[i], nums[j], nums[k]))))
    return [list(triplet) for triplet in sorted(result)]

⚡ Approach 2: Sort Then Two Pointers (Best)

The idea in one line: sort the array, fix one anchor, then solve Two Sum on the rest with two pointers.

The idea:

  • Sort the array from small to large first.
  • Sorting puts equal numbers next to each other, so skipping duplicates is easy.
  • Fix one number at a time. Call it the anchor.
  • For each anchor, find two more numbers that add to -anchor.

How it works:

  • Set a left pointer just after the anchor. Set a right pointer at the end.
  • Add the anchor, the left value, and the right value.
  • Sum is zero: save the triplet. Move both pointers in. Skip equal neighbors.
  • Sum too small: move the left pointer right for a bigger number.
  • Sum too big: move the right pointer left for a smaller number.
  • Skip the anchor itself if it equals the number before it.

Why it is fast:

  • Each anchor does one O(n) two-pointer scan.
  • Outer loop times inner scan is O(n²). A huge win over O(n³).
  • No extra memory beyond the output.

Here is the dry-run after sorting [-4, -1, -1, 0, 1, 2] with the anchor at -1.

anchor=-1, left=0, right=2, sum=-1+0+2=1 too big, move right left

anchor=-1, left=0, right=1, sum=-1+0+1=0 found [-1,0,1]

move both pointers inward, they meet, stop

next anchor handled the same way

Steps to Solve

  1. Sort the array from small to large.
  2. Loop one anchor index from the start. Skip it if it equals the number before it.
  3. Set a left pointer right after the anchor and a right pointer at the end.
  4. Add the three numbers. If the sum is zero, save the triplet, then move both pointers and skip equal neighbors.
  5. If the sum is too small, move left right. If it is too big, move right left.
  6. Stop the inner loop when the pointers meet. Move to the next anchor.

This Python version sorts the list then walks two pointers for every anchor.

three_sum.py
def three_sum(nums):
    nums.sort()                       # sort small to large
    result = []
    n = len(nums)
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue                  # skip the same anchor value
        left = i + 1
        right = n - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1         # skip duplicate left values
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1        # skip duplicate right values
            elif total < 0:
                left += 1             # need a bigger number
            else:
                right -= 1            # need a smaller number
    return result




nums = [-1, 0, 1, 2, -1, -4]
for triplet in three_sum(nums):
    print(triplet)

The output of the above code will be:

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

Let us walk through the Python version line by line. The tricky parts are the duplicate skips.

nums.sort() sorts the list in place. After this the array is [-4, -1, -1, 0, 1, 2]. Equal numbers now sit next to each other. That is what makes skipping duplicates simple.

for i in range(n - 2): picks each anchor. We stop at n - 2 because we still need two numbers after the anchor.

if i > 0 and nums[i] == nums[i - 1]: continue skips an anchor that equals the one before it. Without this line we would print the same triplet twice. This is the first duplicate guard.

left = i + 1 and right = n - 1 set the two pointers. The left pointer sits right after the anchor. The right pointer sits at the very end.

total = nums[i] + nums[left] + nums[right] adds all three numbers. This sum decides what we do next.

if total == 0: means we found a triplet. We save it with result.append. Then we move left up and right down. The two inner while loops skip any neighbor that is equal. That stops repeated triplets from the same anchor. This is the second duplicate guard.

elif total < 0: means the sum is too small, so left += 1 reaches for a bigger number. else: means too big, so right -= 1 reaches for a smaller number. Each move deletes a value that cannot help, so the scan never wastes a step.

⏱️ Time and Space Complexity

The brute force is O(n³) because of three nested loops. The optimal way sorts once in O(n log n), then for each anchor it does an O(n) two-pointer scan. That outer loop times inner scan is O(n²). The extra space is just the output, so the working memory is O(1) beyond that.

Approach Time Complexity Space Complexity
Brute force (triple loop) O(n³) O(1)
Sort then two pointers O(n²) O(1)

Tip

3Sum is really Two Sum wrapped in one extra loop. Say that out loud in the interview. Then the only new thing to explain is how you skip duplicate triplets.

🧩 Key Takeaways

  • ✅ Sort the array first. It groups equal numbers and unlocks two pointers.
  • ✅ Fix one anchor, then solve Two Sum on the rest with a left and right pointer.
  • ✅ Skip an anchor that equals the previous one to avoid repeat triplets.
  • ✅ After saving a triplet, skip equal neighbors on both sides.
  • ✅ Sorting plus two pointers brings the time from O(n³) down to O(n²).

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    What does the 3Sum problem ask you to find?

    Why: 3Sum asks for every unique group of three numbers whose sum is zero.

  2. 2

    Why do we sort the array before scanning?

    Why: Sorting puts equal values next to each other and enables the two-pointer move per anchor.

  3. 3

    After finding a valid triplet, why do we skip equal neighbors?

    Why: Skipping equal neighbors stops the same triplet from being recorded again.

  4. 4

    What is the time complexity of the sort plus two-pointer solution?

    Why: One outer loop over anchors times an O(n) inner scan gives O(n²), which dominates the O(n log n) sort.

Score: 0 / 4

🚀 What’s Next?

Previous Two Sum II - Input Array Is Sorted Next Container With Most Water