3Sum Closest in JavaScript: Sorting and Two Pointers

The 3Sum Closest problem is a variation of the well‑known 3Sum problem, which I wrote about and solved in JavaScript (TypeScript) earlier this week.

The problem is fairly simple: given an array nums of n integers and an integer target, find three integers within nums that produce the closest possible value to target when summed. Return the sum of these three integers.

Some Examples

Input: nums = [‑1, 2, 1, ‑4], target = 1
Output: 2
The sum that is closest to the target is 2 = (‑1) + 2 + 1.

Input: nums = [0, 2, 1, ‑3], target = 1
Output: 0
Here, the closest sum to 1 is 0, which we get by combining 0, 1, and ‑1.

Input: nums = [‑1, 0, 1, 1, 55], target = 3
Output: 2
In this case, the closest sum is 2 from (‑1) + 1 + 1.

How It Relates to 3Sum

Given that we've just tackled the 3Sum problem earlier this week, this problem feels very familiar. The fundamental difference lies in what we've looking for: whilst 3Sum aims to find a combination that equals a specific (and exact) sum, 3Sum Closest wants to find the combination whose sum is nearest to a given target.

Approach

The steps for solving the '3Sum Closest' problem (using the two‑pointer technique) are in many ways similar to the original '3Sum' problem, with some critical differences to adapt to the new requirements. Here's a rundown:

1. Sort the Array:

   As with the '3Sum' problem, sort the input array in ascending order. This simplifies our process and helps us handle duplicates and find solutions more efficiently.

2. Fix One Element:

   Choose one element as a fixed point; for ease of implementation, you can choose the element at index i.

3. Use Two Pointers:

   With the fixed element at index i, use two pointers, left and right, to find the two other elements. Instead of looking for a sum that negates the fixed element (as in '3Sum'), we're now looking for a sum that is closest to the given target value.

4. Adjust the Pointers:

   If the sum of elements at nums[i], nums[left], and nums[right] is less than the target, move the left pointer to the right to increase the sum.
5. If the sum is greater than the target, move the right pointer to the left to decrease the sum.

6. Record Closest Sum:

   Keep track of the triplet that provides the sum closest to the target as you go. If you find a sum that is equal to the target, you can return it immediately as it's the closest possible sum.

7. Avoid Duplicates:

   To ensure the uniqueness of the solution, skip over elements with the same value at nums[i], nums[left], and nums[right] just as in the original 3Sum problem.

Implementation in TypeScript

Here's a version in TypeScript I wrote to illustrate:

const threeSumClosest = (nums: number[], target: number): number => {  nums.sort((a, b) => a - b);  let closest = Infinity;  for (let i = 0; i < nums.length - 2; i++) {    let left = i + 1;    let right = nums.length - 1;    while (left < right) {      const sum = nums[i] + nums[left] + nums[right];      if (Math.abs(target - sum) < Math.abs(target - closest)) {        closest = sum;      }      if (sum < target) {        left++;      } else {        right--;      }    }  }  return closest;};

How It Works

1. First, we sort the array, which is crucial for the two‑pointers technique to work effectively.
2. Initialise closest with Infinity to hold the closest sum we find.
3. Use a for‑loop to fix one element (nums[i]) and then use two pointers (left and right) to find the other two elements that make the sum closest to the target.

Wrapping‑Up

So, is 3Sum Closest just 3Sum with a slight twist? In a way, yes. The same technique (two‑pointers) applies well but with the added layer of finding the sum that is "closest" to a target rather than matching it exactly.

By understanding these subtle differences, you refine your problem‑solving skills and reinforce your grasp of algorithmic techniques, which is essential for any serious web developer.