Leetcode 16: 3Sum Closest

 

1. Problem Statement (Simple Explanation):

You are given:

• An integer array nums of length n

• An integer target

You must choose three distinct indices i, j, k such that the sum:

            sum = nums[i] + nums[j] + nums[k]

is as close as possible to target.

Return:

• The sum of the three integers (not the triplet itself).

You are guaranteed that exactly one best answer exists.

2. Examples:

Example 1:

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

All possible triplet sums (showing the relevant ones):

• -1 + 2 + 1 = 2

• -1 + 2 + (-4) = -3

• -1 + 1 + (-4) = -4

• 2 + 1 + (-4) = -1

Differences from target 1:

• |2 - 1| = 1

• |-3 - 1| = 4

• |-4 - 1| = 5

• |-1 - 1| = 2

Closest is 2.

Output: 2

Example 2:

Input: nums = [0,0,0], target = 1

Only triplet sum:

• 0 + 0 + 0 = 0

Difference:

• |0 - 1| = 1

Output: 0

3. Approach 1 – Brute Force (O(n³), Just for Understanding):

• Try all triplets (i, j, k) with i < j < k.

• Compute each sum.

• Track the one with minimum |sum - target|.

Time complexity:

• O(n3), which is too slow for n up to 500 (approx 20M triplets).

We need a better approach.

4. Approach 2 – Sort + Two Pointers (O(n²), Recommended):

This is very similar in structure to 3Sum, but instead of finding exact sum == 0, we track the closest sum to target.

Intuition:

1. Sort the array nums.

2. Fix one index i as the first element.

3. Use two pointers:

• left = i + 1

• right = n - 1

4. Compute:

• sum = nums[i] + nums[left] + nums[right]

5. Compare |sum - target| with current best difference:

• If smaller → update the best sum.

6. Adjust pointers:

• If sum < target, we need a bigger sum → move left++.

• If sum > target, we need a smaller sum → move right--.

• If sum == target → exactly closest possible → return sum immediately.

No need to worry about duplicate triplets, because we only return the sum, not the list of triplets.

Algorithm (Step-by-Step):

1. Sort nums.

2. Initialize:

• closestSum = nums[0] + nums[1] + nums[2] (first possible triplet).

3. For each i from 0 to n - 3:

• left = i + 1

• right = n - 1

• While left < right:

• sum = nums[i] + nums[left] + nums[right]

• If |sum - target| < |closestSum - target|:

• Update closestSum = sum.

• If sum < target:

• Move left++

• Else if sum > target:

• Move right--

• Else:

• Return target (exact match).

4. After the loops, return closestSum.

Pseudo-code (Sort + Two Pointers):

Complexity:

• Sorting: O(n*logn)

• Outer loop i: O(n)

• Inner two-pointer: O(n)

Overall:

• Time: O(n2)

• Space: O(1) extra (in-place sort aside)

This is optimal for this problem.

5. Java code:

6.  C code:

7. C++ code:

8. Python code:

9. JavaScript code:

<<<PREV