I'm trying to solve Three Sum (find all triplets that add to 0 within an array avoiding duplicate cases) but currently running into a bug I can't seem to find.
When the input is [-1,0,1,2,-1,-4], it works fine.
With this input however, [-1,0,1,2,-1,-4,-2,-3,3,0,4] I'm getting this array as output:
[[-1,-1,2],[-1,0,1],[-2,0,2],[-3,0,3],[-3,1,2],[-4,0,4],[-4,1,3]].
The correct output should be
[[-4,0,4],[-4,1,3],[-3,-1,4],[-3,0,3],[-3,1,2],[-2,-1,3],[-2,0,2],[-1,-1,2],[-1,0,1]]
So for some reasons my solution is omitting the triplets [-3,-1,4] and [-2,-1,3].
var threeSum = function (nums) {
const sorted = nums.sort()
const output = []
for (let i = 0; i < sorted.length - 2; i++)
if (i === 0 || (i > 0 && sorted[i] !== sorted[i - 1])) {
let lower = i + 1
let higher = sorted.length - 1
while (lower < higher) {
const currentSum = sorted[i] + sorted[lower] + sorted[higher];
if (currentSum === 0) {
output.push([sorted[i], sorted[lower], sorted[higher]])
while (sorted[lower] === sorted[lower + 1]) lower++
while (sorted[higher] === sorted[higher - 1]) higher--
lower++
higher--
}
else if (currentSum < 0) {
lower++
} else {
higher--
}
}
}
}
return output
};
By default Javascript sorts via string comparison.
You want to sort numerically so use
nums.sort(function(a, b){return a - b});