ACAlgoGeeks

1sort(nums)   → [-4, -1, -1, 0, 1, 2]
2for i = 0 to n-3:   → i = 0 (nums[i]=-4)
3  if i > 0 and nums[i] == nums[i-1]: skip
4  left = i+1, right = n-1   → left = 1, right = 5
5  while left < right:
6    sum = nums[i] + nums[left] + nums[right]   = -4+-1+2 = -3
7    if sum == 0: record triplet, move left/right
8    else if sum < 0: left++
9    else: right--

1function threeSum(nums: number[]): number[][] {
2  nums.sort((a, b) => a - b);
3  const result: number[][] = [];
4  for (let i = 0; i < nums.length - 2; i++) {
5    if (i > 0 && nums[i] === nums[i - 1]) continue;
6    let left = i + 1, right = nums.length - 1;
7    while (left < right) {
8      const sum = nums[i] + nums[left] + nums[right];
9      if (sum === 0) {
10        result.push([nums[i], nums[left], nums[right]]);
11        while (left < right && nums[left] === nums[left + 1]) left++;
12        left++; right--;
13      } else if (sum < 0) left++;
14      else right--;
15    }
16  }
17  return result;
18}

About

3Sum finds all unique triplets in an array that sum to zero using two pointers. Sort the array, fix one index i, then use two pointers (left, right) to find pairs that sum to -nums[i]. Part of Two Pointers (Advanced Variants).

Step-by-step explanation

Step 1 — Sort: Sort the array in ascending order. This allows us to use two pointers to find pairs that sum to a target without missing any and to skip duplicates easily.

Step 2 — Fix first element: Loop i from 0 to n - 3. For each i, we look for pairs (left, right) such that nums[i] + nums[left] + nums[right] = 0, i.e. nums[left] + nums[right] = -nums[i]. Skip duplicate i: if i > 0 and nums[i] == nums[i-1], skip this i to avoid duplicate triplets.

Step 3 — Two pointers: Set left = i + 1 and right = n - 1. While left < right, compute sum = nums[i] + nums[left] + nums[right]. If sum == 0, record the triplet [nums[i], nums[left], nums[right]], then advance left (and optionally skip duplicates) and decrement right. If sum < 0, increment left to increase the sum; if sum > 0, decrement right to decrease it.

Step 4 — Uniqueness: When we record a triplet, we skip over duplicate values for left (and similarly for right if needed) so that the same triplet is not added twice. After the loop, we have all unique triplets that sum to zero. Time O(n²), space O(1) excluding output.

What's happening

Fix i=0 (value -4), set left=1, right=5.

Time Complexity

O(n²)

Space Complexity

O(1)

Output

Fix i=0 (value -4), set left=1, right=5.