# Leetcode – 15 – 3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a  b  c)
• The solution set must not contain duplicate triplets.
```    For example, given array S = {-1 0 1 2 -1 -4},

A solution set is:
(-1, 0, 1)
(-1, -1, 2)```

Description:

In this problem we have to find all the number combinations in the array which will add upto 0. We have to consider that the output should be sorted.

Solution (three pointers)

The approach that we are talking about is to sort the array first and then have one pointer running along the length of the array. We will have another two pointer to point to the start and end of the array elements

We will check for the sum and if the sum is 0 then we we will add it to the list and move forward with increment  the second and decrement third pointer

We will ignore any duplicates along the way. Code:

```public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> list = new ArrayList<List<Integer>>();
for(int i = 0; i < nums.length-2; i++) {
if(i > 0 && (nums[i] == nums[i-1])) continue; // avoid duplicates
for(int j = i+1, k = nums.length-1; j<k;) {
if(nums[i] + nums[j] + nums[k] == 0) {
j++;k--;
while((j < k) && (nums[j] == nums[j-1]))j++;// avoid duplicates
while((j < k) && (nums[k] == nums[k+1]))k--;// avoid duplicates
}else if(nums[i] + nums[j] + nums[k] > 0) k--;
else j++;
}
}
return list;
}
}```

Time Complexity: O(n2)

• Go through the length of array elements and check for elements adjacent to the current element – O(n2)

Space Complexity: O(1)

• We will adding 3 elements to the list and can have n number of combinations  – O(n)

Available Test Cases: 311

• Check for empty array
• Check for duplicates

Github:

Leetcode_15_3_sum

1 comment