Array Three Sum

Interviewer Prompt

Given an array of distinct integers (non repeating) and an integer representing a target sum, write a function that returns an array of all triplets in the input array that sum up to the target sum.

if no three numbers sum up to the target sum, the function should return an empty array.

Examples

arrayThreeSum([12, 3, 1, 2, -6, 5, -8, 6], 0)   //should return [[-8, 2, 6], [-8, 3, 5], [-6, 1, 5]]
arrayThreeSum([1, 15, -5, 12 , -3, 6 , 2], 10)  //should return [[ -3, 1, 12 ]]
arrayThreeSum([5, 6 , 1, -9 , 7, 3 , 2], 35)    //should return []

Interviewer Strategy Guide

Let's think about time complexity. If your interviewee tries to go down the path of trying all possible combinations of three integers (i.e three for loops), that will have a time complexity of O(n^3). Try to encourage them to find a more optimal approach.

Hints to give the interviewee

The input array is NOT sorted, we still can sort the input array and then use that sorted array to help us optimize the solution (comparing smallest number to the largest until we reach our deserved sum)

Solutions

Optimized Solution 1: O(n^2) time complexity, O(n) space complexity

function arrayThreeSum(arr, targetSum){

   //sorts the input array from least to greatest
  arr.sort((a, b) => a - b) 

  const triplets = []

  for (let i = 0; i < arr.length - 2; i++){
    let currentElement = arr[i]
    let left = i + 1 //index
    let right = arr.length - 1 //index

    //for each element in the array check to see if any two other integers in the array add to the target sum
    
    while(left < right){ //less than
      let currentSum = arr[i] + arr[left] + arr[right]

      //if the currentSum is equal to the target sum add an array of those 3 integers to the triplets array

      if(currentSum === targetSum){
        triplets.push([currentElement, arr[left], arr[right]])
        left++;
        right--;
      } else if(currentSum > targetSum){
        right--
      } else if (currentSum < targetSum){
        left++
      }
    }
  }
  return triplets
}

Optimized Solution 2 - Using Hash Table - unsorted: O(n^2) time complexity, O(n) space complexity

function arrayThreeSum(arr, targetSum){

  const triplets = []
  
  for(let i = 0; i < arr.length - 1; i++){
  
    let currentElement = arr[i]
  
    //the sum needed given we already know the value of one of our elements
    let currentSumNeeded = targetSum - currentElement
    
  
    //hash table stores all of the current elements we have tried
    let hashTable = {} 
    
    for (let j = i + 1; j < arr.length; j++){
    
      let nextElement = arr[j]
    
      if(hashTable[currentSumNeeded - nextElement]){
      
        triplets.push([currentElement, currentSumNeeded - nextElement, nextElement])
        
      } else {
      
        hashTable[nextElement] = true
      }
    }
  }
  return triplets
}

https://repl.it/@kyvyCodes/Array3sum#index.js