## Similar Problems

Similar Problems not available

# 3sum - Leetcode Solution

## Companies:

LeetCode: 3sum Leetcode Solution

Difficulty: Medium

Topics: sorting array two-pointers

The 3Sum problem on LeetCode is to find all unique triplets in the array which gives the sum of zero. In other words, the problem requires you to find three numbers from the array that sum up to zero.

The problem is quite popular and is considered a classic problem in computer science. The brute force approach to solve this problem would require three nested loops to check all possible triplets, which would take O(n^3) time complexity. Therefore, a more efficient solution should be used.

One way to solve this problem efficiently is by sorting the array first. Sorting the array would bring all the negative numbers to the left side of the array and all the positive numbers to the right side. The zero would end up in the middle.

Then, we can use a two-pointer approach to find the triplets. We start with fixing the first number and then look for the remaining two numbers whose sum adds up to the complement of the first number.

The two-pointer approach involves two pointers, one at the beginning and one at the end of the sorted array. We start by fixing the first number and then increment the left pointer if the sum of the first number and the left pointer element is less than the complement, or decrement the right pointer if the sum of the first number and the right pointer element is greater than the complement. If the sum is equal to the complement, we have found a triplet.

The code for the solution looks like this:

```
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
int n = nums.size();
sort(nums.begin(), nums.end());
for (int i = 0; i < n - 2; i++) {
if (i == 0 || nums[i] != nums[i-1]) {
int l = i + 1, r = n - 1;
while (l < r) {
int sum = nums[i] + nums[l] + nums[r];
if (sum == 0) {
result.push_back({nums[i], nums[l], nums[r]});
while (l < r && nums[l] == nums[l+1]) l++;
while (l < r && nums[r] == nums[r-1]) r--;
l++;
r--;
} else if (sum < 0) {
l++;
} else {
r--;
}
}
}
}
return result;
}
};
```

The above code has a time complexity of O(n^2) and space complexity of O(1) as we are not using any extra space.

The vector `result`

stores all unique triplets that sum up to zero. We sort the input array `nums`

to bring all negative numbers to the left side and positive numbers to the right side. Then, we iterate through the array using a for loop, fixing the first number and then using the two-pointer approach to find the other two numbers.

The `if`

statement inside the for loop is used to skip any duplicate values. The `while`

loop inside the two-pointer approach is used to skip any duplicate values. Finally, the `return`

statement returns the vector `result`

containing all unique triplets that sum up to zero.

## 3sum Solution Code

`1`