# Solution For 3sum

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> threeSum(vector& nums) {
vector> 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.

## Step by Step Implementation For 3sum

```public List 	> threeSum(int[] nums) {
List 	> res = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i + 2 < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {              // skip same result
continue;
}
int j = i + 1, k = nums.length - 1;
int target = -nums[i];
while (j < k) {
if (nums[j] + nums[k] == target) {
res.add(Arrays.asList(nums[i], nums[j], nums[k]));
j++;
k--;
while (j < k && nums[j] == nums[j - 1]) j++;  // skip same result
while (j < k && nums[k] == nums[k + 1]) k--;  // skip same result
} else if (nums[j] + nums[k] > target) {
k--;
} else {
j++;
}
}
}
return res;
}```
```Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

# Note:

# The solution set must not contain duplicate triplets.

# Example:

# Given array nums = [-1, 0, 1, 2, -1, -4],

# A solution set is:
# [
#   [-1, 0, 1],
#   [-1, -1, 2]
# ]
def threeSum(nums):
res = []
nums.sort()
for i in range(len(nums)-2):
if i > 0 and nums[i] == nums[i-1]:
continue
l, r = i+1, len(nums)-1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s < 0:
l +=1
elif s > 0:
r -= 1
else:
res.append((nums[i], nums[l], nums[r]))
while l < r and nums[l] == nums[l+1]:
l += 1
while l < r and nums[r] == nums[r-1]:
r -= 1
l += 1; r -= 1
return res```
```Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {

};```
```vector> threeSum(vector& nums) {
// sort the array first
sort(nums.begin(), nums.end());
int n = nums.size();
// result vector
vector> res;
// iterate over the array
for (int i = 0; i < n; i++) {
// if the current element is greater than 0, we can break as the rest of the array will also be greater than 0
if (nums[i] > 0) {
break;
}
// if the current element is the same as the previous element, we can skip it
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// two pointer approach, one at the beginning of the array and one at the end
int j = i + 1;
int k = n - 1;
// target sum is 0 - current element
int target = 0 - nums[i];
// while the two pointers do not cross each other
while (j < k) {
// if the current sum is equal to the target sum
if (nums[j] + nums[k] == target) {
// add the triplet to the result vector
res.push_back({nums[i], nums[j], nums[k]});
// move the left pointer to the next element
j++;
// move the right pointer to the previous element
k--;
// if the left pointer is at an element that is the same as the previous element, skip it
while (j < k && nums[j] == nums[j - 1]) {
j++;
}
// if the right pointer is at an element that is the same as the previous element, skip it
while (j < k && nums[k] == nums[k + 1]) {
k--;
}
}
// if the current sum is less than the target sum, move the left pointer to the next element
else if (nums[j] + nums[k] < target) {
j++;
}
// if the current sum is greater than the target sum, move the right pointer to the previous element
else {
k--;
}
}
}
// return the result vector
return res;
}```
```public class Solution {
public IList> ThreeSum(int[] nums) {
// sort the array
Array.Sort(nums);
List> res = new List>();

for (int i = 0; i < nums.Length - 2; i++)
{
// if the current element is greater than 0, then there's no point
// in considering it as the leftmost element since it can never sum to 0
if (nums[i] > 0) break;

// if the current element is the same as the previous element, then we've
// already considered it as the leftmost element and can safely skip it
if (i > 0 && nums[i] == nums[i - 1]) continue;

int left = i + 1, right = nums.Length - 1, target = -nums[i];
while (left < right)
{
if (nums[left] + nums[right] == target)
{
res.Add(new List { nums[i], nums[left], nums[right] });
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
}
else if (nums[left] + nums[right] < target)
{
left++;
}
else
{
right--;
}
}
}

return res;
}
}```
Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]