3Sum

MediumArray Two Pointers Sorting

An auditor scans a ledger of signed amounts, nums, looking for groups of three entries that cancel out exactly. Find every distinct triplet of values [a, b, c] with a + b + c == 0, where the three values sit at three different positions of the array.

Triplets are compared by their values: two triplets made of the same three values, in any order, are the same triplet and must appear only once. Return the triplets in any order, with the values inside each triplet in any order. If nothing cancels out, return an empty list.

Example 1

Input: nums = [3,-2,1,0,-1,2]
Output: [[-2,-1,3],[-2,0,2],[-1,0,1]]

Explanation: Three groups cancel out: -2 + -1 + 3, -2 + 0 + 2 and -1 + 0 + 1.

Example 2

Input: nums = [5,1,-2,7]
Output: []

Explanation: The four possible triplets sum to 4, 13, 10 and 6, never 0.

Example 3

Input: nums = [-2,1,1,1,-2]
Output: [[-2,1,1]]

Explanation: Many index choices produce -2, 1, 1, but the triplet is listed once.

Constraints

nums has between 3 and 3000 entries.
Each entry is an integer from -10^5 to 10^5.

💡 Hint 1

Checking every triple is O(n³). If you fix the first value a, what problem is left for the other two?

💡 Hint 2

After sorting, "find two values summing to -a" can be solved with two pointers moving towards each other.

💡 Hint 3

To avoid duplicate triplets, skip over equal neighbours: for the fixed value and for each pointer after a match.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Sort the array, then fix the smallest value nums[i] of the triplet. The other two must sum to -nums[i] and lie to the right of i, so run two pointers lo = i + 1 and hi = n - 1: if the sum is too small move lo right, if too large move hi left, and on a match record it and move both. Duplicates are avoided by skipping a fixed value equal to the previous one, and by stepping lo past equal values after a match. Once nums[i] > 0 no triplet can sum to zero, so you can stop.

Time O(n²)Space O(1) extra besides sorting and the output

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

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length - 2 && nums[i] <= 0; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int lo = i + 1, hi = nums.length - 1;
            while (lo < hi) {
                int sum = nums[i] + nums[lo] + nums[hi];
                if (sum < 0) lo++;
                else if (sum > 0) hi--;
                else {
                    result.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                    lo++;
                    hi--;
                    while (lo < hi && nums[lo] == nums[lo - 1]) lo++;
                }
            }
        }
        return result;
    }
}

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
function threeSum(nums) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit