# Explanation of the algorithm with a simple Java O(n^2) solution

• O(n^3) is a straight-forward solution, albeit not optimal for this problem. Sorting should help you make the array look better for further optimization. Once you do that, it becomes a regular two-sum problem after that. So essentially:
sorting : nlogn
iteration: for each element , call twosum : n^2

The slightly tricky part is to avoid the duplicates. Two tricky testcases are :

1. // [-1, 0, 1, 2, -1, -4]
You may have duplicate sets of -1. The best is to skip the second occurence since we have already built up the first set.

2. //[-2,0,0,2,2]
You should skip when the current lower and higher match with the next set since it may lead to the duplicate answer.

``````    public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ll = new ArrayList<>();

Arrays.sort(nums);
for(int i=0;i<nums.length;i++) {
if(i>0 && nums[i]==nums[i-1]) {
continue;
}
int first = 0 - nums[i];
int s = i+1;
int e = nums.length-1;
while(s<e) {
if(nums[s]+nums[e]==first) {
s++;
e--;
while(s<e && nums[e]==nums[e+1] && nums[s]==nums[s-1]) {
e--;
s++;
}
}
else if(nums[s]+nums[e]>first) {
e--;
}
else {
s++;
}
}
}
return ll;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.