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).