#14 · Two Pointers

3Sum

Given an integer array, return all unique triplets [a, b, c] with a + b + c = 0. The solution set must not contain duplicate triplets.

MediumLeetCode

Active
Found
Window
Visited
Rejected

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Sorted array + two pointers

After sorting, fix the first value and look for a pair summing to its negation with one pointer at each end of the remaining range. A sum that is too small can only be fixed by moving left up; one that is too big only by moving right down.

Memory layout

A single contiguous sorted array scanned from both ends: sequential access and cache friendly. The sort is the only allocation (a copy, if the input must stay untouched).

Operation	Cost
sort	O(n log n)
two-pointer scan per i	O(n)
total	O(n²) time, O(1)–O(n) extra space (sort dependent)

Hash set of seen values

For a fixed i, a set remembers the values already passed so that "is there an earlier value equal to −a[i] − a[j]?" is an O(1) lookup instead of a scan.

Memory layout

A hash table with up to n entries (scattered memory, so slower per step than two pointers) and rebuilt for every i.

Operation	Cost
lookup / insert	O(1) average
total	O(n²) time, O(n) extra space

Why it fits

3Sum reduces to n runs of Two Sum: fix one value and look for a pair summing to its negative. Sorted order lets each run use two pointers in O(n) with no hashing.
Sorting also turns duplicate avoidance into a simple rule: skip a value that equals its predecessor, both for the fixed i and for the pointers after a hit.
Monotonic structure gives pruning for free: once sorted[i] > 0, all later sums are positive, so the search can stop.

Why alternatives degrade

Three nested loops:: O(n³) triples (~1.7 × 10¹⁴ for n = 10⁵) and still needs a set to remove duplicate triples.
Hash set per i without sorting:: Finds triples, but deduplicating them needs a set of sorted keys (extra memory and hashing); sorting first makes duplicates adjacent so they can simply be skipped.
Sorting + binary search for the third value:: O(n² log n): the log factor is unnecessary when two pointers can walk the range in O(n).

Four approaches, from naive to production

1 · beginner

Three loops plus a dedupe set

time O(n³)space O(k) for k results

Try every triple of positions, keep the ones that sum to zero, and use a set of sorted triples to discard duplicates.

vector<vector<int>> threeSum(vector<int>& nums) {
    set<string> seen;
    vector<vector<int>> result;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if ((long long)nums[i] + nums[j] + nums[k] == 0) {
                    vector<int> triple = {nums[i], nums[j], nums[k]}; sort(triple.begin(), triple.end());
                    string key = to_string(triple[0]) + "," + to_string(triple[1]) + "," + to_string(triple[2]);
                    if (!seen.count(key)) {
                        seen.insert(key);
                        result.push_back(triple);
                    }
                }
            }
        }
    }
    return result;
}

public List<List<Integer>> threeSum(int[] nums) {
    Set<String> seen = new HashSet<>();
    List<List<Integer>> result = new ArrayList<>();
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if ((long) nums[i] + nums[j] + nums[k] == 0) {
                    int[] t = {nums[i], nums[j], nums[k]}; Arrays.sort(t);
                    List<Integer> triple = List.of(t[0], t[1], t[2]);
                    String key = t[0] + "," + t[1] + "," + t[2];
                    if (!seen.contains(key)) {
                        seen.add(key);
                        result.add(triple);
                    }
                }
            }
        }
    }
    return result;
}

def three_sum(nums: list[int]) -> list[list[int]]:
    seen: set[str] = set()
    result: list[list[int]] = []
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if nums[i] + nums[j] + nums[k] == 0:
                    triple = sorted([nums[i], nums[j], nums[k]])
                    key = ','.join(map(str, triple))
                    if key not in seen:
                        seen.add(key)
                        result.append(triple)
    return result

function threeSum(nums: number[]): number[][] {
  const seen = new Set<string>();
  const result: number[][] = [];
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      for (let k = j + 1; k < nums.length; k++) {
        if (nums[i] + nums[j] + nums[k] === 0) {
          const triple = [nums[i], nums[j], nums[k]].sort((a, b) => a - b);
          const key = triple.join(',');
          if (!seen.has(key)) {
            seen.add(key);
            result.push(triple);
          }
        }
      }
    }
  }
  return result;
}

Flaws & bottlenecks

About n³/6 triples: ~1.7 × 10¹⁴ for n = 10⁵, far beyond any time limit.
Duplicates are found, then discarded via string keys, so every duplicate still costs a sort and a join.
Does no pruning: it keeps going even when no remaining triple can reach zero.

Interviewer cross-questions

Why do duplicates appear at all?

Say: The input may repeat values (here two −1s), so the same multiset of values can be found at different index combinations: positions (0,1,2) and (1,2,4) both give [−1, 0, 1]. The problem asks for unique value triples, not unique positions.

How can you cut a factor of n?

Say: Fix two values and the third is determined (−a−b): look it up in a hash set (O(n²)), or sort and use two pointers for the pair (also O(n²)).

Is using a string key for dedupe good practice?

Say: It works but is wasteful (allocation, joining, hashing a string). Sorting the array first makes duplicates adjacent, so you can skip repeated values with an integer comparison and need no set at all.

2 · intermediate

Sort, then a hash set for the third value

time O(n²)space O(n)

Sort. For each i, scan j to its right, keeping a set of values seen so far; if −a[i] − a[j] is in the set, that is a triple. Skip repeated values using the sorted order.

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<int> sorted(nums); sort(sorted.begin(), sorted.end());
    vector<vector<int>> result;
    int n = sorted.size();
    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && sorted[i] == sorted[i - 1]) continue;
        unordered_set<long long> seen;
        for (int j = i + 1; j < n; j++) {
            long long need = -(long long)sorted[i] - sorted[j];
            if (seen.count(need)) {
                result.push_back({sorted[i], (int)need, sorted[j]});
                while (j + 1 < n && sorted[j] == sorted[j + 1]) j++;
            }
            seen.insert(sorted[j]);
        }
    }
    return result;
}

public List<List<Integer>> threeSum(int[] nums) {
    int[] sorted = nums.clone(); Arrays.sort(sorted);
    List<List<Integer>> result = new ArrayList<>();
    int n = sorted.length;
    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && sorted[i] == sorted[i - 1]) continue;
        Set<Long> seen = new HashSet<>();
        for (int j = i + 1; j < n; j++) {
            long need = -(long) sorted[i] - sorted[j];
            if (seen.contains(need)) {
                result.add(List.of(sorted[i], (int) need, sorted[j]));
                while (j + 1 < n && sorted[j] == sorted[j + 1]) j++;
            }
            seen.add((long) sorted[j]);
        }
    }
    return result;
}

def three_sum(nums: list[int]) -> list[list[int]]:
    s = sorted(nums)
    result: list[list[int]] = []
    for i in range(len(s) - 2):
        if i > 0 and s[i] == s[i - 1]: continue
        seen: set[int] = set()
        j = i + 1
        while j < len(s):
            need = -s[i] - s[j]
            if need in seen:
                result.append([s[i], need, s[j]])
                while j + 1 < len(s) and s[j] == s[j + 1]: j += 1
            seen.add(s[j])
            j += 1
    return result

function threeSum(nums: number[]): number[][] {
  const sorted = [...nums].sort((a, b) => a - b);
  const result: number[][] = [];
  for (let i = 0; i < sorted.length - 2; i++) {
    if (i > 0 && sorted[i] === sorted[i - 1]) continue;
    const seen = new Set<number>();
    for (let j = i + 1; j < sorted.length; j++) {
      const need = -sorted[i] - sorted[j];
      if (seen.has(need)) {
        result.push([sorted[i], need, sorted[j]]);
        while (j + 1 < sorted.length && sorted[j] === sorted[j + 1]) j++;
      }
      seen.add(sorted[j]);
    }
  }
  return result;
}

Flaws & bottlenecks

A new hash set is built for every i: repeated allocation and hashing.
Duplicate skipping after a hit (the inner while) is subtle and easy to get wrong.
Hash lookups scatter memory accesses, so the constant factor is worse than the two-pointer scan.

Interviewer cross-questions

Why is sorting still useful here?

Say: Not for the search itself, but for deduplication: equal values are adjacent, so skipping a repeated i, and advancing j past repeats after recording a triple, prevents duplicates without a set of triples.

Why does the set only contain values to the right of i?

Say: It is created fresh for each i and filled as j advances, so it holds exactly the elements between i + 1 and j − 1. That guarantees the three indices are distinct and ordered.

How does this compare with the two-pointer version?

Say: Same O(n²) time, but two pointers need no extra memory, no hashing, and scan memory sequentially. The hash version is useful when the array cannot be sorted or the data is streamed.

3 · advanced

Sort + two pointers

time O(n²)space O(1) beyond the sort and output

Sort. For each i, place left just after it and right at the end; move left up when the sum is negative and right down when it is positive, recording zero sums and skipping repeated values.

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<int> sorted(nums); sort(sorted.begin(), sorted.end());
    vector<vector<int>> result;
    int n = sorted.size();
    for (int i = 0; i < n - 2; i++) {
        if (sorted[i] > 0) break;
        if (i > 0 && sorted[i] == sorted[i - 1]) continue;
        int left = i + 1;
        int right = n - 1;
        while (left < right) {
            long long sum = (long long)sorted[i] + sorted[left] + sorted[right];
            if (sum < 0) left++;
            else if (sum > 0) right--;
            else {
                result.push_back({sorted[i], sorted[left], sorted[right]});
                while (left < right && sorted[left] == sorted[left + 1]) left++;
                while (left < right && sorted[right] == sorted[right - 1]) right--;
                left++;
                right--;
            }
        }
    }
    return result;
}

public List<List<Integer>> threeSum(int[] nums) {
    int[] sorted = nums.clone(); Arrays.sort(sorted);
    List<List<Integer>> result = new ArrayList<>();
    int n = sorted.length;
    for (int i = 0; i < n - 2; i++) {
        if (sorted[i] > 0) break;
        if (i > 0 && sorted[i] == sorted[i - 1]) continue;
        int left = i + 1;
        int right = n - 1;
        while (left < right) {
            long sum = (long) sorted[i] + sorted[left] + sorted[right];
            if (sum < 0) left++;
            else if (sum > 0) right--;
            else {
                result.add(List.of(sorted[i], sorted[left], sorted[right]));
                while (left < right && sorted[left] == sorted[left + 1]) left++;
                while (left < right && sorted[right] == sorted[right - 1]) right--;
                left++;
                right--;
            }
        }
    }
    return result;
}

def three_sum(nums: list[int]) -> list[list[int]]:
    s = sorted(nums)
    result: list[list[int]] = []
    for i in range(len(s) - 2):
        if s[i] > 0: break
        if i > 0 and s[i] == s[i - 1]: continue
        left = i + 1
        right = len(s) - 1
        while left < right:
            total = s[i] + s[left] + s[right]
            if total < 0: left += 1
            elif total > 0: right -= 1
            else:
                result.append([s[i], s[left], s[right]])
                while left < right and s[left] == s[left + 1]: left += 1
                while left < right and s[right] == s[right - 1]: right -= 1
                left += 1
                right -= 1
    return result

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

Flaws & bottlenecks

O(n log n) sort plus O(n²) scan; for very large n the quadratic term dominates.
Mutating or copying the input is required (sorting), and original indices are lost, so this version cannot return positions.
Easy to get wrong: forgetting to skip repeated left/right values after a hit produces duplicate triples.

Interviewer cross-questions

Why can the pointers only move in one direction each?

Say: Because the array is sorted: if the sum is too small, every pairing of the current left with a smaller right would be even smaller, so that left can never be part of a solution with this i, and left can be discarded safely (symmetrically for right).

How does it avoid duplicate triples?

Say: Three skips: skip a repeated i, and after recording a hit, advance left past equal values and retreat right past equal values. With sorted data, equal values are adjacent, so these skips remove every duplicate.

Can you do better than O(n²)?

Say: Not in general: 3Sum is conjectured to need roughly quadratic time (the "3SUM conjecture", with only logarithmic-factor improvements known). If values are bounded integers, FFT-based methods can help in special cases.

4 · expert

Two pointers with pruning

time O(n²) worst case, often far lessspace O(1) beyond the sorted copy and output

The same sorted two-pointer scan, but with early exits: stop when the smallest value is positive, skip any i whose best-case sum (with the two largest values) is still negative, and jump over duplicates with do-while loops. Sorting uses an integer typed array.

vector<vector<int>> threeSum(const vector<int>& nums) {
    int n = nums.size();
    if (n < 3) return {};
    vector<int> a(nums); sort(a.begin(), a.end());
    vector<vector<int>> result;
    for (int i = 0; i < n - 2; i++) {
        if (a[i] > 0) break;
        if ((long long)a[i] + a[n - 2] + a[n - 1] < 0) continue;
        if (i > 0 && a[i] == a[i - 1]) continue;
        int left = i + 1;
        int right = n - 1;
        while (left < right) {
            long long sum = (long long)a[i] + a[left] + a[right];
            if (sum < 0) left++;
            else if (sum > 0) right--;
            else {
                result.push_back({a[i], a[left], a[right]});
                do left++; while (left < right && a[left] == a[left - 1]);
                do right--; while (left < right && a[right] == a[right + 1]);
            }
        }
    }
    return result;
}

public List<List<Integer>> threeSum(int[] nums) {
    int n = nums.length;
    if (n < 3) return new ArrayList<>();
    int[] a = nums.clone(); Arrays.sort(a);
    List<List<Integer>> result = new ArrayList<>();
    for (int i = 0; i < n - 2; i++) {
        if (a[i] > 0) break;
        if ((long) a[i] + a[n - 2] + a[n - 1] < 0) continue;
        if (i > 0 && a[i] == a[i - 1]) continue;
        int left = i + 1;
        int right = n - 1;
        while (left < right) {
            long sum = (long) a[i] + a[left] + a[right];
            if (sum < 0) left++;
            else if (sum > 0) right--;
            else {
                result.add(List.of(a[i], a[left], a[right]));
                do left++; while (left < right && a[left] == a[left - 1]);
                do right--; while (left < right && a[right] == a[right + 1]);
            }
        }
    }
    return result;
}

def three_sum(nums: Sequence[int]) -> list[list[int]]:
    n = len(nums)
    if n < 3: return []
    a = sorted(nums)
    result: list[list[int]] = []
    for i in range(n - 2):
        if a[i] > 0: break
        if a[i] + a[n - 2] + a[n - 1] < 0: continue
        if i > 0 and a[i] == a[i - 1]: continue
        left = i + 1
        right = n - 1
        while left < right:
            total = a[i] + a[left] + a[right]
            if total < 0: left += 1
            elif total > 0: right -= 1
            else:
                result.append([a[i], a[left], a[right]])
                left += 1
                while left < right and a[left] == a[left - 1]: left += 1
                right -= 1
                while left < right and a[right] == a[right + 1]: right -= 1
    return result

function threeSum(nums: ArrayLike<number>): number[][] {
  const n = nums.length;
  if (n < 3) return [];
  const a = Int32Array.from(nums).sort();
  const result: number[][] = [];
  for (let i = 0; i < n - 2; i++) {
    if (a[i] > 0) break;
    if (a[i] + a[n - 2] + a[n - 1] < 0) continue;
    if (i > 0 && a[i] === a[i - 1]) continue;
    let left = i + 1;
    let right = n - 1;
    while (left < right) {
      const sum = a[i] + a[left] + a[right];
      if (sum < 0) left++;
      else if (sum > 0) right--;
      else {
        result.push([a[i], a[left], a[right]]);
        do left++; while (left < right && a[left] === a[left - 1]);
        do right--; while (left < right && a[right] === a[right + 1]);
      }
    }
  }
  return result;
}

Flaws & bottlenecks

Pruning improves typical inputs but not the worst case, which stays O(n²).
More branches to reason about and test; each early exit must be provably safe.
Int32Array assumes 32-bit values (silent wrap-around beyond that); sums must be computed in a wider type in fixed-width languages.

Interviewer cross-questions

Why is the "best-case" prune correct?

Say: With a[i] fixed, the largest sum any triple using i can reach is a[i] plus the two largest remaining values, a[n−2] and a[n−1]. If even that is below zero, no triple starting at i can sum to zero, so skipping i loses nothing. The symmetric check (smallest possible sum above zero) stops the loop early.

What changes for 32-bit integer languages?

Say: a[i] + a[left] + a[right] can overflow int (three values near 2³¹). Compute the sum in a 64-bit type (long / long long) before comparing to zero.

How would you test the pruning?

Say: Compare against the plain two-pointer version on randomized arrays, including all-positive, all-negative, all-zero, many duplicates, and extreme values, and assert identical result sets. Property tests like this catch unsafe early exits.

Synchronized code walkthrough

Showing: Three loops plus a dedupe set — shares the player above; click any step to jump.

vector<vector<int>> threeSum(vector<int>& nums) {
    set<string> seen;
    vector<vector<int>> result;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if ((long long)nums[i] + nums[j] + nums[k] == 0) {
                    vector<int> triple = {nums[i], nums[j], nums[k]}; sort(triple.begin(), triple.end());
                    string key = to_string(triple[0]) + "," + to_string(triple[1]) + "," + to_string(triple[2]);
                    if (!seen.count(key)) {
                        seen.insert(key);
                        result.push_back(triple);
                    }
                }
            }
        }
    }
    return result;
}

public List<List<Integer>> threeSum(int[] nums) {
    Set<String> seen = new HashSet<>();
    List<List<Integer>> result = new ArrayList<>();
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if ((long) nums[i] + nums[j] + nums[k] == 0) {
                    int[] t = {nums[i], nums[j], nums[k]}; Arrays.sort(t);
                    List<Integer> triple = List.of(t[0], t[1], t[2]);
                    String key = t[0] + "," + t[1] + "," + t[2];
                    if (!seen.contains(key)) {
                        seen.add(key);
                        result.add(triple);
                    }
                }
            }
        }
    }
    return result;
}

def three_sum(nums: list[int]) -> list[list[int]]:
    seen: set[str] = set()
    result: list[list[int]] = []
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if nums[i] + nums[j] + nums[k] == 0:
                    triple = sorted([nums[i], nums[j], nums[k]])
                    key = ','.join(map(str, triple))
                    if key not in seen:
                        seen.add(key)
                        result.append(triple)
    return result

function threeSum(nums: number[]): number[][] {
  const seen = new Set<string>();
  const result: number[][] = [];
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      for (let k = j + 1; k < nums.length; k++) {
        if (nums[i] + nums[j] + nums[k] === 0) {
          const triple = [nums[i], nums[j], nums[k]].sort((a, b) => a - b);
          const key = triple.join(',');
          if (!seen.has(key)) {
            seen.add(key);
            result.push(triple);
          }
        }
      }
    }
  }
  return result;
}

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<int> sorted(nums); sort(sorted.begin(), sorted.end());
    vector<vector<int>> result;
    int n = sorted.size();
    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && sorted[i] == sorted[i - 1]) continue;
        unordered_set<long long> seen;
        for (int j = i + 1; j < n; j++) {
            long long need = -(long long)sorted[i] - sorted[j];
            if (seen.count(need)) {
                result.push_back({sorted[i], (int)need, sorted[j]});
                while (j + 1 < n && sorted[j] == sorted[j + 1]) j++;
            }
            seen.insert(sorted[j]);
        }
    }
    return result;
}

public List<List<Integer>> threeSum(int[] nums) {
    int[] sorted = nums.clone(); Arrays.sort(sorted);
    List<List<Integer>> result = new ArrayList<>();
    int n = sorted.length;
    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && sorted[i] == sorted[i - 1]) continue;
        Set<Long> seen = new HashSet<>();
        for (int j = i + 1; j < n; j++) {
            long need = -(long) sorted[i] - sorted[j];
            if (seen.contains(need)) {
                result.add(List.of(sorted[i], (int) need, sorted[j]));
                while (j + 1 < n && sorted[j] == sorted[j + 1]) j++;
            }
            seen.add((long) sorted[j]);
        }
    }
    return result;
}

def three_sum(nums: list[int]) -> list[list[int]]:
    s = sorted(nums)
    result: list[list[int]] = []
    for i in range(len(s) - 2):
        if i > 0 and s[i] == s[i - 1]: continue
        seen: set[int] = set()
        j = i + 1
        while j < len(s):
            need = -s[i] - s[j]
            if need in seen:
                result.append([s[i], need, s[j]])
                while j + 1 < len(s) and s[j] == s[j + 1]: j += 1
            seen.add(s[j])
            j += 1
    return result

function threeSum(nums: number[]): number[][] {
  const sorted = [...nums].sort((a, b) => a - b);
  const result: number[][] = [];
  for (let i = 0; i < sorted.length - 2; i++) {
    if (i > 0 && sorted[i] === sorted[i - 1]) continue;
    const seen = new Set<number>();
    for (let j = i + 1; j < sorted.length; j++) {
      const need = -sorted[i] - sorted[j];
      if (seen.has(need)) {
        result.push([sorted[i], need, sorted[j]]);
        while (j + 1 < sorted.length && sorted[j] === sorted[j + 1]) j++;
      }
      seen.add(sorted[j]);
    }
  }
  return result;
}

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<int> sorted(nums); sort(sorted.begin(), sorted.end());
    vector<vector<int>> result;
    int n = sorted.size();
    for (int i = 0; i < n - 2; i++) {
        if (sorted[i] > 0) break;
        if (i > 0 && sorted[i] == sorted[i - 1]) continue;
        int left = i + 1;
        int right = n - 1;
        while (left < right) {
            long long sum = (long long)sorted[i] + sorted[left] + sorted[right];
            if (sum < 0) left++;
            else if (sum > 0) right--;
            else {
                result.push_back({sorted[i], sorted[left], sorted[right]});
                while (left < right && sorted[left] == sorted[left + 1]) left++;
                while (left < right && sorted[right] == sorted[right - 1]) right--;
                left++;
                right--;
            }
        }
    }
    return result;
}

public List<List<Integer>> threeSum(int[] nums) {
    int[] sorted = nums.clone(); Arrays.sort(sorted);
    List<List<Integer>> result = new ArrayList<>();
    int n = sorted.length;
    for (int i = 0; i < n - 2; i++) {
        if (sorted[i] > 0) break;
        if (i > 0 && sorted[i] == sorted[i - 1]) continue;
        int left = i + 1;
        int right = n - 1;
        while (left < right) {
            long sum = (long) sorted[i] + sorted[left] + sorted[right];
            if (sum < 0) left++;
            else if (sum > 0) right--;
            else {
                result.add(List.of(sorted[i], sorted[left], sorted[right]));
                while (left < right && sorted[left] == sorted[left + 1]) left++;
                while (left < right && sorted[right] == sorted[right - 1]) right--;
                left++;
                right--;
            }
        }
    }
    return result;
}

def three_sum(nums: list[int]) -> list[list[int]]:
    s = sorted(nums)
    result: list[list[int]] = []
    for i in range(len(s) - 2):
        if s[i] > 0: break
        if i > 0 and s[i] == s[i - 1]: continue
        left = i + 1
        right = len(s) - 1
        while left < right:
            total = s[i] + s[left] + s[right]
            if total < 0: left += 1
            elif total > 0: right -= 1
            else:
                result.append([s[i], s[left], s[right]])
                while left < right and s[left] == s[left + 1]: left += 1
                while left < right and s[right] == s[right - 1]: right -= 1
                left += 1
                right -= 1
    return result

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

vector<vector<int>> threeSum(const vector<int>& nums) {
    int n = nums.size();
    if (n < 3) return {};
    vector<int> a(nums); sort(a.begin(), a.end());
    vector<vector<int>> result;
    for (int i = 0; i < n - 2; i++) {
        if (a[i] > 0) break;
        if ((long long)a[i] + a[n - 2] + a[n - 1] < 0) continue;
        if (i > 0 && a[i] == a[i - 1]) continue;
        int left = i + 1;
        int right = n - 1;
        while (left < right) {
            long long sum = (long long)a[i] + a[left] + a[right];
            if (sum < 0) left++;
            else if (sum > 0) right--;
            else {
                result.push_back({a[i], a[left], a[right]});
                do left++; while (left < right && a[left] == a[left - 1]);
                do right--; while (left < right && a[right] == a[right + 1]);
            }
        }
    }
    return result;
}

public List<List<Integer>> threeSum(int[] nums) {
    int n = nums.length;
    if (n < 3) return new ArrayList<>();
    int[] a = nums.clone(); Arrays.sort(a);
    List<List<Integer>> result = new ArrayList<>();
    for (int i = 0; i < n - 2; i++) {
        if (a[i] > 0) break;
        if ((long) a[i] + a[n - 2] + a[n - 1] < 0) continue;
        if (i > 0 && a[i] == a[i - 1]) continue;
        int left = i + 1;
        int right = n - 1;
        while (left < right) {
            long sum = (long) a[i] + a[left] + a[right];
            if (sum < 0) left++;
            else if (sum > 0) right--;
            else {
                result.add(List.of(a[i], a[left], a[right]));
                do left++; while (left < right && a[left] == a[left - 1]);
                do right--; while (left < right && a[right] == a[right + 1]);
            }
        }
    }
    return result;
}

def three_sum(nums: Sequence[int]) -> list[list[int]]:
    n = len(nums)
    if n < 3: return []
    a = sorted(nums)
    result: list[list[int]] = []
    for i in range(n - 2):
        if a[i] > 0: break
        if a[i] + a[n - 2] + a[n - 1] < 0: continue
        if i > 0 and a[i] == a[i - 1]: continue
        left = i + 1
        right = n - 1
        while left < right:
            total = a[i] + a[left] + a[right]
            if total < 0: left += 1
            elif total > 0: right -= 1
            else:
                result.append([a[i], a[left], a[right]])
                left += 1
                while left < right and a[left] == a[left - 1]: left += 1
                right -= 1
                while left < right and a[right] == a[right + 1]: right -= 1
    return result

function threeSum(nums: ArrayLike<number>): number[][] {
  const n = nums.length;
  if (n < 3) return [];
  const a = Int32Array.from(nums).sort();
  const result: number[][] = [];
  for (let i = 0; i < n - 2; i++) {
    if (a[i] > 0) break;
    if (a[i] + a[n - 2] + a[n - 1] < 0) continue;
    if (i > 0 && a[i] === a[i - 1]) continue;
    let left = i + 1;
    let right = n - 1;
    while (left < right) {
      const sum = a[i] + a[left] + a[right];
      if (sum < 0) left++;
      else if (sum > 0) right--;
      else {
        result.push([a[i], a[left], a[right]]);
        do left++; while (left < right && a[left] === a[left - 1]);
        do right--; while (left < right && a[right] === a[right + 1]);
      }
    }
  }
  return result;
}