## Table of contents

## Open Table of contents

## Problem

Given an integer array `nums`

, the task is to return all the triplets `[nums[i], nums[j], nums[k]]`

such that `i != j`

, `i != k`

, `j != k`

, and `nums[i] + nums[j] + nums[k] == 0`

. It is important to note 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:
The distinct triplets are [-1,0,1] and [-1,-1,2].
```

**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.
```

**Constraints:**

`3 <= nums.length <= 3000`

`-105 <= nums[i] <= 105`

## Explanation/Approach

The problem is to find all unique triplets in the array that add up to zero. This problem can be efficiently solved using a combination of sorting and two-pointer technique.

**Sorting:**First, we sort the array. This helps in skipping duplicates and also makes it easier to move pointers for checking sums.**Iterating with a Fixed Element:**We iterate through the array, fixing one element at a time and then using two pointers to find the other two elements.**Two Pointers:**For each fixed element, we use a left pointer starting right after the fixed element and a right pointer at the end of the array. We move these pointers based on the sum of the triplet.**Skipping Duplicates:**To avoid duplicate triplets, we skip over duplicate values both for the fixed element and while moving the two pointers.

## Solution: Two Pointers with Sorting

```
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# Resultant list for storing triplets
res = []
# Sort the array to simplify finding triplets and avoiding duplicates
nums = sorted(nums)
# Iterate over the array
for i, num1 in enumerate(nums):
# If the current number is greater than 0, further triplets are impossible
if num1 > 0:
break
# Skip duplicate elements
if i > 0 and num1 == nums[i-1]:
continue
# Initialize two pointers
l, r = i + 1, len(nums) - 1
# Iterate with the two pointers
while r > l:
three_sum = num1 + nums[l] + nums[r]
# Move pointers based on the sum
if three_sum > 0:
r -= 1
elif three_sum < 0:
l += 1
else:
# Add the triplet to the result
res.append([num1, nums[l], nums[r]])
l += 1
# Skip duplicates for the left pointer
while nums[l] == nums[l-1] and l < r:
l += 1
return res
```

**Time and Memory Complexity**

The time complexity is O(n^2), primarily due to the two-pointer traversal for each element. The sorting operation contributes O(n log n), which is overshadowed by the quadratic complexity. The space complexity is O(1) or O(n) depending on the implementation of the sorting algorithm.

**Explanation**

This solution begins by sorting the array. For each element (skipping duplicates), it looks for a pair in the rest of the array that adds up to the negative of the element. The two pointers (`l`

and `r`

) help in finding these pairs. When a triplet is found, it is added to the result, and the left pointer is moved while skipping over duplicates.

**Visualization**

You’re correct. Let’s adjust the visualization for Iteration 2 to reflect this step:

**Visualization**

With the sorted array `[-4, -1, -1, 0, 1, 2]`

from `nums = [-1,0,1,2,-1,-4]`

, the algorithm’s process is as follows:

```
Iteration 1 (fix -4):
Array: [-4, -1, -1, 0, 1, 2]
↑ ↑ ↑
l = 1, r = 5. The sum is always less than 0, with the smallest sum being -3 (-4 + -1 + 2), so no valid triplet is found.
Iteration 2 (fix first -1):
Array: [-4, -1, -1, 0, 1, 2]
↑ ↑ ↑
l = 2, r = 5. Initially, the sum is 0 (-1 + -1 + 2), finding a valid triplet [-1, -1, 2].
After finding this triplet, we move the left pointer once to avoid duplicates:
l = 3, r = 5. Now, the sum is 0 (-1 + 0 + 1), finding another valid triplet [-1, 0, 1].
Iteration 3 (skip second -1, duplicate):
Skipping the second -1 to avoid repeating the same triplet.
Iteration 4 (fix 0):
Array: [-4, -1, -1, 0, 1, 2]
↑ ↑ ↑
l = 4, r = 5. The sum is 3 (0 + 1 + 2), which is too large. Adjusting pointers does not find a valid triplet here.
Response:
[[-1, -1, 2], [-1, 0, 1]]
```

In each iteration, the algorithm fixes one element (like -4, -1, 0) and uses two pointers (l and r) to find a pair in the rest of the array that adds up to the negative of the fixed element. After finding a valid triplet, the left pointer is moved to avoid duplicates and to find other possible combinations. Skipping duplicates is crucial to avoid repeating the same triplet and to enhance efficiency.