SyntaxPilot
Courses/DSA and Coding Problems/Lesson 6
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 6 of 90

Two pointers: 3Sum

queued

These are the notes for DSA episode 6. 3Sum (LeetCode 15) asks for every unique triplet that adds up to zero. Three loops take O(n³) and print the same triplet more than once. Sorting the array unlocks the two pointer technique: fix one number, then walk two pointers towards each other, for O(n²) time and no duplicates. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.

The problem, in real life

A shop keeps a ledger: money in is positive, money out is negative. An auditor looks for money moving in a circle: groups of three entries that cancel out to exactly zero, like +5, -3, -2. The report must list each group once, even if the same three amounts appear in several places.

Problem statement

Given an integer array nums, return all triplets [nums[i], nums[j], nums[k]] with i, j, k different and nums[i] + nums[j] + nums[k] == 0. The answer must not contain duplicate triplets. Constraints: 3 ≤ n ≤ 3000, -10⁵ ≤ nums[i] ≤ 10⁵.

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

Brute force, take 1: three loops

import java.util.*;

public class Main {
    static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                for (int k = j + 1; k < n; k++)
                    if (nums[i] + nums[j] + nums[k] == 0)
                        res.add(Arrays.asList(nums[i], nums[j], nums[k]));
        return res;
    }
    public static void main(String[] args) {
        System.out.println(threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
    }
}

Output:

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

[-1, 0, 1] and [0, 1, -1] are the same group in a different order. Wrong output.

Brute force, take 2: sort each triplet, use a HashSet

Set<List<Integer>> set = new HashSet<>();
int n = nums.length;
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        for (int k = j + 1; k < n; k++)
            if (nums[i] + nums[j] + nums[k] == 0) {
                List<Integer> t = Arrays.asList(nums[i], nums[j], nums[k]);
                Collections.sort(t);
                set.add(t);
            }
return new ArrayList<>(set);

Output for the example:

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

Correct. But on 5,000 entries:

int n = 5000, nums[] = new int[n];
for (int i = 0; i < n; i++) nums[i] = (int) (i * 7919L % 20001) - 10000;
System.out.println(threeSum(nums).size() + " triplets");

Result: Time Limit Exceeded.

Why it is slow

There are n(n-1)(n-2)/6 triples: O(n³). For n = 5,000 that is about 2 × 10¹⁰, plus a sort and a hash for every answer.

The way in: fix the first number. If it is -1, you need two more numbers that add up to +1. That is Two Sum (episode 2), and on a sorted array, Two Sum has a trick that needs no hash map.

Two pointers on a sorted array

Picture a shelf of price tags sorted from cheapest to costliest. You want two items that cost exactly 10 together.

  • Left hand on the cheapest, right hand on the costliest. Add the prices.
  • Too cheap? The cheapest item can't be in any answer, even with the costliest partner. Move the left hand right.
  • Too costly? The costliest item can't be in any answer, even with the cheapest partner. Move the right hand left.
  • Each step throws one item away for good, so one walk, O(n), finds the pair.
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] a = {1, 3, 4, 6, 8, 11};
        int target = 10, lo = 0, hi = a.length - 1;
        while (lo < hi) {
            int sum = a[lo] + a[hi];
            if (sum == target) {
                System.out.println(a[lo] + " + " + a[hi]);
                break;
            }
            if (sum < target) lo++;
            else hi--;
        }
    }
}

Output:

4 + 6

The walk: 1 + 11 = 12 (too big, hi moves), 1 + 8 = 9 (too small, lo moves), 3 + 8 = 11 (hi moves), 3 + 6 = 9 (lo moves), 4 + 6 = 10. Five steps instead of fifteen pairs.

The key insight: 3Sum = a loop + two pointers

  1. Sort nums.
  2. For each i, find lo, hi after i with nums[lo] + nums[hi] = -nums[i] using two pointers.
  3. Sum below 0 → lo++. Above 0 → hi--. Exactly 0 → record the triplet.
  4. Duplicates sit side by side after sorting, so skip them: skip i when nums[i] == nums[i - 1], and after a hit move lo and hi past equal values.

Dry run: sorted [-4, -1, -1, 0, 1, 2]

i (value) lo, hi (values) sum action
0 (-4) -1, 2 -3 too small, lo++
0 (-4) -1, 2 / 0, 2 / 1, 2 -3, -2, -1 too small each time, lo meets hi
1 (-1) -1, 2 0 record [-1, -1, 2], move both
1 (-1) 0, 1 0 record [-1, 0, 1], move both, pointers cross
2 (-1) same value as i = 1: skip
3 (0) 1, 2 3 too big, hi--, pointers meet

Answer: [[-1, -1, 2], [-1, 0, 1]], each exactly once, with no HashSet.

The optimal solution

import java.util.*;

public class Main {
    static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int lo = i + 1, hi = nums.length - 1;
            while (lo < hi) {
                int sum = nums[i] + nums[lo] + nums[hi];
                if (sum < 0) lo++;
                else if (sum > 0) hi--;
                else {
                    res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                    while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
                    while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
                    lo++;
                    hi--;
                }
            }
        }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
        System.out.println(threeSum(new int[]{0, 0, 0, 0}));
        System.out.println(threeSum(new int[]{0, 1, 1}));
        System.out.println(threeSum(new int[]{-2, 0, 1, 1, 2}));
    }
}

Output:

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

On the 5,000 entries that timed out:

long t = System.nanoTime();
int found = threeSum(nums).size();
System.out.println(found + " triplets   " + (System.nanoTime() - t) / 1000000 + " ms");

Output (the time varies from run to run):

416024 triplets   234 ms

The same solution in C++ and Python

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> threeSum(vector<int> nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    int n = nums.size();
    for (int i = 0; i + 2 < n; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int lo = i + 1, hi = n - 1;
        while (lo < hi) {
            int sum = nums[i] + nums[lo] + nums[hi];
            if (sum < 0) lo++;
            else if (sum > 0) hi--;
            else {
                res.push_back({nums[i], nums[lo], nums[hi]});
                while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
                while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
                lo++; hi--;
            }
        }
    }
    return res;
}

int main() {
    for (auto& t : threeSum({-1, 0, 1, 2, -1, -4}))
        cout << "[" << t[0] << ", " << t[1] << ", " << t[2] << "]\n";
}

Output: [-1, -1, 2] and [-1, 0, 1], one per line. (i + 2 < n avoids the unsigned trap of nums.size() - 2 when the vector is short.)

def three_sum(nums):
    nums = sorted(nums)
    res, n = [], len(nums)
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        lo, hi = i + 1, n - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s < 0:
                lo += 1
            elif s > 0:
                hi -= 1
            else:
                res.append([nums[i], nums[lo], nums[hi]])
                while lo < hi and nums[lo] == nums[lo + 1]:
                    lo += 1
                while lo < hi and nums[hi] == nums[hi - 1]:
                    hi -= 1
                lo += 1
                hi -= 1
    return res

print(three_sum([-1, 0, 1, 2, -1, -4]))  # [[-1, -1, 2], [-1, 0, 1]]
print(three_sum([0, 0, 0, 0]))          # [[0, 0, 0]]

Complexity

Approach Time Extra space n = 5,000
Three loops + HashSet O(n³) O(answers) Time Limit Exceeded
Sort + two pointers O(n log n + n²) = O(n²) O(1) besides the output and the sort milliseconds

No algorithm is known that is much faster than O(n²) for 3Sum in general, so O(n²) is the expected interview answer.

Common mistakes

Mistake What you see Why Fix
if (nums[i] == nums[i + 1]) continue; [[-1, 0, 1]]: [-1, -1, 2] is lost skips the first of equal values, the only i that can use both if (i > 0 && nums[i] == nums[i - 1]) continue;
No skip after a hit [[-2, 0, 2], [-2, 0, 2]] for [-2, 0, 0, 2, 2] lo and hi land on equal values again skip equal lo and hi, then move both
Three loops, no sort of the triplet [-1, 0, 1] and [0, 1, -1] same group, other order sort, then skip duplicates
Two pointers on an unsorted array missing triplets moving a pointer only throws away useless values when the array is sorted Arrays.sort(nums) first
nums.size() - 2 in C++ on a short vector huge loop, crash size() is unsigned: 1 - 2 wraps around write i + 2 < n with int n

Mini project: the auditor's report

Read a list of ledger entries (positive and negative rupee amounts) and print every group of three that cancels out, formatted like +500, -300, -200. Then extend it to groups of four (4Sum): fix two numbers with two loops, two-pointer the rest, and skip duplicates at every level. Try it on [1, 0, -1, 0, -2, 2], which has three groups of four: [-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1].

Practice

  1. 3Sum Closest (LeetCode 16): the triplet sum closest to target = 1 in [-1, 2, 1, -4].
Solution

Same loop + two pointers, but keep the sum with the smallest |sum - target|, moving lo when sum < target and hi otherwise. Answer: 2 (-1 + 2 + 1).

  1. Two Sum II (LeetCode 167): sorted [2, 7, 11, 15], target 9. Return the 1-based positions.
Solution

Two pointers from both ends: 2 + 15 too big, 2 + 11 too big, 2 + 7 = 9. Answer: [1, 2], O(n) time, O(1) space.

  1. Count the triplets with sum less than 2 in [-2, 0, 1, 3] (LeetCode 259).
Solution

Sort, fix i, two pointers: when nums[i] + nums[lo] + nums[hi] < target, every hi' between lo + 1 and hi also works, so add hi - lo and move lo; otherwise move hi. Answer: 2 ([-2, 0, 1], [-2, 0, 3]).

  1. Why does the outer loop stop at nums.length - 2?
Solution

lo = i + 1 and hi = n - 1 must be two more distinct positions, so i can be at most n - 3.

Quick quiz

What does threeSum(new int[]{-2, -2, 0, 2, 4, -4}) return?

  • 1 triplet
  • 2 triplets
  • 3 triplets
  • 4 triplets
Answer

3 triplets. Sorted: -4, -2, -2, 0, 2, 4. The program prints [[-4, 0, 4], [-2, -2, 4], [-2, 0, 2]]. [-4, 2, 2] is not allowed: there is only one 2.

Interview questions

  1. Why sort first? Sorting makes the two-pointer moves safe (too small → the smallest is useless) and puts duplicates next to each other so they can be skipped.
  2. Prove the two-pointer step is safe. If nums[lo] + nums[hi] is too small, then nums[lo] plus any value at or before hi is also too small, so lo can be discarded. The mirror argument works for hi.
  3. How do you avoid duplicate triplets without a HashSet? Skip i when it equals nums[i - 1], and after each hit, advance lo and hi past equal values.
  4. Time and space? O(n²) time; O(1) extra space apart from the output (Java's Arrays.sort on int[] uses O(log n) stack).
  5. Generalize to kSum. Recursively fix one number and solve (k-1)Sum on the rest; the base case is two pointers. Time O(n^(k-1)).

Glossary

Term Meaning
Triplet A group of three values taken from three different positions
Unique triplets No two triplets with the same three values, in any order
Two pointers Two indexes that move through an array (here, from both ends towards each other)
Sorted array Values in non-decreasing order; required for the two-pointer moves
Duplicate skip Moving past equal neighbours so each value is tried once in each role
Arrays.asList Java: makes a fixed-size List from values
HashSet A set that stores each distinct element once, with O(1) average lookups
O(n log n) The cost of sorting n items with a good sorting algorithm
kSum The general problem: k numbers that add up to a target

Summary

  • Three loops are O(n³) and repeat triplets in different orders.
  • Two pointers on a sorted array find a pair with a given sum in O(n): too small → move left up, too big → move right down.
  • 3Sum = sort, then for each i, two pointers on the rest for -nums[i].
  • Skip nums[i] == nums[i - 1], and skip equal lo/hi after a hit. O(n²) time, O(1) extra space.

Next episode: Container With Most Water.