educative.io

Educative

Can we use binary search for finding the third element and reduce the runtime to O(NlogN)?

Having a sorted array, and using two pointers on the opposite ends of the array (moving them inward), gives us the sorted middle section for an easy binary search operation of the third item. This can effectively reduce the runtime to O(NlogN). Or am I missing something?

Like this:

const search_triplets = function(arr) {
  triplets = [];
  // TODO: Write your code here
  arr.sort((a, b) => {
    if (a < b) return -1;
    if (a > b) return 1;
    return 0;
  });
  const unique = new Set();
  const bisect = (left, right) => {
    const target = arr[left] + arr[right];
    let lo = left + 1;
    let hi = right - 1;
    while (lo <= hi) {
      const mid = lo + Math.floor((hi - lo) / 2);
      const c = arr[mid] + target;
      if (c === 0) return mid;
      if (c < 0) lo = mid + 1;
      if (c > 0) hi = mid - 1;
    }
    return -1;
  };

  const record = (left, right, mid) => {
    const leftValue = arr[left];
    const midValue = arr[mid];
    const rightValue = arr[right];
    const signature = `${leftValue},${midValue},${rightValue}`;
    if ((leftValue + midValue + rightValue) !== 0) return;
    if (unique.has(signature)) return;
    unique.add(signature);
    triplets.push([leftValue, midValue, rightValue]);
  };

  let left = 0;
  let right = arr.length  - 1;
  let mid = -1;

  while (left < right) {
    mid = bisect(left, right);
    if (mid !== -1) record(left, mid, right);
    mid = bisect(left, right - 1);
    if (mid !== -1) record(left, mid, right - 1);
    mid = bisect(left + 1, right);
    if (mid !== -1) record(left + 1, mid, right);
    left += 1;
    right -= 1;
  }
  return triplets;
};

Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Triplet Sum to Zero (medium) - Grokking the Coding Interview: Patterns for Coding Questions