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 sums up to 0.

this problem was taken from Leetcode

 

Explanation:

1. Sorting the Array: The array is first sorted to easily manage duplicates and use a two-pointer approach.
2. Iterating with a Loop: A loop iterates through the array, fixing one element (nums[i]) and then using a two-pointer approach to find the other two elements (nums[left] and nums[right]).
3. Avoiding Duplicates: Duplicate values are skipped using continue for the first element and while loops for the second and third elements to ensure the solution set contains only unique triplets.
4. Two-Pointer Approach: The sum is checked, and pointers are adjusted accordingly to find valid triplets.

Example Usage:

This would output:

This solution efficiently finds all unique triplets that sum to zero in O(n^2) time complexity.

 

Skipping duplicates in the threeSum algorithm is crucial to ensure that the solution set contains only unique triplets. Here’s a detailed explanation of how duplicates are skipped at different stages:

1. Skipping Duplicates for the First Element (i):

When iterating through the array with the outer loop (for (let i = 0; i < nums.length - 2; i++)), the algorithm checks if the current element nums[i] is the same as the previous element nums[i - 1]. If they are the same, it means that any triplet starting with this element would already have been considered in a previous iteration, so the algorithm skips this iteration.

Code Example:

Explanation:

• i > 0: Ensures that we don’t check for a previous element when i is 0.
• nums[i] === nums[i - 1]: If this condition is true, it means nums[i] is a duplicate of the previous element, so the loop skips to the next i using continue.

2. Skipping Duplicates for the Second and Third Elements (left and right):

After fixing the first element nums[i], the algorithm uses two pointers, left and right, to find the other two elements (nums[left] and nums[right]) that, together with nums[i], sum to zero.

Once a valid triplet is found, the algorithm moves both pointers inward but also checks for duplicates by comparing the current elements with the next ones in line. If the next element is the same as the current one, the algorithm skips the next element by advancing the pointer further.

Code Example:

Explanation:

• Left Pointer:
  • while (left < right && nums[left] === nums[left + 1]) left++;
  • This loop skips all duplicate values for nums[left] by incrementing left until it points to a new value.
• Right Pointer:
  • while (left < right && nums[right] === nums[right - 1]) right--;
  • Similarly, this loop skips all duplicate values for nums[right] by decrementing right until it points to a new value.

Why This is Important:

• Avoiding Redundant Triplets: Without skipping duplicates, the algorithm would include multiple instances of the same triplet in the result, which is inefficient and incorrect for this problem.
• Efficiency: Skipping duplicates prevents unnecessary comparisons, speeding up the algorithm.

Example Walkthrough:

Consider the array [-1, 0, 1, 2, -1, -4]:

1. Sorting: The array becomes [-4, -1, -1, 0, 1, 2].
2. Iteration with i = 0 (nums[i] = -4):
   • No duplicates for nums[i], proceed with left = 1 and right = 5.
   • No valid triplet is found, move to the next i.
3. Iteration with i = 1 (nums[i] = -1):
   • Triplet [-1, -1, 2] is found.
   • Skip duplicates: left moves from index 2 to 3 because nums[2] === nums[3].
   • Triplet [-1, 0, 1] is found.
4. Iteration with i = 2 (nums[i] = -1):
   • Skip this iteration entirely because nums[2] === nums[1].

As a result, only unique triplets are returned: [[-1, -1, 2], [-1, 0, 1]].

 

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    nums.sort((a, b) =>{ return a - b });
    const result = [];

    for(let i = 0; i < nums.length - 2; i ++) {
        // Skip duplicate values for the first element of the triplet
        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]]);
                 // Skip duplicate values for the second and third elements of the triplet
                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;
};