LeetCode #15: 3Sum — Master Sorting, Two Pointers and Duplicate Handling

LeetCode Problem: 15 — 3Sum
Difficulty: Medium
Topics: Array, Sorting, Two Pointers
Pattern: Sorting + Two Pointers
Series: LeetCode Interview Preparation — From Beginner to Expert

Some LeetCode problems teach you a data structure.

Some teach you an algorithm.

And some teach you how to combine patterns.

3Sum is one of those problems.

If you've already understood Two Sum and Two Sum II, this problem is the perfect next step.

The key idea is:

3Sum
=
Fix one number
+
Solve Two Sum using Two Pointers

But there is another challenge:

How do we avoid duplicate answers?

That makes 3Sum an extremely valuable interview problem.

The Problem

Given an integer array:

nums

return all unique triplets:

[a, b, c]

such that:

a + b + c = 0

The solution must not contain duplicate triplets.

Example 1

Input:

[−1, 0, 1, 2, −1, −4]

Output:

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

Notice that:

[-1, 0, 1]

and:

[0, -1, 1]

represent the same triplet.

We only return one of them.

Example 2

Input:

[0, 1, 1]

There is no triplet whose sum is zero.

Output:

[]

Example 3

Input:

[0, 0, 0]

The answer is:

[[0, 0, 0]]

Not:

[
    [0, 0, 0],
    [0, 0, 0],
    [0, 0, 0]
]

Duplicate handling is a major part of this problem.

First Thought: Brute Force

The most obvious solution is to choose every possible combination of three numbers.

We could use three loops:

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:
                ...

This checks every possible triplet.

The number of combinations is approximately:

n³

Therefore:

Time = O(n³)

That's too slow for large arrays.

But brute force is still useful.

Why?

Because during an interview, you should first establish the straightforward solution before optimizing it.

Can We Improve It?

Yes.

Think back to Two Sum II.

We learned that a sorted array allows us to use:

Two Pointers

So what if we sort the array?

For example:

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

becomes:

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

Now we can exploit the ordering.

The Core Idea

Pick one number.

Let's call it:

nums[i]

Then our problem becomes:

nums[i] + nums[left] + nums[right] = 0

Rearrange:

nums[left] + nums[right] = -nums[i]

That's simply a Two Sum problem.

So:

3Sum
↓
Fix one number
↓
Find two numbers
↓
Use Two Pointers

This is the key insight.

Visualizing the Algorithm

Suppose:

nums = [-4, -1, -1, 0, 1, 2]

Fix:

i = 0
nums[i] = -4

Now we need:

left + right = 4

Pointers:

i
↓
[-4, -1, -1, 0, 1, 2]
     ↑              ↑
    left           right

Calculate:

-1 + 2 = 1

Too small.

Move:

left++

Now:

-1 + 2 = 1

Still too small.

Move again:

0 + 2 = 2

Still too small.

Move again:

1 + 2 = 3

Still too small.

No solution for -4.

Then move to the next fixed number.

Let's Try -1

Now:

i = 1
nums[i] = -1

We need:

left + right = 1

Start:

[-4, -1, -1, 0, 1, 2]
     ↑       ↑     ↑
     i      left  right

Calculate:

-1 + 2 = 1

Therefore:

-1 + -1 + 2 = 0

Found:

[-1, -1, 2]

Continue searching.

Move both pointers:

left++
right--

Now:

0 + 1 = 1

Therefore:

-1 + 0 + 1 = 0

Found:

[-1, 0, 1]

The Algorithm

The complete strategy is:

Step 1

Sort the array.

nums.sort()

Step 2

Loop through every possible first element.

for i in range(len(nums)):

Step 3

Skip duplicate values for i.

if i > 0 and nums[i] == nums[i - 1]:
    continue

Step 4

Create two pointers:

left = i + 1
right = len(nums) - 1

Step 5

Calculate:

total = nums[i] + nums[left] + nums[right]

Step 6

If:

total < 0

move:

left += 1

If:

total > 0

move:

right -= 1

If:

total == 0

store the triplet and move both pointers.

Python Solution

def threeSum(nums):
    nums.sort()
    result = []

    n = len(nums)

    for i in range(n - 2):

        # Skip duplicate first values
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left = i + 1
        right = n - 1

        while left < right:
            total = nums[i] + nums[left] + nums[right]

            if total < 0:
                left += 1

            elif total > 0:
                right -= 1

            else:
                result.append([
                    nums[i],
                    nums[left],
                    nums[right]
                ])

                left += 1
                right -= 1

                # Skip duplicate left values
                while left < right and nums[left] == nums[left - 1]:
                    left += 1

                # Skip duplicate right values
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1

    return result

Dry Run

Let's take:

nums = [-1, 0, 1, 2, -1, -4]

First sort:

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

Iteration 1

i = 0
nums[i] = -4

Pointers:

left = 1
right = 5

Values:

-4 + -1 + 2 = -3

Too small.

Move left:

left = 2

Now:

-4 + -1 + 2 = -3

Still too small.

Continue.

Eventually:

left = 4
right = 5

Then:

-4 + 1 + 2 = -1

Still no solution.

Iteration 2

i = 1
nums[i] = -1

Pointers:

left = 2
right = 5

Calculate:

-1 + -1 + 2 = 0

Found:

[-1, -1, 2]

Move both:

left++
right--

Now:

left = 3
right = 4

Calculate:

-1 + 0 + 1 = 0

Found:

[-1, 0, 1]

Iteration 3

Now:

i = 2
nums[i] = -1

But:

nums[2] == nums[1]

So we skip it.

Why?

Because we already considered all combinations starting with -1.

If we process the second -1 again, we would generate duplicate triplets.

This is one of the most important parts of the problem.

Duplicate Handling

Suppose the sorted array is:

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

There may be many ways to select the same values.

But the output should contain each unique triplet only once.

There are two places where duplicates matter.

Duplicate #1: The First Number

We use:

if i > 0 and nums[i] == nums[i - 1]:
    continue

This prevents:

i = 1

from repeating the work already done at:

i = 0

when both values are equal.

Duplicate #2: Left and Right Pointers

Suppose we find:

[-1, 0, 1]

and there are multiple zeros or ones afterward.

We need to skip repeated values.

That's why we use:

while left < right and nums[left] == nums[left - 1]:
    left += 1

and:

while left < right and nums[right] == nums[right + 1]:
    right -= 1

Why Do We Move Both Pointers After Finding a Triplet?

Suppose:

total == 0

We've found a valid combination.

Could we simply move left?

Yes, but we'd need to reason carefully about the next possibilities.

The clean approach is:

left += 1
right -= 1

We've already used both values in the current valid combination.

Then we skip duplicates.

This keeps the algorithm clean and efficient.

Why Sorting Is So Important

Sorting gives us two major advantages.

Advantage 1: Two Pointers

We can determine which pointer to move based on whether the sum is too small or too large.

Advantage 2: Duplicate Detection

Duplicates become adjacent:

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

Now they're easy to skip.

Without sorting, duplicate handling becomes much more complicated.

Complexity

Sorting costs:

O(n log n)

The outer loop runs:

O(n)

For each fixed element, the two pointers together scan at most:

O(n)

Therefore:

Total = O(n²)

So:

Time Complexity

O(n²)

Extra Space

Ignoring the output:

O(1)

depending on the sorting implementation.

In Python, sort() uses additional implementation-dependent memory, but algorithmically the two-pointer portion uses constant extra space.

The output itself can contain many triplets, so output storage is separate from auxiliary space.

Why We Don't Need Three Loops

The brute-force solution does:

i
j
k

which gives:

O(n³)

Our optimized solution does:

i
    ↓
left → ← right

For each i, the two pointers scan the remaining array in linear time.

Therefore:

O(n × n)
=
O(n²)

That's a huge improvement.

A Powerful Interview Pattern

The most important thing to remember isn't the exact code.

Remember this transformation:

3Sum
 ↓
Sort
 ↓
Fix one element
 ↓
Two Sum
 ↓
Two Pointers

This is a reusable strategy.

When you see:

Find three numbers satisfying a condition.

Ask:

Can I fix one number and turn the remaining problem into Two Sum?

That question can unlock many problems.

Early Optimization

Because the array is sorted, we can sometimes stop early.

Suppose:

nums[i] > 0

Remember that the array is sorted.

If the first number is already positive, then every number after it is also positive.

Therefore:

positive + positive + positive > 0

It can never equal zero.

So we can safely:

if nums[i] > 0:
    break

An optimized version becomes:

def threeSum(nums):
    nums.sort()
    result = []

    for i in range(len(nums) - 2):

        if nums[i] > 0:
            break

        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left = i + 1
        right = len(nums) - 1

        while left < right:
            total = nums[i] + nums[left] + nums[right]

            if total < 0:
                left += 1

            elif total > 0:
                right -= 1

            else:
                result.append(
                    [nums[i], nums[left], nums[right]]
                )

                left += 1
                right -= 1

                while left < right and nums[left] == nums[left - 1]:
                    left += 1

                while left < right and nums[right] == nums[right + 1]:
                    right -= 1

    return result

The asymptotic complexity remains:

O(n²)

but this can reduce unnecessary work.

Common Mistake #1: Forgetting to Sort

Without sorting, the two-pointer logic doesn't work correctly.

Always start with:

nums.sort()

Common Mistake #2: Not Skipping Duplicate i

This:

for i in range(n):

isn't enough.

You need:

if i > 0 and nums[i] == nums[i - 1]:
    continue

Otherwise duplicate triplets can appear.

Common Mistake #3: Skipping Duplicates Before Finding a Solution

Be careful with pointer movement.

A simple and safe order is:

Find valid triplet
↓
Add it
↓
Move left/right
↓
Skip duplicates

Don't accidentally skip a valid combination.

Common Mistake #4: Returning as Soon as You Find One Triplet

The problem asks for all unique triplets.

So finding:

[-1, -1, 2]

doesn't mean you're finished.

You must continue searching.

Common Mistake #5: Thinking the Array Must Already Be Sorted

Unlike Two Sum II, the original input here does not need to be sorted.

We sort it ourselves:

nums.sort()

That's part of the algorithm.

Common Mistake #6: Using a Set Without Understanding the Pattern

A Hash Set can also be used to construct solutions, but if you are asked about optimal time and duplicate handling, the sorted + two-pointer approach is usually the cleanest standard solution.

More importantly, you should understand why it works.

Interview Follow-Up Questions

Once you've solved 3Sum, interviewers can easily extend it.

Follow-Up 1: 3Sum Closest

Instead of finding:

sum == 0

find the triplet whose sum is closest to a target.

This is:

LeetCode #16 — 3Sum Closest

The same sorting + two-pointer pattern applies.

Follow-Up 2: 4Sum

Find four numbers whose sum equals a target.

The pattern becomes:

Fix first
+
Fix second
+
Two Pointers

This leads to:

LeetCode #18 — 4Sum

Follow-Up 3: 3Sum With a Different Target

Instead of:

a + b + c = 0

find:

a + b + c = target

The algorithm remains almost identical.

Follow-Up 4: Count Triplets

Instead of returning the triplets, count how many valid combinations exist.

Now you need to carefully handle duplicates and indices.

How to Recognize This Pattern

When you encounter a problem containing:

• Three numbers
• A target sum
• Unique combinations
• An array
• Pair relationships
• Duplicate values
• A requirement for better than O(n³)

Think:

Sort
↓
Fix one
↓
Two Pointers

This should become an interview reflex.

The Pattern Generalizes

This is where your LeetCode pattern library starts becoming powerful.

Two Sum

Hash Map

Two Sum II

Sorted Array
+
Two Pointers

3Sum

Sort
+
Fix One
+
Two Pointers

4Sum

Sort
+
Fix Two
+
Two Pointers

You can see the progression.

We're not learning completely unrelated problems.

We're building on previous patterns.

Interview Explanation Template

If the interviewer asks:

"Explain your approach."

A strong answer would be:

"I'll first sort the array. Then I'll iterate through each element as the first element of the triplet. For every fixed element, I'll use two pointers on the remaining sorted portion to find two values whose sum is the negative of the fixed value. If the total is too small, I'll move the left pointer forward; if it's too large, I'll move the right pointer backward. After finding a valid triplet, I'll move both pointers and skip duplicates. Sorting takes O(n log n), and the nested iteration with two pointers takes O(n²), so the overall complexity is O(n²)."

That's the kind of explanation interviewers want to hear.

Interview Cheat Sheet

Problem:
Find all unique triplets
whose sum equals zero.

First:
Sort the array.

For each i:

    Skip duplicate nums[i]

    left = i + 1
    right = n - 1

    while left < right:

        total =
            nums[i] +
            nums[left] +
            nums[right]

        if total < 0:
            left++

        elif total > 0:
            right--

        else:
            save triplet

            left++
            right--

            skip duplicates

Optimization:
If nums[i] > 0:
    break

Complexity:
Time: O(n²)
Extra Space: O(1)
excluding output

Practice Challenges

Don't stop at the LeetCode solution.

Try these variations.

Challenge 1

Solve 3Sum with a custom target instead of zero.

Challenge 2

Find the triplet whose sum is closest to a target.

Challenge 3

Find all triplets whose sum equals 10.

Challenge 4

Find the number of unique triplets whose sum equals zero.

Challenge 5

Solve 4Sum.

Challenge 6

Given an array and target T, determine whether any three numbers add up to T.

Challenge 7

Given an array, find three numbers with the maximum possible sum below a target.

These variations will help you understand the pattern rather than memorize one solution.

What You Should Learn From LeetCode #15

There are actually four lessons hidden inside this one problem.

Lesson 1

Sorting can unlock algorithms.

Lesson 2

A difficult problem can sometimes be reduced to a simpler problem you've already solved.

3Sum → Two Sum

Lesson 3

Two Pointers can reduce an O(n³) brute-force approach to O(n²).

Lesson 4

Duplicate handling is part of algorithm design—not an afterthought.

Final Takeaway

3Sum is one of the most important stepping stones in your LeetCode journey.

The solution isn't about memorizing this:

left += 1
right -= 1

The real skill is recognizing the structure:

Three numbers
      ↓
Fix one
      ↓
Remaining problem becomes Two Sum
      ↓
Sorted array
      ↓
Two Pointers
      ↓
O(n²)

And there's an even bigger lesson.

When an interview problem looks complicated, don't immediately search for a completely new algorithm.

Ask:

"Can I reduce this problem to something I already know?"

That's exactly what we did here.

We took:

3Sum

and reduced it to:

Two Sum + Two Pointers

That way of thinking is one of the most valuable skills you can develop for software engineering interviews.