PROBLEM STATEMENT
This problem is from Leetcode – 3Sum. The problem statement in short is given below:
Given an integer array nums, find all unique triplets [a, b, c] such that a + b + c = 0.
Return a list of all such unique triplets. The solution set must not contain duplicate triplets.
SOLUTION
FIRST APPROACH
Lets try the brute force approach first.
public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> threeSum = new HashSet<List<Integer>>();
List<Integer> sumList = new ArrayList<Integer>();
int len = nums.length;
for(int i=0; i<len-2; i++) {
int first = nums[i];
for(int j=i+1; j<len-1; j++) {
int second = nums[j];
for(int k=j+1; k<len; k++) {
int third = nums[k];
if(first + second + third == 0 ) {
sumList = new ArrayList<Integer>();
sumList = Arrays.asList(first, second, third);
// sort list before adding
Collections.sort(sumList);
threeSum.add(sumList);
} // endIf
}
}
}
return new ArrayList<List<Integer>>(threeSum);
}You can checkout the code from Github here – 3Sum – FirstApproach
PERFORMANCE ANALYSIS
| COMPLEXITY | O (N3) |
SECOND APPROACH
Lets try the HashSet Approach.
public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> threeSum = new HashSet<List<Integer>>();
List<Integer> sumList = new ArrayList<Integer>();
Arrays.sort(nums);
int len = nums.length;
for(int i=0; i<len-2; i++) {
// skip duplicates
if(i>0 && nums[i] == nums[i-1])
continue;
int first = nums[i];
Set<Integer> numsSet = new HashSet<>();
for(int j=i+1; j<len; j++) {
int second = nums[j];
// target val
int third = (first+second)*-1;
// check if target exists in map
if(numsSet.contains(third)) {
sumList = new ArrayList<Integer>();
sumList.add(first);
sumList.add(second);
sumList.add(third);
// sort list before adding
Collections.sort(sumList);
threeSum.add(sumList);
}
numsSet.add(nums[j]);
}
}
return new ArrayList<List<Integer>>(threeSum);
}You can checkout the code from Github here – 3Sum – SecondApproach
PERFORMANCE ANALYSIS
| RUNTIME | 437 ms | Beats 18.00 % |
| MEMORY | 53.59 MB | Beats 9.07 % |
| TIME COMPLEXITY | O (N2) |
| SPACE COMPLEXITY | O (N) |
THIRD APPROACH
example:
int nums = {1,2,-3}
Create a pairwise 2-D sum matrix as below. Skip when i == j :
0 1 2
_______________
0 | - 3 -2
1 | 3 - -1
2 | -2 -1 -
Create a HashMap with indices as key and sum as val:
map.add("0,1", 3);
map.add("0,2", -2);
map.add("1,0", 3);
map.add("1,2", -1);
map.add("2,0", -2);
map.add("2,1", -1);
This approach ensures that key is different even if the sum is same.
We’ll use this 2-D sum matrix to find the complement. See the code sample below:
public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> threeSum = new HashSet<List<Integer>>();
List<Integer> sumList = new ArrayList<Integer>();
Map<String, Integer> numsSumMap = new HashMap<>();
int len = nums.length;
// create the 2-D sum matrix
for(int i=0; i<len; i++) {
for(int j=0; j<len; j++) {
if(i!=j) {
String val = i +"," + j;
numsSumMap.put( val, nums[i] + nums[j]);
}
}
}
// now traverse the input and see if its complement exists in above matrix
for(int k=0; k<len; k++) {
int target = nums[k]*-1;
int third = nums[k];
if(numsSumMap.containsValue(target)) {
for(String key: numsSumMap.keySet()) {
if(numsSumMap.get(key).equals(target)) {
String val = key;
String[] valArr = val.split(",");
int i = Integer.parseInt(valArr[0]);
int j = Integer.parseInt(valArr[1]);
int first = nums[i];
int second = nums[j];
if( i != j && j!=k && i!=k ) {
sumList = Arrays.asList(first, second, third);
// sort list before adding
Collections.sort(sumList);
threeSum.add(sumList);
} // endIf
}
}
}
}
return new ArrayList<List<Integer>>(threeSum);
}
You can checkout the code from Github here – 3Sum – ThirdApproach
FOURTH APPROACH
Take the above pairwise 2-D sum matrix and flatten it.
0 1 2
_______________
0 | - 3 -2
1 | 3 - -1
2 | -2 -1 -
||
\/
___ ___ ___
| 0 | - | 3 | -2 | 1 | 3 | - | -1 | 2 | -2 | -1 | - |
| | |
index index index
The idea is to reduce the traverse time from O(N2) to O(N) while searching for the complement. See the code sample below:
public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> threeSum = new HashSet<List<Integer>>();
List<Integer> sumList = new ArrayList<Integer>();
int len = nums.length;
Integer[][] numsSumMat = new Integer[len][len];
for(int i=0; i<len; i++) {
for(int j=0; j<len; j++) {
if(i != j) {
numsSumMat[i][j] = nums[i] + nums[j] ;
}
else {
numsSumMat[i][j] = Integer.MAX_VALUE;
}
}
}
// flatten 2d array
Integer[] numSumFlatten = new Integer[(len*len) + len];
int idx = 0;
for(int i=0; i<len; i++) {
numSumFlatten[idx++] = i;
for(int j=0; j<len; j++) {
numSumFlatten[idx++] = numsSumMat[i][j] ;
}
}
// now traverse and find the complement
for(int index=0; index<len; index++) {
int target = nums[index]*-1;
int third = nums[index];
int row = 0;
int col = 0;
int count = 1;
for(int k=0; k<numSumFlatten.length; k++) {
if(numSumFlatten[k] == target &&
numSumFlatten[k] != Integer.MAX_VALUE &&
col != 0 && index != row && index != (col-1) ) {
int first = nums[row];
int second = nums[col-1];
sumList = sumList = Arrays.asList(first, second, third);
// sort list before adding
Collections.sort(sumList);
threeSum.add(sumList);
}
// col goes from 0 to len
if(count == len+1) {
col = 0;
row = row+1;
count = 1;
}
else {
col++;
count = count+1;
}
}// endfor
}
return new ArrayList<List<Integer>>(threeSum);
}You can checkout the code from Github here – 3Sum – FourthApproach
FIFTH APPROACH
Finally, lets try the 2-pointer approach. See the code sample below:
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> threeSum = new ArrayList<List<Integer>>();
Arrays.sort(nums);
int len = nums.length;
for(int i=0; i<len-2; i++) {
// skip duplicates
if(i>0 && nums[i] == nums[i-1]) {
continue;
}
int j = i+1;
int k = nums.length-1;
while(j < k) {
int sum = nums[i] + nums[j] + nums[k];
if(sum == 0) {
threeSum.add(Arrays.asList(nums[i] , nums[j] , nums[k]));
// skip duplicates
while (j < k && nums[k] == nums[k - 1]) k--;
while (j < k && nums[j] == nums[j + 1]) j++;
j++;
k--;
} //endif
else if(sum < 0) {
j++;
}
else if(sum > 0) {
k--;
}
} // endwhile
}// end outer for loop
return threeSum;
}
You can checkout the code from Github here – 3Sum – FifthApproach
PERFORMANCE ANALYSIS
| RUNTIME | 30 ms | Beats 70.19 % |
| MEMORY | 51.55 MB | Beats 57.01 % |
| TIME COMPLEXITY | O (N2) |
| SPACE COMPLEXITY | O (K) |