# 3Sum

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

## Solution

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

`[-1, 0, 1, 2, -1, -4]`

This would output:

```[[-1, -1, 2], [-1, 0, 1]] ```

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:

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

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:

```// After finding a triplet while (left < right && nums[left] === nums[left + 1]) left++; while (left < right && nums[right] === nums[right - 1]) right--; ```

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;
};```