3Sum Closest

The 3Sum Closest Problem is a classic programing problem used to demonstrate the application of algorithms. It is a variant of the 3Sum Problem , which asks for three numbers in an array whose sum is equal to a given number. In 3Sum Closest, the goal is to find three numbers in an array whose sum is closest to a given number.

The solution to this problem makes use of the two pointer approach. The first step is to sort the input array. We then loop through the array and select one number at a time. We then use two pointers to search for the two other numbers that would sum up with the number to give us the closest sum to the given number.

    // Sort our list 
    let sortedList = list.sort((a, b) => a - b);

    let result = Number.MAX_VALUE;
    // Loop through the list 
    for (let i = 0; i < sortedList.length - 2; i++) {
        // Set left and right pointer 
        let left = i + 1;
        let right = sortedList.length - 1;

        // Loop through the list 
        while (left < right) {
            // Calculate current sum 
            const currSum = sortedList[i] + sortedList[left] + sortedList[right];

            // Check if the sum is closer to the given number than the current result 
            if (Math.abs(currSum - givenNumber) < Math.abs(result - givenNumber)) {
                result = currSum;
            }

            // Check if the sum is greater than the given number 
            if (currSum > givenNumber) {
                // Decrement right pointer 
                right--;
            } else {
                // Increment the left pointer 
                left++;
            }
        }
    }

    return result;
  

The above code implements the two pointer approach to solve the 3Sum Closest Problem. We first sort the input list and then loop through it. We then use two pointers to search for the two other numbers that would sum up with the number to give us the closest sum to the given number. We use the Math.abs() function to compare the difference between the given sum and the current sum to determine which one is the closest.

This solution has a time complexity of O(n^2) and a space complexity of O(1).