LeetCode Problem #15. 3Sum

Problem statement 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]
]

this problem is medium but I think it is much harder especially with the condition of non duplicate,  I'll write two solutions 

#First Solution
We want to find all triplets  (a,b,c)  such that  a+b+c=0 . In other words,  c=−(a+b) . The most straightforward  O(n^2)  solution is to enumerate all  (a,b)  pairs and check if the value  c  exists in the array, using a hash table. However, we can achieve a O(n^2) solution without extra data structures .
Lets sort the given v array in ascending order. For all triplets  (i,j,k),i < j < k , we have  v[i] ≤ v[j] ≤ v[k] .
If we enumerate all pairs  (i,j),i < j , the corresponding sum for a fixed i is non-decreasing:  v[i] + v[j] ≤ v[i] + v[j+1] ≤ v[i] + v[j+2] ≤ … ≤ v[i] + v[n] .
Conversely,  −(v[i] + v[j]) ≥ −(v[i] + v[j+1]) ≥ −(v[i] + v[j+2])...≥ −(v[i] + v[n]) .
This means that for a fixed i, if we check all values j, such that  i < j ≤ n , in increasing order, the index k corresponding to c, is decreasing. So, we can initialize an index k to the last position of the array and always decrease it when looking for a suitable value c.
To ignore duplicates, note that we never want to consider consecutive indices i or j with the same value.
source

	public List<List<Integer>> threeSum(int[] nums) {
	List<List<Integer>> result = new LinkedList<List<Integer>>();
	Arrays.sort(nums);
	for (int i = 0; i < nums.length; i++) {
	if (i > 0 && nums[i] == nums[i - 1]) {
	continue;
	}
	int k = nums.length - 1;
	for (int j = i + 1; j < nums.length; j++) {
	while (nums[j] + nums[k] + nums[i] > 0 && k > j)
	k--;
	if (j> i+1 && nums[j] == nums[j - 1] ) continue;
	if (k > j && nums[j] + nums[k] + nums[i] == 0) {
	result.add(Arrays.asList(nums[i], nums[j], nums[k]));
	}
	}
	}
	return result;
	}

view raw 3SumV1.Java hosted with ❤ by GitHub

#Second Solution
the previous solution is good but its performance is not the best, we can optimize the performance by replacing for loops with while loop.
we know we need to find triplets (a,b,c) we already have a = nums[i] we can now slove 3Sums with 2Sums problem, we need to find b & c 
where b is greater than a, and c is greater than b.

initialize low pointer low = i+1
initialize high pointer high= n-1
if sum (nums[i], nums[low], nums[high] == 0) this means we found a solution 
if sum (nums[i], nums[low], nums[high] > 0) this means we need to decrease high--
if sum (nums[i], nums[low], nums[high] < 0) this means we need to increase low++
check this version of code and check performance difference.

	class Solution {
	public List<List<Integer>> threeSum(int[] nums) {
	List<List<Integer>> result = new LinkedList<List<Integer>>();
	Arrays.sort(nums);
	for (int i = 0; i < nums.length-2; i++) {
	if (i > 0 && nums[i] == nums[i - 1]) {
	continue; // remove duplicate
	}
	int low = i+1;
	int high = nums.length -1;
	while (low < high)
	{
	while (nums[low] + nums[high] + nums[i] > 0 && high > low)
	high--;
	if (low > i+1 && nums[low] == nums[low - 1] ) {
	low++;
	continue;
	}
	if (nums[low] + nums[high] + nums[i] == 0 && high>low)
	{
	result.add(Arrays.asList(nums[i], nums[low], nums[high]));
	}
	low++;
	}
	}
	return result;
	}
	}

view raw 3SumV2.Java hosted with ❤ by GitHub

Thank you,

 Ahmed Ghazey