I wrote an algorithm that takes in an array and a targetSum integer and then outputs an array of arrays of all triplet values that add to the targetSum. I’m just not sure if it runs in O(N^2*log(N)) or O(N^2) time. Would the sorting be negligible in comparison to the nested loop or no?
function threeNumberSum(array, targetSum) {
array.sort((a, b) => a - b);
const triplets = [];
for (let i = 0; i < array.length - 2; i++) {
let left = i + 1;
let right = array.length - 1;
while (left < right) {
const currentSum = array[i] + array[left] + array[right];
if (currentSum === targetSum) {
triplets.push([array[i], array[left], array[right]]);
left++;
right--;
} else if (currentSum < targetSum) {
left++;
} else if (currentSum > targetSum) {
right--;
}
}
}
return triplets;
}