3Sum closest

Given an array of integers and a target, find a triplet in the array such that their sum is closest to the target. Return the closest sum.

Example

Input:
arr = [1, -1, 2, -4]
target = 1

Output:
2
Closest sum to the target is 2. (1 + (-1) +2).

This problem is a variation of 3sum problem, where we check if there exists a triplet whose sum is equal to the given target.

Recursive solution: 3sum closest.

Conceptually this is how it works,

• Sort the input array.
• Use a object to store the closest sum which will be passed as reference to the recursive function.
• As we have to find triplets, pass the number (3 in this case) to get the sum of those number of combinations of elements in the array.
• Once we have the sum of combination of numbers, check if it is closest to the target or not, if it is then store it.
• Base case: when we have reached the limit of combinations.

By updating the max count you can use this function for any number of combinations.

const threeSumClosest = (nums, target) => {
    //sort the array
    nums = nums.sort((a, b) => a - b);
  
    //object to store the result,
    //will be passed as reference
    const result = {
        distance: Number.MAX_VALUE,
        nearest: target
    };
    
    //helper function to find the closest sum to target
    helper(nums, 0, 0, 3, 0, result, target);   
    
    //return the closest sum
    return result.nearest;
};

const helper = (arr, startIndex, length, max, sum, result, target) => {
    //base case
    if(length > max){
        return;
    }
  
    //if we have max(3) numbers combination 
    if(length === max){
        //difference between target and sum
        let calc = Math.abs(sum - target);
        
        //closest sum
        if(calc < result.distance){
            result.nearest = sum;
            result.distance = calc;
        }
      
        return;
    }
    
    //get sum of all max(3) combinations 
    for(let i = startIndex; i < arr.length; i++){
        helper(arr, i + 1, length + 1, max, sum + arr[i], result, target);
    }
}

Input:
const arr = [-1,2,1,-4];
const target = 1;
console.log(threeSumClosest(arr, target));

Output:
2

Time complexity: O(n ^ m).
Space complexity: O(n).

---

Iterative solution: 3sum closest.

In the iterative approach,

• Sort the array.
• Iterate the elements for the array and in each iteration.
• Use two index trackers, one which starts from front and other which starts from end.
• Keep on iterating till both index does not meet, basically get all the triplets combination.
• Calculate the closest sum for each triplets and return the minimum among them.

Unlike recursive solution, this approach is specific for triplets only.

const threeSumClosest = (nums, target) => {
    //sort the array;
    nums = nums.sort((a,b)=>a-b);
    
    //to store closestSum
    let closestSum = Infinity;
  
    //iterate the array
    for (let i = 0; i < nums.length; i ++) {
        //tracker
        let left = i + 1;
        let right = nums.length -1;
      
        //iterate till we have all the combinations
        while (left < right) {
            //sum of the triplets
            let sum = nums[i] + nums[left] + nums[right];
            
            // calc closestSum
            if (Math.abs(sum - target) < Math.abs(closestSum - target)) closestSum = sum;
          
            //update the tracker
            if (sum > target) {
                right --
            } else {
                left ++
            }
        }
    }
    return closestSum;
};

Input:
const arr = [-1,2,1,-4];
const target = 1;
console.log(threeSumClosest(arr, target));

Output:
2

Time complexity: O(n ^ 2).
Space complexity: O(1).