3Sum

Return every unique group of three numbers whose sum is zero.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

3Sum: After sorting and fixing one value, pointer moves discard pairs that cannot sum to its complement.

Input and goalReturn every unique group of three numbers whose sum is zero.

Sort and test first -4Input [-1, 0, 1, 2, -1, -4] sorts to [-4, -1, -1, 0, 1, 2]. With fixed -4, -4 + -1 + 2 = -3, so move L right.

fixed i=0-40L=1-11-120314R=525

coveredRangepair search [1..5]total-4 + -1 + 2 = -3 < 0moveL: 1 -> 2

Recognize it

The result needs unique triples satisfying a sum equation; sorting is allowed, and fixing one member reduces the remaining choice to a pair with an ordered sum.

Keep true

For a fixed index, every pair outside [L, R] is already emitted or safely discarded. If the total is low, no pair using the current L can work; if high, no pair using the current R can work.

Reuse it

After sorting, fix enough values to reduce k-sum to 2-sum, then use order to discard an entire boundary at once; carry duplicate-skipping rules at every fixed level.

Pattern: Sort, fix one value, then use two pointers.

Simple idea: Fix the first value. The remaining problem is Two Sum on a sorted range. If the sum is too small, move the left pointer. If it is too large, move the right pointer.

def three_sum(nums: list[int]) -> list[list[int]]:
   nums.sort()
   answer: list[list[int]] = []

   for index, first in enumerate(nums):
      if index > 0 and first == nums[index - 1]:
         continue

      left, right = index + 1, len(nums) - 1
      while left < right:
         total = first + nums[left] + nums[right]
         if total < 0:
            left += 1
         elif total > 0:
            right -= 1
         else:
            answer.append([first, nums[left], nums[right]])
            left += 1
            right -= 1
            while left < right and nums[left] == nums[left - 1]:
               left += 1

   return answer

Cost: $O(n^2)$ time and $O(1)$ extra space, not counting sorting and the answer.