Coding problem · Medium · Two Pointers

3Sum

Medium Algorithms & data structures Most askedSeen at Meta, Amazon, Microsoft, Bloomberg

Given an integer array nums, return all unique triplets [a, b, c] such that a + b + c == 0. The triplets and the numbers inside them may be returned in any order, but the result must not contain duplicate triplets.

Example 1

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2

Input: nums = [0,1,1]
Output: []

Constraints

3 <= nums.length <= 3000

Hints

Hint 1

Sort first. Fix the first number, then the rest is Two Sum on a sorted array.

Hint 2

Skip equal neighbours (for the fixed number and after each match) to avoid duplicate triplets.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n²) · Space O(1) extra (besides sorting)

Sort, then for each index i (skipping duplicates of nums[i]) run two pointers on the rest: if the sum is too small move lo right, too big move hi left, and on a match record it and skip duplicates on both sides. Sorting dominates nothing — the nested scan is O(n²).

Reference solution

function threeSum(nums) {
  nums = [...nums].sort((a, b) => a - b);
  const out = [];
  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 sum = nums[i] + nums[lo] + nums[hi];
      if (sum < 0) lo++;
      else if (sum > 0) hi--;
      else {
        out.push([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 out;
}

function threeSum(input: number[]): number[][] {
  const nums = [...input].sort((a, b) => a - b);
  const out: number[][] = [];
  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 sum = nums[i] + nums[lo] + nums[hi];
      if (sum < 0) lo++;
      else if (sum > 0) hi--;
      else {
        out.push([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 out;
}

def three_sum(nums: list[int]) -> list[list[int]]:
    nums = sorted(nums)
    out = []
    for i in range(len(nums) - 2):
        if i and nums[i] == nums[i - 1]:
            continue
        lo, hi = i + 1, len(nums) - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s < 0:
                lo += 1
            elif s > 0:
                hi -= 1
            else:
                out.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, hi = lo + 1, hi - 1
    return out

<?php

function threeSum(array $nums): array
{
    sort($nums);
    $n = count($nums);
    $out = [];
    for ($i = 0; $i < $n - 2; $i++) {
        if ($i > 0 && $nums[$i] === $nums[$i - 1]) {
            continue;
        }
        [$lo, $hi] = [$i + 1, $n - 1];
        while ($lo < $hi) {
            $sum = $nums[$i] + $nums[$lo] + $nums[$hi];
            if ($sum < 0) {
                $lo++;
            } elseif ($sum > 0) {
                $hi--;
            } else {
                $out[] = [$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 $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 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 {
                    out.add(List.of(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 out;
    }
}

Common mistakes

Using a set of tuples to dedupe works but hides the cleaner duplicate-skipping logic interviewers look for.

Valid Palindrome · Easy
Container With Most Water · Medium