3Sum

You're given an integer array nums. Return every distinct triplet [a, b, c] of values such that a + b + c == 0 and the three values come from three different positions in the array.

Two triplets count as the same if they contain the same values, so the answer must not contain duplicates like [-1, 0, 1] and [0, 1, -1]. You may return the triplets in any order, and the values within each triplet in any order.

Fix one value a, and the rest of the problem is "find two values that sum to -a", which is Two Sum. On a sorted array, Two Sum takes a single two-pointer sweep: start at both ends, and move the left pointer up when the sum is too small or the right pointer down when it's too big.

Sorting also solves the duplicate problem for free. Equal values end up next to each other, so you can skip a repeated a in the outer loop and skip repeated values after recording a triplet in the inner sweep. Every triplet then comes out in non-decreasing order exactly once, with no set needed.

Another hint: once the sorted a is positive, everything to its right is positive too, so no further triplet can sum to zero.

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

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

Open by connecting it to Two Sum: "if I fix one number, I need two others that sum to its negative." Then explain why you sort: it unlocks the two-pointer sweep and makes duplicate handling a matter of skipping neighbors. Interviewers are mostly checking whether you can de-duplicate cleanly without leaning on a set of tuples.

Before finishing, trace an input with heavy duplicates such as [-1, -1, 2, 2] or all zeros. That's where off-by-one skip logic breaks.