3Sum — Sort + Two Pointers

What does it solve?

Find all unique triplets that sum to zero. The brute force is O(N³); sorting plus two pointers cuts it to O(N²) and makes deduping trivial.

Key insight: sort first. Fix index i, then run two pointers lo and hi on the remainder. If the sum is too small, move lo up; too large, move hi down; exactly zero, record it. Sorting lets you skip duplicates so each triplet appears once.

The core idea

// sort, fix i, two-pointer the rest
sort(nums)
for i in 0..n-3:
  lo=i+1, hi=n-1
  while lo<hi:
    s = a[i]+a[lo]+a[hi]
    s<0 → lo++ ; s>0 → hi-- ; s==0 → record

Complexity

Time complexity

O(N²)

O(N log N) sort, then for each fixed i an O(N) two-pointer sweep → O(N²) dominates.

Space complexity

O(1)

Beyond the output list, only a few indices. Sorting is in place; no hash map required.

Examples & edge cases

Live animation — fix i, converge lo & hi on the sorted array

fixed i lo pointer hi pointer triplet found frozen (before i)

Sorted array

Press Play to begin…

Triplets found

none yet

Current step detail

i = — lo = — hi = — triplets = —

Step — of —

fixed value

—

nums[i]

current sum

—

a[i]+a[lo]+a[hi]

window width

—

hi − lo

triplets

—

unique found

Select an example and press Play to start.

✓ Done

Speed Medium

Step-by-step table

Step	i	lo	hi	sum	vs 0	Action	triplets

C++ implementation

three_sum.cpp

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

// All unique triplets summing to zero
vector<vector<int>> threeSum(vector<int>& a) {
    sort(a.begin(), a.end());
    int n = a.size();
    vector<vector<int>> res;

    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && a[i] == a[i-1]) continue; // skip duplicate fixed value
        int lo = i + 1, hi = n - 1;
        while (lo < hi) {
            int s = a[i] + a[lo] + a[hi];
            if (s < 0) lo++;
            else if (s > 0) hi--;
            else {
                res.push_back({a[i], a[lo], a[hi]});
                while (lo < hi && a[lo] == a[lo+1]) lo++; // skip dupes
                while (lo < hi && a[hi] == a[hi-1]) hi--;
                lo++; hi--;
            }
        }
    }
    return res;
}

int main() {
    vector<int> a = {-1,0,1,2,-1,-4};
    for (auto& t : threeSum(a))
        cout << t[0] << "," << t[1] << "," << t[2] << "\n"; // -1,-1,2 and -1,0,1
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars