[LeetCode] 15. 3Sum

Table of Contents

Description

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 1:

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

• nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
• nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
• nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.

The distinct triplets are [-1,0,1] and [-1,-1,2]. Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sum up to 0.

Approach

Refer to the solution for [Leetcode] 1. Two Sum and reinterpret the equation

$$nums[i] + nums[j] + nums[k] = 0 \quad \Longrightarrow \quad nums[i] + nums[j] = -nums[k]$$

This transforms the problem into finding two numbers whose sum equals a target value.We can use a similar approach to find the two numbers that sum to -nums[k].

We’ll iterate through the sorted array, considering each element as a candidate for the second element (numJ). For each numJ, we loop through the subsequent elements as potential third elements (numK), calculate the required first element ($numI = -numJ - numK$), and then check if that numI was encountered earlier. If so, the triplet is valid.

Solution

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  // Minimum number of elements required to form a triplet
  const MIN_COUNT = 3;

  // Early return scenarios:
  // 1. If there are fewer than 3 numbers.
  // 2. If all numbers are positive (then no three numbers can sum to zero).
  if (nums.length < MIN_COUNT || nums.every(num => num > 0)) return [];
  if (nums.every(num => num === 0)) return [[0, 0, 0]];

  // Sorting facilitates the process of avoiding duplicate triplets.
  const sortedNums = nums.sort((a, b) => a - b);
  // Map to track numbers that have been seen so far.
  const potentialNumIMap = {};
  // Object to store unique triplets.
  const tripletMap = {};

  // Iterate over each element considering it as the second element (numJ) in the triplet.
  for (let j = 0; j < sortedNums.length; j++) {
    const numJ = sortedNums[j];

    // For each numJ, iterate over the subsequent elements to consider as the third element (numK) in the triplet.
    for (let k = j + 1; k < sortedNums.length; k++) {
      const numK = sortedNums[k],
        // Calculate the required first element (numI) so that the sum of the triplet equals zero.
        numI = -numJ - numK;
      const triplet = [numI, numJ, numK];

      // If the required numI was already seen, this forms a valid triplet.
      if (potentialNumIMap[numI]) {
        // Using the triplet as a key string helps avoid adding duplicates.
        tripletMap[triplet] = triplet;
      }
    }
    // Mark numJ as seen, making it available as a potential numI for future pairs.
    potentialNumIMap[numJ] = true;
  }

  return Object.values(tripletMap);
};

Complexity Analysis

Time Complexity

The time complexity is $O(n^2)$, where $n$ is the number of elements in the input array. The outer loop runs $n$ times, and the inner loop runs $n-1$ times. The inner loop runs $n-1$ times because the outer loop iterates through the array, and the inner loop iterates through the remaining elements.

Space Complexity

The overall space complexity is $O(n)$. We use a map to record each number encountered, which in the worst case may store up to n elements. Additionally, we store unique triplets in an object. Even though each triplet contains three numbers, at most n/3 triplets will be recorded, still contributing $O(n)$ space. Combined, total space complexity of $O(n)$.