3sum

Intuition

The task is to find all unique triplets in the array that sum to zero. This is a variation of the two-pointer approach often used for finding pairs that meet a condition. By sorting the array, we can efficiently find these triplets by combining a fixed left pointer with two moving pointers.

Approach

Below is the step-by-step breakdown of the approach:

1. Sort the Array:
   • Sort nums in ascending order. This allows us to use two pointers effectively.
2. Iterate with Fixed Pointer:
   • For each index left, treat nums[left] as the first number of the triplet.
   • If nums[left] is greater than zero, break the loop, as all subsequent numbers will also be positive, making it impossible to reach a sum of zero.
3. Skip Duplicates:
   • If nums[left] is the same as the previous number, skip it to avoid duplicate triplets.
4. Two-Pointer Technique:
   • Initialize middle at left + 1 and right at nums.length - 1.
   • Calculate sum = nums[left] + nums[middle] + nums[right].
     • If sum is zero, add the triplet [nums[left], nums[middle], nums[right]] to the result and move both pointers to avoid duplicates.
     • If sum is greater than zero, decrement right to reduce the sum.
     • If sum is less than zero, increment middle to increase the sum.
5. Return the Result:
   • Return the array of unique triplets.

Complexity

• Time complexity: $O(n^2)$, sorting takes O(nlogn), and the two-pointer traversal for each element takes O(n), making it O(n²) overall.
• Space complexity: $O(1)$ for extra space (excluding the result array).

Code

function threeSum(nums: number[]): number[][] {
  nums = nums.sort((a, b) => a - b)
  const ans: number[][] = []
  for (let left = 0; left < nums.length - 2; left++) {
    if (nums[left] > 0) break
    if (left > 0 && nums[left] === nums[left - 1]) continue
 
    let middle = left + 1
    let right = nums.length - 1
    while (middle < right) {
      const sum = nums[left] + nums[middle] + nums[right]
      if (sum === 0) {
        ans.push([nums[left], nums[middle], nums[right]])
        while (middle < right && nums[middle] === nums[middle + 1]) middle++
        while (middle < right && nums[right] === nums[right - 1]) right--
        middle++
        right--
      } else if (sum > 0) {
        right--
      } else {
        middle++
      }
    }
  }
  return ans
}