O(N logN) solution?

[Vladimir_Panchenko]

Maybe I’m doing something wrong, but I think there is an O(N logN) solution to that:

const triplet_with_smaller_sum = function (arr, target) {
  arr.sort((a, b) => a - b);

  let count = 0;

  let a = 0,
    b = 1,
    c = 2;

  while (c < arr.length && arr[a] + arr[b] + arr[c] < target) {
    c++;
    count++;
  }

  b = 2;
  c = 3;

  while (c < arr.length && b < c && arr[a] + arr[b] + arr[c] < target) {
    b++;
    count++;
  }

  a = 1;
  b = 2;
  c = 3;

  while (c < arr.length && a < b && arr[a] + arr[b] + arr[c] < target) {
    a++;
    count++;
  }

  return count;
};

Here we sort the array (O(N logN)) and iterate through it 3 times (O(3N) = O(N)), so the final time complexity is O(N logN).

Am I missing something?

[lfrah_Dar]

@Vladimir_Panchenko
No, you’re not missing anything. The solution is perfect and the final time complexity is also O(nlogn).

[Vladimir_Panchenko]

Thanks!