3Sum

Fixing one number turns the problem into finding two numbers in the remaining suffix that sum to -nums[i]. Sorting the array organizes duplicate values next to each other, allowing two pointers to sweep inward while skipping identical adjacent values to guarantee that every generated triplet is unique.

Full solution

Sort, then fix one number and two-pointer scan the rest for the complement sum — O(n^2) time, O(1) extra space, and the sorted order makes duplicate-triplet skipping trivial on both pointers.

from typing import List


def three_sum(nums: List[int]) -> List[List[int]]:
    nums.sort()
    n = len(nums)
    result = []
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # skip duplicate anchors
        if nums[i] > 0:
            break  # smallest remaining value is positive, no zero sum possible
        low, high = i + 1, n - 1
        while low < high:
            total = nums[i] + nums[low] + nums[high]
            if total < 0:
                low += 1
            elif total > 0:
                high -= 1
            else:
                result.append([nums[i], nums[low], nums[high]])
                low += 1
                high -= 1
                while low < high and nums[low] == nums[low - 1]:
                    low += 1
                while low < high and nums[high] == nums[high + 1]:
                    high -= 1
    return result

function threeSum(nums) {
  nums = [...nums].sort((a, b) => a - b);
  const n = nums.length;
  const result = [];
  for (let i = 0; i < n - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue; // skip duplicate anchors
    if (nums[i] > 0) break; // smallest remaining value is positive, no zero sum possible
    let low = i + 1;
    let high = n - 1;
    while (low < high) {
      const total = nums[i] + nums[low] + nums[high];
      if (total < 0) {
        low++;
      } else if (total > 0) {
        high--;
      } else {
        result.push([nums[i], nums[low], nums[high]]);
        low++;
        high--;
        while (low < high && nums[low] === nums[low - 1]) low++;
        while (low < high && nums[high] === nums[high + 1]) high--;
      }
    }
  }
  return result;
}

The theory behind it

Arrays — the ground this problem stands on. All Arrays problems

What Arrays is

An array is a row of fixed boxes laid side by side in computer memory, like numbered lockers in a hallway. Because each box occupies identical space and sits directly next to its neighbors, jumping to locker zero or locker ten thousand takes the exact same tiny fraction of time. Every box holds an item of the same type, addressed by an offset number called an index.

When to reach for it

Reach for an array when items arrive in a known sequence and need immediate retrieval by position number. Problems asking for running totals, prefix accumulations, cyclic rotations, or in-place rearrangements signal array mechanics. Whenever constraints require constant-time random lookups or contiguous cache scans across fixed collections, a flat sequence is the default container.

How the pattern works

Visualize a tape with zero-indexed slots stretching from start to end. Keep track of write and read cursors when modifying contents without allocating helper buffers. For running computations, maintain an invariant such as having processed all elements left of the current index while pending elements wait to the right. When modifying entries in place, consider scanning backwards from the end so unread data is not overwritten.