3Sum — Two Pointers

What does it solve?

Given an integer array, find all unique triplets [a, b, c] such that a + b + c = 0. The solution set must not contain duplicate triplets.

Sort the array first, then fix one element i and use a two-pointer scan with lo and hi moving inward to find all valid pairs.

The core idea

// sort, then for each i:
for i = 0 → n-3:
  if i>0 && arr[i]==arr[i-1]: skip
  lo=i+1, hi=n-1
  while lo < hi:
    s = arr[i]+arr[lo]+arr[hi]
    if s==0: record; skip dups
    elif s<0: lo++ else: hi--

▶ Visualiser

Fixed anchor i

lo pointer

hi pointer

Triplet found

Skipped duplicate

a[i]—

a[lo]—

a[hi]—

sum—

Triplets found so far

none yet

Step — of —

Anchor i

—

value

lo / hi

—

indices

Current sum

—

target: 0

Triplets found

unique

Select an example and press Play to start.

✓ Complete

Speed Medium

Step-by-step table

#	i	lo	hi	a[i]	a[lo]	a[hi]	Sum	Action

C++ implementation

three_sum.cpp

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

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());   // sort first
    vector<vector<int>> res;
    int n = nums.size();

    for (int i = 0; i < n - 2; i++) {
        // skip duplicate anchors
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        // early exit: smallest possible sum > 0
        if (nums[i] > 0) break;

        int lo = i + 1, hi = n - 1;
        while (lo < hi) {
            int s = nums[i] + nums[lo] + nums[hi];
            if (s == 0) {
                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--;
            } else if (s < 0) {
                lo++;   // need larger sum
            } else {
                hi--;   // need smaller sum
            }
        }
    }
    return res;
}

int main() {
    vector<int> nums = {-1, 0, 1, 2, -1, -4};
    auto res = threeSum(nums);
    // res: [[-1,-1,2],[-1,0,1]]
    return 0;
}

Complexity

Time complexity

O(n²)

Sorting costs O(n log n). The outer loop runs O(n) times; for each anchor, the two-pointer inner scan is O(n). Total: O(n²) which dominates the sort.

Space complexity

O(1)

Only three index variables (i, lo, hi) plus the output list. No auxiliary hash set or extra array is needed — sorting in-place keeps extra space constant.

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars