3Sum Medium 0 attempts
LeetCode ↗

3Sum

Medium ArrayTwo PointersSorting LeetCode

You're given an integer array nums. Find every triplet of values [nums[i], nums[j], nums[k]] drawn from three distinct indices i, j, and k where the three values sum to zero, and return all such triplets.

The same triplet of values should never show up twice in the result, even if it can be built from more than one combination of indices.

Input Format
Implement threeSum(nums). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. The order of the outer result array does not matter. Order inside each group does not matter either.

Sample Input and Output

Example 1 · Run Sample

Input
nums = [-1,0,1,2,-1,-4]
Output
[[-1,-1,2],[-1,0,1]]

Example 2

Input
nums = []
Output
[]

Example 3

Input
nums = [0]
Output
[]
Constraints
  • 3 <= nums.length <= 3000
  • -10^5 <= nums[i] <= 10^5
Test Cases (3)
Case 1
Args: [[-1,0,1,2,-1,-4]] Expected: [[-1,-1,2],[-1,0,1]]
Case 2
Args: [[]] Expected: []
Case 3
Args: [[0]] Expected: []
Topics
ArrayTwo PointersSorting

Approach: Sort + Two Pointers

Sort the array first. Then iterate through each element as the first number of the triplet. For each fixed first number, use two pointers (left and right) to find pairs that sum to the negative of the first number.

Skip duplicate values at each step to avoid duplicate triplets.

javascript
function threeSum(nums) {
  nums.sort((a, b) => a - b);
  const result = [];

  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;

    let left = i + 1;
    let right = nums.length - 1;

    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      if (sum === 0) {
        result.push([nums[i], nums[left], nums[right]]);
        while (left < right && nums[left] === nums[left + 1]) left++;
        while (left < right && nums[right] === nums[right - 1]) right--;
        left++;
        right--;
      } else if (sum < 0) {
        left++;
      } else {
        right--;
      }
    }
  }

  return result;
}

Time Complexity: O(n^2) — sorting is O(n log n), the nested loop is O(n^2).

Space Complexity: O(1) extra space (ignoring the output array).

Saved in this browser only. Private to you.

JavaScript