JavaScript solutions for a Google interview problem

google-problem.js

arr1 = [1, 2, 3, 9];
arr2 = [1, 2, 4, 4];

// Method 1
// Time Complexity: O(N^2)
// Space Complexity: O(1)

const findSum = (arr, val) => {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (i !== j && arr[i] + arr[j] === val) {
        return true;
      };
    };
  };
  return false;
};

// Method 2
// Time Complexity: O(NlogN)
// Space Complexity: O(1)

const findSum = (arr, val) => {
  for (let i = 0; i < arr.length; i++){
      if (binarySearch(removeIndex(arr, i), val - arr[i])) {
      return true
    }
  };
  return false;
};

const removeIndex = (arr, i) => {
  return arr.slice(0,i).concat(arr.slice(i + 1, arr.length));
};

const binarySearch = (arr, val) => {
  let start = 0;
  let end = arr.length - 1;
  let pivot = Math.floor(arr.length / 2);
  while (start < end) {
    if (val < pivot) {
      end = pivot - 1;
    } else {
      start = pivot + 1;
    };
    pivot = Math.floor((start + end) / 2);
    if (pivot === val) {
      return true;
    }
  };
  return false;
};


// Method 3: O(N)
// Time Complexity: O(N)
// Space Complexity: O(1)

const findSum = (arr, val) => {
  let start = 0;
  let end = arr.length - 1;
  while (start < end) {
    let sum = arr[start] + arr[end];
    if (sum > val) {
      end -= 1;
    } else if (sum < val) {
      start += 1;
    } else {
      return true;
    };
  };
  return false;
};


// Method 4: O(N) - No longer guarantee that the array is sorted
// Time Complexity: O(N(N - 1)) => O(2N - 1) => O(N)
// Space Complexity: O(N)

const findSum = (arr, val) => {
  let searchValues = [val - arr[i]];
  for (let i = 1; i < arr.length; i++) {
    let searchVal = val - arr[i];
    if (searchValues.includes(searchVal)) {
      return true;
    } else {
      searchValues.push(searchVal);
    }
  };
  return false;
};