Some findings on 3sum leatcode solutions
Just recently, while practicing coding in leetcode, I came over with this 3sum problem.
Given an integer array numbers, return all the triplets such that i != j, i != k, and j != k, and numbers[i] + numbers[j] + numbers[k] == 0, result should not contain any duplicate triplet.
There're couples of solutions for this problem, the most naive approach is to have three different loops on the numbers array, and try to find a triplet having numbers[i] + numbers[j] + numbers[k] = 0;
This solution is intuitive but not optimize, the runtime complexity is O(n^3) where n is the length of the numbers array.
Looking into the condition, we have to find a triplet where numbers[i] + numbers[j] + numbers[k] = 0, that means:
numbers[i] + numbers[j] = -numbers[k]
So, if we can have a hashmap to track the map between value of each item in number array to its index, we can reduce from three loops into two.
private static List<List<Integer>> threeSum(Integer[] nums) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int length = nums.length;
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (length < 3) {
return result;
}
for (int i = 0; i < length; i++) {
map.put(-nums[i], i);
}
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
int sum = nums[i] + nums[j];
if (map.containsKey(sum )) {
int loc = map.get(sum);
if (loc > j) {
List<Integer> list = Arrays.asList(nums[i],nums[j],nums[loc]);
list.sort(null);
if (!isExist(result, list)) {
result.add(list);
}
}
}
}
}
return result;
}
private static boolean isExist(List<List<Integer>> list, List<Integer> item) {
for (int i = 0; i < list.size(); i++) {
for(int j = 0; j < list.get(i).size(); j++){
if(list.get(i).get(j).equals(item.get(j))){
if(j == list.get(i).size() - 1){
return true;
} else {
continue;
}
} else {
break;
}
}
}
return false;
}
The method isExist() duty is to make sure the output will not contain any duplicate triplet.
With this algorithm, we have runtime complexity is O(n^2) and space complexity is O(n).
The runtime complexity is O(n^2) is the best time we can achieve, as we have to calculate the sum of at least two items in the numbers array.
After submitting this algorithm to leetcode, it seems like the result is correct for most of the test data, however, there're test cases failed with "Time Limit Exceeded" error.
It makes me surprise on why the algorithm is not good enough, so I did some bench-marking on the algorithm to find out the root cause. Dig deeper to the algorithm, I suspect the problem may come from the isExist() method, which it does not run fast enough.
At first I tried to see if converting the list from ArrayList to LinkedList would have any difference (would use Iterator with LinkedList).
List<List<Integer>> result = new LinkedList<List<Integer>>();
...
private static boolean isExist(List<List<Integer>> list, List<Integer> item) {
Iterator<List<Integer>> iterator = list.iterator();
while(iterator.hasNext()){
List<Integer> data = iterator.next();
for(int j = 0; j < data.size(); j++){
if(data.get(j).equals(item.get(j))){
if(j == data.size() - 1){
return true;
} else {
continue;
}
} else {
break;
}
}
}
return false;
}
Running test case with numbers array has 3000 item that has around 16k triplet in the output, I can see that:
The isExist() method using ArrayList is much faster than the one using LinkedList (not a surprise result); so the problem is still there...
Another improvement we can do is to sort the numbers array at first, and try to mimic any item that appears more than twice in the array. This improvement does help a little bit, but it does not help to fix the time limit exceeded error.
After thinking for a while, I think we can keep a hash map of the triplet, so that we can exclude any duplicate triplet easier. It's better to flatten the triplet to a string, with some 'salt' in it. Here I will use "|" as a 'salt' to hash to triplet to string and use it as key of the map.
Map<String,Integer> resultKeyMap = new HashMap<String, Integer>();
...
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
int sum = nums[i] + nums[j];
if (map.containsKey(sum )) {
int loc = map.get(sum);
if (loc > j) {
List<Integer> list = Arrays.asList(nums[i],nums[j],nums[loc]);
list.sort(null);
String key = list.get(0) + "|" + list.get(1) + "|" + list.get(2);
if(!resultKeyMap.containsKey(key)){
result.add(list);
resultKeyMap.put(key, result.size() - 1);
}
}
}
}
}
And voila', the improvement here did by-pass the time limit exceeded error.
A downside of this change is to require an extra O(k) to the space complexity (where k is the number of non-duplicate triplet that satisfy the condition).
Happy coding!
Comments
Post a Comment