15. 3Sum

Link: https://leetcode.com/problems/3sum

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

Solution:

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  let res = [] // Initialize an empty array to store the unique triplets.

  // Return an empty array if the input array has fewer than three elements.
  if (nums.length < 3) return res

  // Sort the array in ascending order to facilitate finding triplets.
  nums = nums.sort((a, b) => a - b)

  // The target sum for the triplets.
  const target = 0

  // Iterate through the array, considering each number as the potential first number of a triplet.
  for (let i = 0; i < nums.length - 2; i++) {
    // Skip this number if it's the same as the one before it to avoid duplicate triplets.
    if (i > 0 && nums[i] === nums[i - 1]) continue

    // Initialize two pointers for the current iteration.
    let j = i + 1 // The second number of the triplet.
    let k = nums.length - 1 // The third number of the triplet.

    // Use a while loop to try different combinations of numbers at j and k.
    while (j < k) {
      let sum = nums[i] + nums[j] + nums[k] // Calculate the sum of the current triplet.

      // If the sum is zero, we've found a valid triplet.
      if (sum === target) {
        res.push([nums[i], nums[j], nums[k]]) // Add it to the results array.

        // Move the j pointer forward to skip any duplicate values.
        while (nums[j] === nums[j + 1]) j++
        // Move the k pointer backward to skip any duplicate values.
        while (nums[k] === nums[k - 1]) k--

        // Prepare for the next potential triplet.
        j++
        k--
      } else if (sum < target) {
        // If the sum is less than zero, increment j to try a larger number.
        j++
      } else {
        // If the sum is more than zero, decrement k to try a smaller number.
        k--
      }
    }
  }

  // Return the array of unique triplets that sum to zero.
  return res
}

1. Initialization: The function begins by checking if the input array nums has fewer than three elements. If so, it returns an empty array immediately since at least three numbers are needed to form a triplet.

2. Sorting: The input array is sorted in ascending order. This sorting is crucial because it allows efficient identification of potential triplets and helps avoid duplicates.

3. Iterating through the Array: The main part of the function iterates through the array, using a variable i to track the current position. For each position of i, it attempts to find two other numbers that, when added to nums[i], equal zero.

4. Skip Over Larger Numbers: If the current number nums[i] is greater than the target (0 in this case), the loop breaks early since all subsequent numbers will also be greater than 0 (because the array is sorted), making it impossible to find a triplet that adds up to 0.

5. Two-pointer Technique: For each value of i, the function uses two pointers, j and k, to find complementary numbers that sum up to zero with nums[i]. The pointers start from i+1 and the end of the array, respectively, moving towards each other until they meet. This technique efficiently explores possible combinations of triplets.

6. Finding a Triplet: When a triplet summing to zero is found, it's added to the result array res. The function then adjusts both j and k to skip over any duplicate values for both pointers. This is crucial for ensuring that the result contains only unique triplets.

7. Adjusting j and k: If the current sum is less than zero, j is incremented to try a larger number (since the array is sorted). Conversely, if the sum is more than zero, k is decremented to try a smaller number.

8. Returning the Result: Finally, after exploring all possible combinations.