3Sum

medium array two pointers

Problem

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.

Sort the array. Fix one anchor i, then look for two values to its right that sum to −nums[i] using a left/right two-pointer sweep. Skip equal anchors and equal pointer moves to avoid duplicates.

Inputnums = [-2, -1, 0, 1, 2, -1]

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

nums (comma-separated)

def three_sum(nums):
    nums = sorted(nums)
    out = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        l, r = i + 1, len(nums) - 1
        while l < r:
            total = nums[i] + nums[l] + nums[r]
            if total == 0:
                out.append([nums[i], nums[l], nums[r]])
                while l < r and nums[l] == nums[l + 1]:
                    l += 1
                while l < r and nums[r] == nums[r - 1]:
                    r -= 1
                l += 1
                r -= 1
            elif total < 0:
                l += 1
            else:
                r -= 1
    return out

function threeSum(nums) {
  nums = nums.slice().sort(function (a, b) { return a - b; });
  const out = [];
  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    let l = i + 1, r = nums.length - 1;
    while (l < r) {
      const sum = nums[i] + nums[l] + nums[r];
      if (sum === 0) {
        out.push([nums[i], nums[l], nums[r]]);
        while (l < r && nums[l] === nums[l + 1]) l++;
        while (l < r && nums[r] === nums[r - 1]) r--;
        l++; r--;
      } else if (sum < 0) l++;
      else r--;
    }
  }
  return out;
}

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> out = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1, r = nums.length - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    out.add(List.of(nums[i], nums[l], nums[r]));
                    while (l < r && nums[l] == nums[l + 1]) l++;
                    while (l < r && nums[r] == nums[r - 1]) r--;
                    l++; r--;
                } else if (sum < 0) l++;
                else r--;
            }
        }
        return out;
    }
}

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

Explanation

We need every unique triplet that adds to zero, with no repeats. The plan is to sort the array, fix one anchor, and find the other two with a two-pointer sweep.

For each anchor i, we need two later values summing to -nums[i]. A left pointer l starts after i and a right pointer r starts at the end. Their sorted positions tell us how to move: if the total is too small, push l right; too big, pull r left; exactly zero, we found a triplet.

Avoiding duplicates is the careful part. We skip an anchor equal to the previous one (nums[i] == nums[i-1]), and after a hit we skip over equal nums[l] and equal nums[r] values before moving on.

Example: sorted [-2, -1, -1, 0, 1, 2]. Anchor -2 needs a pair summing to 2; l=0 and r=2 give 0 + 2, so [-2, 0, 2] is recorded.

Each anchor sweeps the rest in one linear pass, giving an n-squared solution while the skip steps keep the output free of duplicate triplets.

Time: O(n²) Space: O(1) extra