3Sum (opens in a new tab) Medium

Problem

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example

Example 1

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: []

Summary

To solve this problem, we can sort the input array, iterate over each element, and use two pointers to find pairs of elements that sum up to the negation of the current element. We can skip duplicate elements and pairs to avoid duplicates in the output. We can return the unique triplets that satisfy the sum condition.

Solution

In TypeScript

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

In Python

from typing import List
 
def threeSum(nums: List[int]) -> List[List[int]]:
	nums.sort()
 
	results = []
 
	for i in range(len(nums)):
		if i > 0 and nums[i] == nums[i - 1]:
			continue
 
		j = i + 1
		k = len(nums) - 1
 
		while j < k:
			sum = nums[i] + nums[j] + nums[k]
 
			if sum == 0:
				results.append([nums[i], nums[j], nums[k]])
				j += 1
				k -= 1
 
				while j < k and nums[j] == nums[j - 1]:
						j += 1
				while j < k and nums[k] == nums[k + 1]:
						k -= 1
			elif sum < 0:
				j += 1
			else:
				k -= 1
 
	return results

Step-by-step explanation

1. Initialize an empty array result to store the triplets that add up to zero.

2. Sort the input array nums in non-decreasing order, which allows us to use two pointers to find all pairs of numbers that add up to the negative of the current number.

nums.sort((a, b) => a - b);

3. Iterate through the input array nums using a single loop, and for each number nums[i], use two pointers j and k to find all pairs of numbers that add up to -nums[i]. We can start j at i + 1 and k at n - 1, where n is the length of nums.

for (let i = 0; i < nums.length; i++) {
	let j = i + 1;
	let k = nums.length - 1;
}

4. To avoid duplicate triplets, we can skip over any numbers that are the same as the previous one. We can check if nums[i] is equal to the previous number (nums[i - 1]) by adding a condition to the loop.

if (i > 0 && nums[i] === nums[i - 1]) {
    continue;
}

5. Using the two pointers j and k, we can find all pairs of numbers that add up to -nums[i]. If the sum of the triplet is zero, we add it to the result array and move both pointers towards each other to find the next pair of numbers. If the sum is less than zero, we move the left pointer j towards the right. If the sum is greater than zero, we move the right pointer k towards the left.

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

6. Return the result array containing all unique triplets that add up to zero.

return result;

Complexity Analysis

Time Complexity

The time complexity of this solution is O(n^2), where n is the length of the input array. The sorting step takes O(n log n) time, and the nested loop takes O(n^2) time in the worst case. However, by using two pointers and skipping duplicates, the actual running time of the algorithm is significantly less than the worst case.

Space Complexity

The space complexity of this solution is O(log n) to O(n) due to the sorting implementation.