Tue 13 Nov 2018
Three Sum Problem
Tags: programming leetcode code

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.^{1}

Brute force algorithm
It has problems like it doesn’t account for duplicate elements. Also it has complexity of @L O(n3) @L which is not optimal.

public static List < List < Integer >> threeSumAlgo1 ( int [] nums ) {
List < List < Integer >> result = new
ArrayList < List < Integer >>();
for ( int i = 0 ; i < nums . length ; i ++) {
for ( int j = i + 1 ; j < nums . length ; j ++) {
for ( int k = j + 1 ; k < nums . length ; k ++) {
if ( nums [ i ] + nums [ j ] + nums [ k ] == 0 ){
List < Integer > temp = new ArrayList <>();
temp . add ( nums [ i ]);
temp . add ( nums [ j ]);
temp . add ( nums [ k ]);
result . add ( temp );
}
}
}
}
return result ;
}

More efficient solution
Using two pointer solution, we can acheive @L O(n2) @L time complexity.

public static List < List < Integer >> threeSumAlgo2 ( int [] nums ) {
List < List < Integer >> result = new
ArrayList < List < Integer >>();
Arrays . sort ( nums );
for ( int i = 0 ; i < nums . length - 2 ; i ++) {
//fix the value
int a = nums [ i ];
int start = i + 1 ;
int end = nums . length - 1 ;
// maintain unique triplets
if ( i > 0
&& ( nums [ i ] == nums [ i - 1 ])) {
continue ;
}
while ( start < end ) {
int b = nums [ start ];
int c = nums [ end ];
int sum = a + b + c ;
// maintain unique triplets
if ( start > i + 1
&& ( nums [ start ] == nums [ start - 1 ])) {
start = start + 1 ;
continue ;
}
if ( sum == 0 ) {
List < Integer > tempResult = new ArrayList <>();
tempResult . add ( a );
tempResult . add ( b );
tempResult . add ( c );
result . add ( tempResult );
start = start + 1 ;
end = end - 1 ;
} else if ( sum > 0 ) {
end = end - 1 ;
} else {
start = start + 1 ;
}
}
}
return result ;
}

Please enable JavaScript to view the comments powered by Disqus.
comments powered by