Neutral Charge Trios

Mediumtwo pointersAlso known as 3Sum

A school chemistry lab has a shelf of vials. Each label shows the vial's electric charge as a whole number, like -3, 0 or 2. For an experiment the class needs mixtures made from exactly three vials whose charges add up to 0.

The teacher wants a list of every possible charge combination, so students can pick one. Two vials with the same label are interchangeable, so [-1, 0, 1] should be listed once, however many ways the shelf can make it.

Your task

Write neutralTrios(charges). Return every distinct trio of values [a, b, c] such that a + b + c = 0 and the three values come from three different vials (three different positions in charges).

Write each trio in ascending order (a ≤ b ≤ c). The trios themselves can be returned in any order. No trio may appear twice. If there are none, return an empty list.

neutralTrios(charges: int[]) → int[][] Any order of the returned list is accepted.

Examples

Example 1

Input

charges = [2, -3, 0, 1, -1, -2]

Output

[[-3, 1, 2], [-2, 0, 2], [-1, 0, 1]]

Why

Three trios add up to 0: -3 + 1 + 2, -2 + 0 + 2 and -1 + 0 + 1. Each is written smallest first. There are no others: for example -3 would need two vials summing to 3, and only 1 + 2 works.

Example 2

Input

charges = [0, 0, 0, 0]

Output

[[0, 0, 0]]

Why

Any three of the four zero vials work, which is 4 different choices of vials, but they all give the same charges. List [0, 0, 0] once.

Constraints

0 ≤ charges.length ≤ 3,000
-100,000 ≤ charges[i] ≤ 100,000

Start with brute force

Try every combination of three positions with three nested loops, keep the ones that add up to 0, sort each trio and put it in a set to remove repeats.

With 3,000 vials there are about 4.5 billion combinations of three. That is far too many. The waste is in the innermost loop: once two values are chosen, the third is fixed, so searching for it one by one is pointless.

Hints

0 of 4 shown

Hint 1
Suppose you decide the trio must include the vial with charge -3. What must the other two add up to? Have you solved that smaller question before?
Hint 2
Fixing one value turns the problem into: find two values that add up to a target. On a sorted list, two pointers from the ends solve that in one pass.
Hint 3
Sort the charges. For each position i, look for pairs to the right of i that add up to -charges[i]. Only looking to the right means each trio is found from its smallest value, once.
Hint 4
Inside the pair search: if the sum is too small move left right, if too big move right left, if exact record it and move both. To avoid duplicates, skip an i whose value equals the previous one, and after a match keep moving left while it repeats the value you just used.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Sort first. Then pick the smallest member of the trio, a[i], and the question becomes "which two values to its right add up to -a[i]?" On a sorted list that is a two-pointer search from both ends.

Trace [2, -3, 0, 1, -1, -2], sorted to [-3, -2, -1, 0, 1, 2]:

i = 0 (-3). Need a pair summing to 3. left on -2, right on 2: total -3. Too small, move left. -1 and 2: -2. Move left. 0 and 2: -1. Move left. 1 and 2: 0. Record [-3, 1, 2]. The pointers cross.
i = 1 (-2). left on -1, right on 2: total -1. Move left. 0 and 2: 0. Record [-2, 0, 2]. Now left = right, stop.
i = 2 (-1). 0 and 2: total 1. Too big, move right. 0 and 1: 0. Record [-1, 0, 1].
i = 3 (0). Only 1 and 2 remain: total 3. Too big, move right. The pointers meet. No trio can start later than this, because fewer than three values would be left, so the loop ends.

Duplicates are handled by the sorted order: skip an i with the same value as the one before, and after a match slide left past copies of the value just used. Both rules stop the same trio from being recorded twice.

Reference solution

function neutralTrios(charges) {
  const a = [...charges].sort((x, y) => x - y);
  const result = [];
  for (let i = 0; i < a.length - 2; i++) {
    if (a[i] > 0) break; // three positives cannot sum to 0
    if (i > 0 && a[i] === a[i - 1]) continue; // same smallest value as before
    let left = i + 1, right = a.length - 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]]);
        left++;
        right--;
        while (left < right && a[left] === a[left - 1]) left++; // skip repeats
      }
    }
  }
  return result;
}

def neutral_trios(charges):
    a = sorted(charges)
    result = []
    for i in range(len(a) - 2):
        if a[i] > 0:
            break  # three positives cannot sum to 0
        if i > 0 and a[i] == a[i - 1]:
            continue  # same smallest value as before
        left, right = i + 1, len(a) - 1
        while left < right:
            s = a[i] + a[left] + a[right]
            if s < 0:
                left += 1
            elif s > 0:
                right -= 1
            else:
                result.append([a[i], a[left], a[right]])
                left += 1
                right -= 1
                while left < right and a[left] == a[left - 1]:
                    left += 1  # skip repeats
    return result

TimeO(n²)Sorting is O(n log n). Then for each of n smallest values, one O(n) two-pointer pass.

SpaceO(n)The sorted copy (sorting in place would avoid it). The output is not counted.

Learn the idea: Two Pointers Simple Sorts

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code