# Three Sum - LeetCode Problem

## Problem Description

The problem [3Sum](https://leetcode.com/problems/3sum/) is 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:

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

## Solution

To solve the problem, we follow the steps below:

1. We sort the array using `nums.sort()`.
    
2. We iterate over each element in the array using a `for` loop.
    
3. Inside the loop, we check if the current element is a positive integer or not. If it is, we break out of the loop.
    
4. If the current element is not a positive integer, we check if it is a duplicate of the previous element. If it is, we skip it using the `continue` statement. If it is not, we initialize two variables `l` and `r`. `l` will point to the next element after the current element, and `r` will point to the last element in the array.
    
5. We then use a `while` loop which will continue until `l` is less than `r`. Inside the `while` loop, we calculate the sum of the current element, `lth` element, and `rth` element. If the sum is greater than 0, we decrement `r` using `r -= 1`. If it is less than 0, we increment `l` using `l += 1`. If it is equal to 0, we append the triplet to the result and increment `l` and decrement `r` using `l += 1` and `r -= 1`. We then check if the next element after `l` is a duplicate of the current element. If it is, we skip it using the `while` loop.
    
6. Finally, we return the result using `return res`.
    

```python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()

        for i, a in enumerate(nums):
            # Skip positive integers
            if a > 0:
                break

            if i > 0 and a == nums[i - 1]:
                continue

            l, r = i + 1, len(nums) - 1
            while l < r:
                threeSum = a + nums[l] + nums[r]
                if threeSum > 0:
                    r -= 1
                elif threeSum < 0:
                    l += 1
                else:
                    res.append([a, nums[l], nums[r]])
                    l += 1
                    r -= 1
                    while nums[l] == nums[l - 1] and l < r:
                        l += 1
        return res
```

## Complexity Analysis

The time complexity of this algorithm is `O(n^2)`. This is because we are using nested loops to iterate over the array. The space complexity of this algorithm is `O(1)`, since we are not using any extra space.

## Conclusion

In this blog post, we have solved the LeetCode problem "3Sum" using Python. We have explained the solution step-by-step and provided a complexity analysis. Happy Coding!😎