3Sum

Approach Summary

Sort the array, fix one element, then use two pointers for the rest. Skip duplicates carefully to avoid duplicate triplets.

Full Solution & Approach

Three-sum reduces to two-sum on a sorted array. First sort the array — this is what lets you skip duplicates and use two pointers. Fix the first element with index i and run a two-pointer scan on the subarray to its right to find pairs that sum to -nums[i]. Move lo from i + 1 and hi from the end inward: if the three values sum to 0, record the triplet and advance both pointers past any duplicates. If the sum is negative, the total is too small, so move lo right; if positive, move hi left. The outer loop skips any i whose value equals the previous i to avoid duplicate triplets. Sorting costs O(n log n), and the two-pointer scan runs in O(n) for each i, giving O(n²) overall.

Sorting costs O(n log n); for each of n fixed first elements the two-pointer scan is O(n), giving O(n²) total. Space is O(1) for the pointers plus whatever the sort needs in place.

Solution Code

Solution

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

function threeSum(nums) {
  nums.sort((a, b) => a - b);
  const res = [];
  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    let lo = i + 1, hi = nums.length - 1;
    while (lo < hi) {
      const total = nums[i] + nums[lo] + nums[hi];
      if (total === 0) {
        res.push([nums[i], nums[lo], nums[hi]]);
        lo++; hi--;
        while (lo < hi && nums[lo] === nums[lo - 1]) lo++;
        while (lo < hi && nums[hi] === nums[hi + 1]) hi--;
      } else if (total < 0) lo++;
      else hi--;
    }
  }
  return res;
}

public 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 total = nums[i] + nums[lo] + nums[hi];
            if (total == 0) {
                res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                lo++; hi--;
                while (lo < hi && nums[lo] == nums[lo - 1]) lo++;
                while (lo < hi && nums[hi] == nums[hi + 1]) hi--;
            } else if (total < 0) lo++;
            else hi--;
        }
    }
    return res;
}

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

Edge Cases to Watch

All zeros — exactly one triplet [0, 0, 0]
Duplicates in the array — must skip identical i values and equal lo/hi values to avoid repeating triplets
Fewer than 3 elements — return []
No valid triplet — return []

How to Recognize This Pattern

Find all triplets summing to zero
No duplicate triplets

Complexity Analysis

Time Complexity

O(n²)

Space Complexity

O(n)