Day 3 of 250: LeetCode 15 Three Sum | Two Pointers Plus Sorting Explained

Building on What We Already Know

On Day 1, we learned the fast slow pointer pattern. On Day 2, we learned how a sorted array enables opposite ends pointer movement. Today, we combine both of those ideas into something more powerful.

LeetCode 15 Three Sum is a problem that trips up a lot of people, not because the logic is fundamentally new, but because it has one extra layer of complexity that requires careful handling: duplicate triplets.

By the end of this post, you will understand exactly how to find all triplets that sum to zero, why sorting is the first move you should always make on this kind of problem, and why duplicate handling is not optional.

Let us get into it.

The Problem Statement

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0. The solution set must not contain duplicate triplets.

Examples:

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

Input:  nums = [0, 1, 1]
Output: []

Input:  nums = [0, 0, 0]
Output: [[0, 0, 0]]

Constraints:

• 3 <= nums.length <= 3000
• -10^5 <= nums[i] <= 10^5

The Core Insight: Reduce Three to Two

The moment you see a three number sum problem, the most important question to ask yourself is:

Can I fix one element and turn this into a two number sum?

The answer here is yes.

If we fix nums[i], then we need to find two other numbers in the rest of the array that sum to 0 - nums[i]. That is exactly the Two Sum II problem from Day 2 of this challenge.

So the structure of the solution becomes:

1. Sort the array
2. Loop over each element and fix it as nums[i]
3. Run the Two Sum II two pointer approach on the rest of the array

The real challenge is not finding the sums. It is making sure we do not return the same triplet more than once. That is where duplicate handling comes in, and we will spend serious time on it.

Why Sorting Is the First Move

Before we write a single pointer, we sort the array.

Sorting does three things for us here:

1. It enables directional pointer movement. Once sorted, if the sum is too large, we know to move the right pointer in. If too small, we move the left pointer out. We used this exact logic in Day 2.

2. It groups duplicate values together. This is critical for skipping duplicates efficiently. If duplicates are adjacent, we can check in one comparison whether the current value is the same as the previous one and skip it immediately.

3. It gives us ordered triplets automatically. Since i < j < k in a sorted array, every triplet we collect will naturally be in non-decreasing order, which means [-1, -1, 2] and [2, -1, -1] will never both appear in our result.

Without sorting, all three of these guarantees disappear. The problem becomes significantly harder.

First Instincts vs. Correct Thinking

The brute force instinct is to use three nested loops and check every possible combination of three elements. That is O(n³), which for 3000 elements is 27 billion operations. Completely unusable.

A smarter instinct might be to use a hash set. Fix two numbers, compute the third, and check if it exists. That brings the time down to O(n²) but managing duplicates with a hash set gets messy fast, and it uses O(n) space for bookkeeping.

The right approach uses what we already know. Sorting plus two pointers gives us O(n²) time with O(1) extra space and clean, manageable duplicate handling.

Understanding the Approach

Here is the full structure:

• Sort the array
• Fix nums[i] using a loop from index 0 to n - 3
• Set j = i + 1 (left pointer, starts just after i)
• Set k = n - 1 (right pointer, starts at the end)
• Compute the total: nums[i] + nums[j] + nums[k]
• If total is greater than 0, move k left
• If total is less than 0, move j right
• If total equals 0, record the triplet, then advance j and skip any duplicates of nums[j]
• Before each outer loop iteration, skip duplicates of nums[i]

Deep Dry Run: Every Step Explained

Input

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

Step 1: Sort the Array

Sorted: [-4, -1, -1, 0, 1, 2]
Index:    0   1   2  3  4  5

All further steps operate on this sorted version.

Iteration 1: Fix i = 0, nums[i] = -4

Array:  [-4, -1, -1,  0,  1,  2]
          ^   ^                ^
          i   j                k
         i=0  j=1             k=5

We need two numbers that sum to 0 - (-4) = 4.

Step 1a:

nums[j] = -1
nums[k] = 2
total = -4 + (-1) + 2 = -3

total (-3) < 0. Need a larger value on the left side. Move j right.

j = 2

Step 1b:

Array:  [-4, -1, -1,  0,  1,  2]
          ^        ^           ^
          i        j           k
         i=0      j=2         k=5

nums[j] = -1
nums[k] = 2
total = -4 + (-1) + 2 = -3

Still < 0. Move j right.

j = 3

Step 1c:

nums[j] = 0
nums[k] = 2
total = -4 + 0 + 2 = -2

Still < 0. Move j right.

j = 4

Step 1d:

nums[j] = 1
nums[k] = 2
total = -4 + 1 + 2 = -1

Still < 0. Move j right.

j = 5
j == k → stop inner loop

No valid triplet found for nums[i] = -4. This makes sense because the two largest remaining values (1 and 2) still cannot bring the sum up to 0 when paired with -4.

Iteration 2: Fix i = 1, nums[i] = -1

Array:  [-4, -1, -1,  0,  1,  2]
              ^   ^            ^
              i   j            k
             i=1  j=2         k=5

We need two numbers that sum to 0 - (-1) = 1.

Step 2a:

nums[j] = -1
nums[k] = 2
total = -1 + (-1) + 2 = 0

total === 0. Valid triplet found.

Triplet recorded: [-1, -1, 2]

Now move j right and skip any duplicates.

j = 3
nums[j] = 0, nums[j - 1] = -1  (no duplicate, continue)

Step 2b:

Array:  [-4, -1, -1,  0,  1,  2]
              ^        ^       ^
              i        j       k
             i=1      j=3     k=5

nums[j] = 0
nums[k] = 2
total = -1 + 0 + 2 = 1

total (1) > 0. Need a smaller value on the right. Move k left.

k = 4

Step 2c:

Array:  [-4, -1, -1,  0,  1,  2]
              ^        ^   ^
              i        j   k
             i=1      j=3 k=4

nums[j] = 0
nums[k] = 1
total = -1 + 0 + 1 = 0

total === 0. Valid triplet found.

Triplet recorded: [-1, 0, 1]

Move j right.

j = 4
j == k → stop inner loop

Two triplets found for nums[i] = -1.

Iteration 3: Skip Duplicate i

i = 2 → nums[i] = -1
nums[i] == nums[i - 1] → -1 == -1 → duplicate detected

Action: Skip this iteration entirely with continue.

Why? Because nums[i] = -1 was already fixed in Iteration 2. Running the full inner loop again with the same fixed value would produce the exact same triplets all over again. We skip it to keep the result clean.

Iteration 4: Fix i = 3, nums[i] = 0

Array:  [-4, -1, -1,  0,  1,  2]
                       ^   ^   ^
                       i   j   k
                      i=3 j=4 k=5

nums[j] = 1
nums[k] = 2
total = 0 + 1 + 2 = 3

total (3) > 0. Move k left.

k = 4
k == j → stop inner loop

No valid triplet for nums[i] = 0.

The loop also stops here because i cannot go beyond n - 3 = 3 for a valid triplet.

Final Result

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

Why Duplicate Handling Is Mandatory, Not Optional

Let us be very clear about this. Duplicate handling is not an optimisation. It is a correctness requirement. If you submit a solution without it, the output will contain repeated triplets and the judge will reject it.

There are two places where duplicates must be handled:

1. Skipping duplicate values of i

if (i > 0 && nums[i] === nums[i - 1]) continue;

If the current fixed element is the same as the previous one, all the two pointer work we would do is identical to what we already did. We skip the entire iteration.

Note the i > 0 guard. We only compare to the previous element when one exists. Without it, nums[0] would incorrectly compare to an undefined index.

2. Skipping duplicate values of j after recording a triplet

while (j < k && nums[j] === nums[j - 1]) {
    j++;
}

After we record a valid triplet and advance j, we check if the new j value is the same as the one we just used. If it is, advancing to it would produce the same triplet again because i and k have not changed yet. We keep pushing j forward until it lands on a new value.

We do not need the same check for k in this implementation because once j is handled, any duplicate k situation is naturally avoided. But adding it for k is also valid and does not hurt.

The Code

var threeSum = function(nums) {
    const res = [];
    nums.sort((a, b) => a - b);       // Sort the array first
    const n = nums.length;

    for (let i = 0; i < n - 2; i++) {
        // Skip duplicate values for the fixed element
        if (i > 0 && nums[i] === nums[i - 1]) continue;

        let j = i + 1;                // Left pointer
        let k = n - 1;                // Right pointer

        while (j < k) {
            const total = nums[i] + nums[j] + nums[k];

            if (total > 0) {
                k--;                  // Sum too large, bring right pointer in
            } else if (total < 0) {
                j++;                  // Sum too small, push left pointer out
            } else {
                res.push([nums[i], nums[j], nums[k]]);  // Valid triplet
                j++;
                // Skip duplicate values for the left pointer
                while (j < k && nums[j] === nums[j - 1]) {
                    j++;
                }
            }
        }
    }

    return res;
};

Line by line breakdown:

• nums.sort((a, b) => a - b) sorts the array in ascending order. Always the first step.
• for (let i = 0; i < n - 2; i++) fixes one element. We stop at n - 2 because j and k need at least two more positions.
• if (i > 0 && nums[i] === nums[i - 1]) continue skips the outer loop if the fixed element is a duplicate of the previous one.
• j = i + 1 and k = n - 1 place the two inner pointers just after i and at the end respectively.
• total > 0 means the right side is too large, so k moves in.
• total < 0 means the left side is too small, so j moves out.
• res.push(...) records the triplet when the total is zero.
• The inner while loop after the push skips duplicate values of j before continuing.

Complexity Analysis

Time

O(n²)

Sorting takes O(n log n). The outer loop runs O(n) times and the inner two pointer loop runs O(n) per iteration, giving O(n²) total.

Space

O(1)

Only pointers and a temp variable are used. The result array is excluded from space complexity since it is part of the required output.

Common Mistakes to Avoid

Mistake 1: Not sorting first.

Without sorting, the two pointer approach cannot work because there is no directional information in the sum comparison. Always sort before setting up pointers.

Mistake 2: Forgetting duplicate handling entirely.

This is the most common reason for a wrong answer verdict on this problem. If you skip the duplicate checks, valid triplets will appear multiple times in your result.

Mistake 3: Handling duplicates in the wrong place.

The outer loop skip (nums[i] === nums[i - 1]) must use i > 0 as a guard. The inner skip must happen after recording the triplet and advancing j, not before.

Mistake 4: Using the wrong loop boundary.

The outer loop should run to n - 2, not n - 1 or n. If i can reach the last two indices, there are not enough remaining elements to form a triplet.

Mistake 5: Skipping duplicates at the wrong time.

Do not skip duplicate j values before you have pushed the triplet. The skip happens after the push. Doing it before means you might miss valid triplets.

Interview Tips for This Problem

If Three Sum comes up in an interview, here is how to talk through your approach:

1. Acknowledge the pattern immediately. "If I fix one element, this becomes Two Sum on a sorted array, which is a problem I know how to solve with two pointers."
2. Sort first and say why. "Sorting lets me use directional pointer movement and handle duplicates cleanly."
3. Mention duplicate handling before coding. Interviewers specifically watch for this. Bring it up before they ask about it.
4. Trace through the example with two or three steps. You do not need to trace the full example, but showing two iterations demonstrates you understand the pointer movement.
5. State the complexity before finishing. "This is O(n²) time and O(1) space, which is optimal for this problem."

Where This Pattern Appears Next

Three Sum is a building block for a family of problems:

• LeetCode 16 Three Sum Closest: Same structure, but instead of finding an exact sum you track the sum closest to the target.
• LeetCode 18 Four Sum: Add one more fixed outer loop. Fix two elements, apply two pointers on the rest.
• LeetCode 259 Three Sum Smaller: Count pairs with sum less than a target. Same two pointer movement, different condition.
• LeetCode 611 Valid Triangle Number: A variation where you count triplets satisfying the triangle inequality. Same sorting plus two pointer frame.

If you are comfortable with Three Sum, all of these feel like minor adjustments rather than new problems.

The Growing Pattern Map

After three days, we now have a clear picture of how these problems connect.

Day

Problem

Pattern

Key Condition

Day 1

Move Zeroes

Fast Slow Pointers

Partition non-zero elements

Day 2

Two Sum II

Opposite Ends Pointers

Sorted array, exact sum

Day 3

Three Sum

Fix one + Opposite Ends

Sorted array, zero sum, no duplicates

Each day adds one layer. Day 3 does not introduce an entirely new pattern. It builds on Day 2 by wrapping it inside an outer loop and adding duplicate handling.

This is what pattern-based learning looks like. The problems get harder, but the foundation stays familiar.

Key Takeaways

• Sorting is not just a preprocessing step. It is what makes the entire approach possible. Do not skip it and do not forget to explain why you are doing it.
• Three Sum is Two Sum II with an outer loop. Once you see that reduction, the solution structure writes itself.
• Duplicate handling is a correctness requirement, not an optimisation. Handle it for both the fixed element and the left pointer.
• Pattern problems compound. The more patterns you recognise, the faster you see solutions to new problems.

What Is Next

Day 3 ✅

We have now covered fast slow pointers, opposite ends pointers, and fix one plus two pointers. Three patterns in three days, each building on the one before.

Day 4 is coming tomorrow with a new problem, a full dry run, and the same structured breakdown.

If you are following along, drop a comment with your solution or any part of the duplicate handling that felt confusing. I will answer.

See you on Day 4. 🚀

This post is part of my 250 Days DSA Challenge, solving one problem every day with a focus on intuition, patterns, and interview ready thinking.