Marauder Bot

Problem

You are given an array of integers. Find every group of three distinct positions whose values add up to zero, and return the triplets themselves rather than their indices. The same triplet of values must not appear more than once in the result, even if it can be formed from different positions in the array.

Example. For [-1, 0, 1, 2, -1, -4], the valid triplets are [-1, -1, 2] and [-1, 0, 1].

Key idea

Checking every group of three numbers directly costs O(n³), and deduplicating the results afterward is awkward. Sorting the array first turns this into a smaller, already-solved problem: for each position, fix that value as the first number of the triplet, and then look for two more numbers later in the array that sum to its negation (exactly the sorted two-pointer search used in Two Sum II). Sorting also makes duplicate triplets easy to avoid, since equal values end up adjacent: skip over repeats of the fixed first number, and skip over repeats while advancing either pointer during the two-pointer scan. Once the fixed number is positive, every remaining number is at least as large, so no further triplet can sum to zero and the scan can stop early.

Solution

function threeSum(nums: number[]): number[][] {
  const sorted = [...nums].sort((a, b) => a - b);
  const triplets: number[][] = [];

  for (let i = 0; i < sorted.length - 2; i++) {
    if (sorted[i] > 0) {
      break; // fixed value is positive, no later triplet can sum to zero
    }
    if (i > 0 && sorted[i] === sorted[i - 1]) {
      continue; // skip duplicate fixed values
    }

    let left = i + 1;
    let right = sorted.length - 1;

    while (left < right) {
      const sum = sorted[i] + sorted[left] + sorted[right];

      if (sum === 0) {
        triplets.push([sorted[i], sorted[left], sorted[right]]);
        left++;
        right--;
        // skip duplicate values on both pointers to avoid duplicate triplets
        while (left < right && sorted[left] === sorted[left - 1]) {
          left++;
        }
        while (left < right && sorted[right] === sorted[right + 1]) {
          right--;
        }
      } else if (sum < 0) {
        left++;
      } else {
        right--;
      }
    }
  }

  return triplets;
}

Complexity

Time: O(n²). Sorting costs O(n log n), then an O(n) two-pointer scan runs for each of n starting positions.
Space: O(1) extra beyond the sort's own working space and the output list.

Watch out for

Skip duplicate values at all three positions (the fixed index and both pointers), or the same triplet appears multiple times.
Sort the array before anything else; the two-pointer narrowing only works because the values are ordered.
Stop as soon as the fixed value exceeds zero, since three non-negative numbers with at least one positive cannot sum to zero.

Pattern

This is the "fix one, two-pointer the rest" pattern for reducing a k-sum problem by one dimension. The same idea of sorting and peeling off one index at a time extends naturally to 4Sum and other fixed-size subset-sum variants.

3Sum