3Sum: two pointers inside a sorted loop

The previous article on Two Sum II ended with one observation worth keeping: once the array is sorted, a left and right pointer can find any target pair in linear time. 3Sum is what happens when you wrap that technique inside another loop. Fix the first number, let Two Sum II handle the remaining two. That's the whole algorithm — except the duplicate-skipping, which is where every clean-looking solution tends to quietly break.

The problem and what the constraints tell you

Given an array of integers, return all unique triplets [a, b, c] such that a + b + c == 0. No duplicate triplets in the output, and the indices must be distinct.

The constraint 3 <= n <= 3000 does most of the work for you. 3000³ is about 27 billion operations — nowhere near feasible. 3000² is 9 million, which is fine. So the constraint is not just a bound; it's telling you the answer has to be O(n²). That immediately rules out the three-nested-loop approach and points you toward something that reduces the inner search from O(n²) to O(n).

The value range -10⁵ <= nums[i] <= 10⁵ fits comfortably in a 32-bit integer. Two of them added together fit in a 64-bit int, but even the sum of three won't overflow int in most languages. No overflow guard needed here.

Approach 1: brute force O(n³)

The obvious starting point: three nested loops over all index triples (i, j, k) with i < j < k. If the sum is zero, sort the triplet and insert it into a set to handle deduplication.

class Solution:
    def threeSum(self, nums):
        result_set = set()
        n = len(nums)
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                for k in range(j + 1, n):
                    if nums[i] + nums[j] + nums[k] == 0:
                        triplet = tuple(sorted([nums[i], nums[j], nums[k]]))
                        result_set.add(triplet)
        return [list(t) for t in result_set]

public class Solution {
    public IList<IList<int>> ThreeSum(int[] nums) {
        var seen = new HashSet<string>();
        var result = new List<IList<int>>();
        int n = nums.Length;
        for (int i = 0; i < n - 2; i++)
            for (int j = i + 1; j < n - 1; j++)
                for (int k = j + 1; k < n; k++)
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        var t = new[] { nums[i], nums[j], nums[k] };
                        Array.Sort(t);
                        string key = string.Join(",", t);
                        if (seen.Add(key))
                            result.Add(t.ToList());
                    }
        return result;
    }
}

Time: O(n³). Space: O(k) for the output plus set overhead. With n = 3000 that's roughly 27 billion comparisons — a TLE in any language. The set-based dedup also feels like papering over a design problem rather than solving it. Every triplet gets sorted inside the loop, which adds another O(1) constant but signals that the structure isn't right.

Approach 2: hash set reduction O(n²)

Fix the outer element at index i, then turn the remaining two-element problem into a Two Sum lookup. Scan through nums[j] for j > i, maintaining a set of values seen so far, and check whether -(nums[i] + nums[j]) is already in that set.

class Solution:
    def threeSum(self, nums):
        result_set = set()
        n = len(nums)
        for i in range(n - 1):
            seen = set()
            for j in range(i + 1, n):
                complement = -(nums[i] + nums[j])
                if complement in seen:
                    triplet = tuple(sorted([nums[i], nums[j], complement]))
                    result_set.add(triplet)
                seen.add(nums[j])
        return [list(t) for t in result_set]

public class Solution {
    public IList<IList<int>> ThreeSum(int[] nums) {
        var resultSet = new HashSet<string>();
        var result = new List<IList<int>>();
        int n = nums.Length;
        for (int i = 0; i < n - 1; i++) {
            var seen = new HashSet<int>();
            for (int j = i + 1; j < n; j++) {
                int complement = -(nums[i] + nums[j]);
                if (seen.Contains(complement)) {
                    var t = new[] { nums[i], nums[j], complement };
                    Array.Sort(t);
                    string key = string.Join(",", t);
                    if (resultSet.Add(key))
                        result.Add(t.ToList());
                }
                seen.Add(nums[j]);
            }
        }
        return result;
    }
}

Time: O(n²). Space: O(n) for the inner hash set plus the result set.

This gets the time complexity right. The deduplication is still awkward — you have to sort each candidate before hashing it, and you need a second outer set to deduplicate across outer iterations. It works, but it's paying O(n) extra memory and a lot of bookkeeping to solve a problem that sorting handles for free. I wouldn't ship this; the two-pointer approach is simpler in every dimension that matters in an interview or a codebase.

Approach 3: sort + two pointers O(n²)

Sort the array once. Iterate with index i from 0 to n - 3, treating nums[i] as the fixed first element. Inside, run Two Sum II on the subarray nums[i+1 .. n-1]: set left = i + 1 and right = n - 1, converging toward the center.

Sorting does three things at once: it makes two-pointer movement monotone, it collapses all duplicate values into adjacent positions (so skipping them is a single while loop), and it enables the early exit when nums[i] > 0.

By-hand trace: nums = [-1, 0, 1, 2, -1, -4]

After sort: [-4, -1, -1, 0, 1, 2]

class Solution:
    def threeSum(self, nums):
        nums.sort()
        result = []
        n = len(nums)
 
        for i in range(n - 2):
            # Early exit: smallest remaining element is positive, no triplet possible
            if nums[i] > 0:
                break
 
            # Skip duplicate values for the fixed element
            if i > 0 and nums[i] == nums[i - 1]:
                continue
 
            left, right = i + 1, n - 1
 
            while left < right:
                total = nums[i] + nums[left] + nums[right]
 
                if total == 0:
                    result.append([nums[i], nums[left], nums[right]])
 
                    # Skip duplicates from the left side
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    # Skip duplicates from the right side
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
 
                    left += 1
                    right -= 1
 
                elif total < 0:
                    left += 1
                else:
                    right -= 1
 
        return result

public class Solution {
    public IList<IList<int>> ThreeSum(int[] nums) {
        Array.Sort(nums);
        var result = new List<IList<int>>();
        int n = nums.Length;
 
        for (int i = 0; i < n - 2; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
 
            int left = i + 1, right = n - 1;
 
            while (left < right) {
                int total = nums[i] + nums[left] + nums[right];
 
                if (total == 0) {
                    result.Add(new List<int> { nums[i], nums[left], nums[right] });
 
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
 
                    left++;
                    right--;
                } else if (total < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
 
        return result;
    }
}

Time: O(n log n) for the sort, O(n²) for the nested scan — dominated by O(n²). Space: O(1) ignoring the output array and the sort's internal stack.

The duplicate-skip logic, dissected

This is the part that breaks most first attempts. There are three places where duplicates bite you, and each one fails differently.

The outer loop (i): After processing nums[i], you don't want to repeat the entire inner scan for the same value. The check if i > 0 and nums[i] == nums[i - 1]: continue handles it. The guard i > 0 is not optional — without it you'd skip i = 0 itself whenever nums[0] == nums[1], dropping valid triplets.

The inner pointers after a match: When you find a triplet, advance both pointers past any run of identical values before continuing. The two while loops inside the total == 0 branch do this. They stop short of crossing (left < right guard) because if all remaining elements are identical, the pointers should end up adjacent, not flipped — flipping them would cause left >= right to terminate the outer while loop, which is correct but requires the guard to not access out-of-bounds indices.

What you don't need to worry about: The total < 0 and total > 0 branches move one pointer unconditionally. If the next value is the same, you'll find the same sum and move again, or the sum changes — no duplicate triplet ever gets recorded because you only append inside total == 0.

A concrete failure case: nums = [-2, 0, 0, 2, 2]. Without the inner duplicate-skip:

• i=0, nums[i]=-2, find left=1 (0), right=4 (2) -> sum=0, record [-2, 0, 2]
• Without skipping: left=2 (0), right=3 (2) -> sum=0, record [-2, 0, 2] again

Expected output: [[-2, 0, 2]]. Incorrect without the skip: [[-2, 0, 2], [-2, 0, 2]].

Edge cases that actually matter

All zeros [0, 0, 0]: After sort, i=0, nums[i]=0, left=1, right=2. Sum is 0+0+0=0, record [0,0,0]. Then both skip-loops don't advance (no same-adjacent values past the boundary), and left++/right-- cause left >= right. The outer loop continues but nums[1]=0 is skipped by the i > 0 and nums[i] == nums[i-1] check. Result: [[0,0,0]]. Correct.

All positives [1, 2, 3, 4]: After sort, nums[0]=1 > 0, so break fires immediately. Result: []. Correct, and O(1) runtime in practice for this input shape.

All same value, non-zero [1, 1, 1]: After sort, i=0, nums[i]=1 > 0, break immediately. Result: []. Correct.

Heavy duplicates [-1, -1, -1, 0, 1, 1, 1]: The outer skip fires for i=1 and i=2 (both equal nums[0]=-1). Only i=0 runs the inner scan. Inside, the inner skip fires multiple times to collapse the runs of 1. Single triplet [-1, 0, 1] is recorded exactly once.

Minimum input [0, 0, 0]: Handled above — the minimum valid input by constraint (n >= 3) has exactly one possible triplet and the code finds it.

Complexity comparison

The hash set approach isn't wrong — it's the natural extension of the 1D Two Sum hash map idea. But the extra O(n) space buys you nothing here; sorting is O(n log n) and eliminates the need for any auxiliary storage beyond the output. I'd use the sort approach in every context: interview, production, whiteboard.

Where this sits in the two-pointers series

Two Sum II (LeetCode 167) established the core move: sort a fixed pair search down to linear time with two pointers. 3Sum wraps that in one outer loop, adding one constraint — the duplicate-skip — that Two Sum II didn't need because the problem guaranteed unique elements. Everything here is exactly Two Sum II + one loop + three skip conditions. If Two Sum II felt natural, 3Sum should feel like a direct upgrade, not a new problem.

The mental model generalizes: k-Sum reduces to (k-1)-Sum by fixing one element. Fix two with two nested loops and you get 4Sum at O(n³). Fix three with three loops and you get 5Sum at O(n⁴). Each level adds one duplicate-skip location. The pattern holds all the way up; in practice nobody goes past 4Sum.

Four sibling problems worth doing in order

3Sum Closest (LeetCode 16) — replace the total == 0 check with tracking min(abs(total - target)). The two-pointer movement logic is identical, only the bookkeeping changes. Duplicate-skipping becomes optional since you're minimizing distance rather than collecting exact matches. Recommended immediately after this one.

3Sum Smaller (LeetCode 259) — count triplets where the sum is less than a given target. Same outer loop and two-pointer setup, but when sum < target you count right - left triplets at once (all values between left and right pair with the current left to give a smaller sum). The counting trick is the non-obvious piece.

4Sum (LeetCode 18) — the direct extension. Two outer loops, two pointers inside. Duplicate-skip at four places instead of three. The interesting part is that O(n³) is the best achievable for 4 elements, and the code structure makes that obvious.

Container With Most Water (LeetCode 11) — a different use of two pointers on a sorted-ish structure. This one doesn't sort and doesn't deduplicate; the two-pointer intuition is greedy (always move the shorter wall) rather than target-convergence. Good for testing whether you understand why two pointers work on 3Sum versus why they work here — the invariant is different.