3Sum, 4Sum and Counting Pairs with Two Pointers

EditorialUpdated Oct 25, 2026

From two numbers to three

In the last lesson, two pointers found two numbers with a given sum. Now find three: which triplets in [-1, 0, 1, 2, -1, -4] add up to 0? That's 3Sum, one of the most asked interview problems. It wants each triplet of values once, so [-1, 0, 1] counts one time even though there are two -1s to build it from.

The direct way checks every group of three. LeetCode allows up to 3,000 numbers, which makes 4,495,501,000 triples to check.

Here's the better idea, and it uses nothing new. Fix the first number, then find the other two with two pointers. If the first number is -4, the other two must add up to 4, and that's exactly the pair problem from the last lesson. One pointer scan per fixed number is at most 4,495,501 steps in total for 3,000 numbers: a thousand times fewer.

In this lesson: 3Sum step by step; how to skip duplicates without losing answers (the one new skill); why it never misses a triplet; 4Sum and any number of values; counting pairs in one pass instead of listing them; and the mistakes that fail on real inputs.

Before this: Introduction to Two Pointers, which explains why the pointers never miss a pair.

3Sum on the list [-1, 0, 1, 2, -1, -4], sorted to [-4, -1, -1, 0, 1, 2]. The first number is fixed in turn, and two pointers scan the numbers after it for the two that complete the sum. Fixing -4, no pair after it adds up to 4. Fixing the first -1, the pointers find -1 + 2 = 1 and then 0 + 1 = 1, giving the triplets [-1, -1, 2] and [-1, 0, 1]. The second -1 is skipped because it would only repeat them. Fixing 0, nothing is left that sums to 0. Three numbers become one fixed number plus the pair problem.

Fix one number, then run two pointers on the rest

Sort the list first. Then, for each position i:

The number at i is the first of the three. The other two must add up to -nums[i].
Put left just after i and right at the end, and run the pair scan you already know: too small moves left right, too big moves right left.
When the three add up to 0, record them and move both pointers inward, past any copies of the numbers you just used.

Here's every step on [-4, -1, -1, 0, 1, 2]:

Step	i, left, right	Sum	What happens
1	0, 1, 5	-4 + -1 + 2 = -3	too small → move left
2	0, 2, 5	-4 + -1 + 2 = -3	too small → move left
3	0, 3, 5	-4 + 0 + 2 = -2	too small → move left
4	0, 4, 5	-4 + 1 + 2 = -1	too small → move left
5	1, 2, 5	-1 + -1 + 2 = 0	found
6	1, 3, 4	-1 + 0 + 1 = 0	found
7	2		-1 again, the same first number as before: skip
8	3, 4, 5	0 + 1 + 2 = 3	too big → move right

Two triplets, [-1, -1, 2] and [-1, 0, 1], in 7 comparisons. Notice step 7: the second -1 is skipped without a single comparison. The next section explains why that's safe.

3Sum: fix one number, two pointers find the rest — The fixed number glows; the pointers scan the numbers after it. A skipped duplicate is marked in orange.

Here's the whole thing in all four languages. Each one prints -1 -1 2 and -1 0 1 for the list [-1, 0, 1, 2, -1, -4].

vector<vector<int>> threeSum(vector<int> nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> result;
    int n = nums.size();
    for (int i = 0; i + 2 < n; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;  // same first number as last time: same triplets
        int left = i + 1, right = n - 1;
        while (left < right) {
            int total = nums[i] + nums[left] + nums[right];
            if (total == 0) {
                result.push_back({nums[i], nums[left], nums[right]});
                left++;
                right--;
                while (left < right && nums[left] == nums[left - 1]) left++;     // past copies just used
                while (left < right && nums[right] == nums[right + 1]) right--;
            } else if (total < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}

def three_sum(nums):
    nums = sorted(nums)
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue                      # same first number as last time: same triplets
        left, right = i + 1, len(nums) - 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             # past copies of the number just used
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    return result

static List<List<Integer>> threeSum(int[] input) {
    int[] nums = input.clone();
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();
    for (int i = 0; i + 2 < nums.length; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;  // same first number as last time: same triplets
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int total = nums[i] + nums[left] + nums[right];
            if (total == 0) {
                result.add(List.of(nums[i], nums[left], nums[right]));
                left++;
                right--;
                while (left < right && nums[left] == nums[left - 1]) left++;     // past copies just used
                while (left < right && nums[right] == nums[right + 1]) right--;
            } else if (total < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}

function threeSum(input) {
    const nums = [...input].sort((a, b) => a - b);
    const result = [];
    for (let i = 0; i + 2 < nums.length; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;  // same first number as last time: same triplets
        let left = i + 1, right = nums.length - 1;
        while (left < right) {
            const total = nums[i] + nums[left] + nums[right];
            if (total === 0) {
                result.push([nums[i], nums[left], nums[right]]);
                left++;
                right--;
                while (left < right && nums[left] === nums[left - 1]) left++;     // past copies just used
                while (left < right && nums[right] === nums[right + 1]) right--;
            } else if (total < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}

Cost: sorting is O(n log n), and each fixed number runs one O(n) scan, so the total is O(n²) time. The result list aside, it needs no extra space beyond the sort.

Skipping duplicates without losing answers

This is the one genuinely new skill, and the place most solutions go wrong. The list has two -1s, but each triplet must appear once. There are two places to skip, and they look different.

Skipping a fixed number: look back. Skip i when nums[i] == nums[i - 1]. The first -1 gets to go, and it can pair with everything after it, including the second -1. That's how [-1, -1, 2] is found. The second -1 can only pair with numbers after itself, a smaller set, so every triplet it could start has already been found. Skipping it loses nothing.

Compare with the next number instead (nums[i] == nums[i + 1]) and you skip the wrong copy: the first -1 goes, the second stays, and nothing after the second -1 can make [-1, -1, 2]. The mistakes section shows it failing.

Skipping after a match: step past the copies. Once -1 + 0 + 1 is recorded, moving left onto another 0 would find the same triplet again. So after a match, left keeps moving while it sits on the number just used, and right does the same from its side.

The sorted list [-4, -1, -1, 0, 1, 2] with two -1s at positions 1 and 2. Fixing the first -1, the pointers can use every number after it, including the second -1, and find [-1, -1, 2] and [-1, 0, 1]. Fixing the second -1, they could only use 0, 1 and 2, so every triplet it could make is one the first -1 already found: it is skipped. Comparing with the next number instead would skip the first -1 and lose [-1, -1, 2].

Why every triplet is found exactly once

Take any triplet that sums to 0, and write its numbers in order: x ≤ y ≤ z. Let i be the first position in the sorted list that holds x.

The loop doesn't skip that i, because it's the first copy of x.
When i is fixed, left and right scan everything after it. By the argument from the last lesson, a pointer scan never walks past a pair that adds up to the target, so it finds y and z.
So every triplet is found at least once.

And at most once: the outer loop uses each value of x once, and after a match both pointers step past the values they just used, so the same y and z can't be recorded twice for one x.

That's the whole proof. 3Sum isn't a new technique; it's the pair scan, run once per first number, with care about copies.

4Sum: one more loop

Four numbers? Fix two, then run the pointers on the rest. Two nested loops choose the first two numbers, each skipping repeated values the same way, and the pair scan finds the last two. That's O(n³).

Two things change when the numbers can be large. LeetCode's 4Sum allows values up to 1,000,000,000 and any target, so:

Add as 64-bit numbers. Four values near a billion don't fit in a 32-bit int.
Be careful with shortcuts. "Stop once the first number is bigger than the target" only works if the other numbers can't pull the sum back down. With negative numbers they can.

Each version below prints the three quadruplets of [1, 0, -1, 0, -2, 2] that sum to 0.

vector<vector<int>> fourSum(vector<int> nums, int target) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> result;
    int n = nums.size();
    for (int a = 0; a + 3 < n; a++) {
        if (a > 0 && nums[a] == nums[a - 1]) continue;
        for (int b = a + 1; b + 2 < n; b++) {
            if (b > a + 1 && nums[b] == nums[b - 1]) continue;
            int left = b + 1, right = n - 1;
            while (left < right) {
                long long total = (long long)nums[a] + nums[b] + nums[left] + nums[right];  // four can overflow int
                if (total == target) {
                    result.push_back({nums[a], nums[b], nums[left], nums[right]});
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (total < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    return result;
}

def four_sum(nums, target):
    nums = sorted(nums)
    n, result = len(nums), []
    for a in range(n - 3):
        if a > 0 and nums[a] == nums[a - 1]:
            continue
        for b in range(a + 1, n - 2):
            if b > a + 1 and nums[b] == nums[b - 1]:
                continue
            left, right = b + 1, n - 1
            while left < right:
                total = nums[a] + nums[b] + nums[left] + nums[right]
                if total == target:
                    result.append([nums[a], nums[b], 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
                elif total < target:
                    left += 1
                else:
                    right -= 1
    return result

static List<List<Integer>> fourSum(int[] input, int target) {
    int[] nums = input.clone();
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();
    int n = nums.length;
    for (int a = 0; a + 3 < n; a++) {
        if (a > 0 && nums[a] == nums[a - 1]) continue;
        for (int b = a + 1; b + 2 < n; b++) {
            if (b > a + 1 && nums[b] == nums[b - 1]) continue;
            int left = b + 1, right = n - 1;
            while (left < right) {
                long total = (long) nums[a] + nums[b] + nums[left] + nums[right];  // four can overflow int
                if (total == target) {
                    result.add(List.of(nums[a], nums[b], nums[left], nums[right]));
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (total < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    return result;
}

function fourSum(input, target) {
    const nums = [...input].sort((a, b) => a - b);
    const result = [];
    const n = nums.length;
    for (let a = 0; a + 3 < n; a++) {
        if (a > 0 && nums[a] === nums[a - 1]) continue;
        for (let b = a + 1; b + 2 < n; b++) {
            if (b > a + 1 && nums[b] === nums[b - 1]) continue;
            let left = b + 1, right = n - 1;
            while (left < right) {
                const total = nums[a] + nums[b] + nums[left] + nums[right];
                if (total === target) {
                    result.push([nums[a], nums[b], nums[left], nums[right]]);
                    left++;
                    right--;
                    while (left < right && nums[left] === nums[left - 1]) left++;
                    while (left < right && nums[right] === nums[right + 1]) right--;
                } else if (total < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    return result;
}

Any number of values (k-Sum): the pattern keeps going. For k numbers, fix k − 2 of them with loops, then run one pair scan. That's O(n^(k−1)) time: O(n²) for 3Sum, O(n³) for 4Sum.

Counting pairs without listing them

Sometimes a problem asks how many pairs, not which. How many pairs in [1, 2, 4, 5, 7, 9] add up to less than 10?

Checking each pair works, but there's a shortcut hiding in the pointer scan. Look at what one comparison tells you when the sum is too small: nums[left] with nums[right] is below the target, and every number between them is smaller than nums[right]. So nums[left] paired with any of them is below the target too. That's right - left pairs, counted in one step.

When the sum is not below the target, nums[right] is too big even with the smallest number left, so it can't be part of any counted pair: move right.

It's the same grid as the last lesson. There, a too-small comparison threw a whole row away. Here it counts the whole row.

Step	Sum	What happens
1	1 + 9 = 10	not below 10: 9 can't pair with anyone left, move right
2	1 + 7 = 8	below 10: add 4 (all of 1's pairs up to 7)
3	2 + 7 = 9	below 10: add 3 (all of 2's pairs up to 7)
4	4 + 7 = 11	not below 10: 7 can't pair with anyone left, move right
5	4 + 5 = 9	below 10: add 1 (all of 4's pairs up to 5)

That's 8 pairs in 5 comparisons, out of 15 pairs in all. For n numbers it's O(n) after sorting, never O(n²). People often believe counting pairs needs every pair checked; it doesn't.

The pair grid for the sorted list [1, 2, 4, 5, 7, 9] and the target 10: rows are the left number, columns the right number, each cell their sum. The pointer scan runs on it. When 1 + 7 = 8 is below 10, the whole row of 1 up to 7 is below 10, so its 4 pairs are counted at once. When 2 + 7 = 9 is below 10, 3 more are counted, and 4 + 5 = 9 adds 1. When 1 + 9 = 10 and 4 + 7 = 11 are not below 10, those columns are dropped. 8 pairs counted in 5 comparisons, out of 15.

long long countPairsBelow(vector<int> nums, int target) {
    sort(nums.begin(), nums.end());
    int left = 0, right = (int)nums.size() - 1;
    long long count = 0;
    while (left < right) {
        if ((long long)nums[left] + nums[right] < target) {
            count += right - left;   // nums[left] with every number up to right: all below target
            left++;
        } else {
            right--;                 // nums[right] is too big even with the smallest partner left
        }
    }
    return count;
}

def count_pairs_below(nums, target):
    nums = sorted(nums)
    left, right, count = 0, len(nums) - 1, 0
    while left < right:
        if nums[left] + nums[right] < target:
            count += right - left    # nums[left] with every number up to right: all below target
            left += 1
        else:
            right -= 1               # nums[right] is too big even with the smallest partner left
    return count

static long countPairsBelow(int[] input, int target) {
    int[] nums = input.clone();
    Arrays.sort(nums);
    int left = 0, right = nums.length - 1;
    long count = 0;
    while (left < right) {
        if ((long) nums[left] + nums[right] < target) {
            count += right - left;   // nums[left] with every number up to right: all below target
            left++;
        } else {
            right--;                 // nums[right] is too big even with the smallest partner left
        }
    }
    return count;
}

function countPairsBelow(input, target) {
    const nums = [...input].sort((a, b) => a - b);
    let left = 0, right = nums.length - 1, count = 0;
    while (left < right) {
        if (nums[left] + nums[right] < target) {
            count += right - left;   // nums[left] with every number up to right: all below target
            left++;
        } else {
            right--;                 // nums[right] is too big even with the smallest partner left
        }
    }
    return count;
}

Each prints 8.

The same trick, one step further. Number of Subsequences That Satisfy the Given Sum Condition counts subsequences whose smallest plus largest number is at most a target. Sort, and when nums[left] + nums[right] fits, nums[left] can be the smallest with any choice of the numbers between them: that's 2^(right − left) subsequences, added at once. On [3, 5, 6, 7] with target 9 it gives 4, the same as listing all 15 subsequences. (The real problem asks for the answer modulo 1,000,000,007, so precompute the powers of two.)

Try it yourself

Below is the grid for counting pairs below a target. You move the pointers. When the sum is too small, moving left counts the whole row at once. Try moving right instead and watch which pairs get dropped without being counted.

Count grid: move the pointers and see which pairs each move counts

When to use it

Reach for "fix some, two pointers on the rest" when you see:

Three or four numbers that sum to a target, with each answer listed once: 3Sum, 4Sum.
A sum as close as possible to a target: the same scan, keeping the best difference (3Sum Closest).
How many pairs or triplets are below, above or within a range: count in bulk.
A rule that only depends on the smallest and largest of a group: sort, then count with pointers (Number of Subsequences That Satisfy the Given Sum Condition).

And watch for problems that look similar but need something else:

One number from each of several separate arrays (4Sum II): the arrays don't share an order to walk, so store pair sums in a hash map.
Original positions needed and the list isn't sorted (Two Sum): sorting scrambles the positions, so use a hash map.
A run of neighbouring numbers (a subarray) with a given sum: that's prefix sums or a sliding window, later in this course.

When two pointers doesn't work

Listing can't be fast if there are many answers. Some lists have about n² triplets that sum to 0, and writing them all out takes that long, whatever the method. Counting doesn't have this limit.
Positions vs values. 3Sum wants each triplet of values once. Counting problems usually count positions: in [0, 0, 0], three different pairs add up to 0, even though they're all 0 + 0. Read which one the problem asks for.
There's no much faster way for 3Sum. Nobody has found an algorithm that beats about n² steps by more than a little, and many problems are known to be at least as hard. In an interview, O(n²) is the answer.
A hash set works too, but costs more. Fixing a number and finding the other two with a set is also O(n²), but it needs extra memory and a separate way to remove repeated triplets. The sorted scan gives both for free.

Common mistakes

Each of these is a real submission bug. The outputs come from running the code.

Comparing with the next copy. Skip the fixed number when nums[i] == nums[i + 1] and [-1, 0, 1, 2, -1, -4] returns [[-1, 0, 1]]. [-1, -1, 2] is gone, because the -1 that could start it was the one skipped. Always compare with nums[i - 1].

Not stepping past copies after a match. Move each pointer just one step after recording a triplet, and [-2, 0, 0, 2, 2] returns [[-2, 0, 2], [-2, 0, 2]]: the same triplet twice, because the pointers land on another 0 and another 2.

Adding four big numbers in an int. In Java, four 1,000,000,000s add up to -294967296 in an int. So a 4Sum that uses int sums, given [1000000000, 1000000000, 1000000000, 1000000000] and target -294967296, prints [[1000000000, 1000000000, 1000000000, 1000000000]]: an answer that's off by 4,294,967,296. Use long (Java) or long long (C++).

A shortcut that assumes positive numbers. Add "stop when nums[a] > target" to 4Sum, and [-5, -4, -3, -2] with target -14 returns []. But -5 + -4 + -3 + -2 = -14. The shortcut forgot that adding negative numbers makes the sum smaller. The safe version checks the smallest sum this first number can still make: stop when nums[a] + nums[a + 1] + nums[a + 2] + nums[a + 3] > target, because every later choice is bigger.

Check yourself

Quiz

1 / 5

Multiple choice

A 3Sum solution skips the fixed number when nums[i] == nums[i + 1]. On [-4, -1, -1, 0, 1, 2], which triplet does it lose?

Practice problems

From easier to harder:

3Sum: the fixed number plus two pointers, with both duplicate skips.
4Sum: one more loop, 64-bit sums, and no shortcut that assumes positive numbers.
Number of Subsequences That Satisfy the Given Sum Condition: count in bulk, with 2^(right − left) instead of right − left.

Next in this section: pointers that move in the same direction, to change an array in place.