LeetCode 16: 3Sum Closest

Problem Restatement

We are given an integer array nums and an integer target.

We need to choose three integers from nums such that their sum is as close as possible to target.

Return the sum of those three integers.

The problem guarantees that each input has exactly one solution. The constraints are 3 <= nums.length <= 500, -1000 <= nums[i] <= 1000, and -10^4 <= target <= 10^4.

Input and Output

Example function shape:

def threeSumClosest(nums: list[int], target: int) -> int:
    ...

Examples

Example 1:

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

The triplet:

[-1, 2, 1]

has sum:

2

The difference from the target is:

abs(2 - 1) = 1

No other triplet has a closer sum.

Output:

2

Example 2:

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

The only possible triplet is:

[0, 0, 0]

Its sum is:

0

Output:

0

First Thought: Try Every Triplet

The direct solution is to check every possible group of three indices.

For each triplet, compute the sum.

Then keep the sum with the smallest absolute difference from target.

class Solution:
    def threeSumClosest(self, nums: list[int], target: int) -> int:
        best = nums[0] + nums[1] + nums[2]
        n = len(nums)

        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    total = nums[i] + nums[j] + nums[k]

                    if abs(total - target) < abs(best - target):
                        best = total

        return best

This is correct, but it checks too many triplets.

Problem With Brute Force

There are O(n^3) possible triplets.

For n = 500, that is too slow.

We need to reuse the sorted order of the array, like in 3Sum.

Key Insight

Sort the array.

Then fix one number and use two pointers to choose the other two numbers.

For a fixed index i, set:

left = i + 1
right = n - 1

Now compute:

total = nums[i] + nums[left] + nums[right]

If total is smaller than target, we need a larger sum.

Because the array is sorted, moving left rightward increases or keeps the second number.

If total is larger than target, we need a smaller sum.

Moving right leftward decreases or keeps the third number.

Each step moves toward a potentially closer sum.

Visual Walkthrough

Use:

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

Sort:

[-4, -1, 1, 2]

Start with the first three numbers as the initial best:

best = -4 + -1 + 1 = -4

Fix:

i = 0
nums[i] = -4
left = 1
right = 3

Sum:

-4 + -1 + 2 = -3

This is closer than -4, so update:

best = -3

The sum is less than target, so move left.

Now:

left = 2
right = 3

Sum:

-4 + 1 + 2 = -1

Update:

best = -1

Move left again, and this fixed i ends.

Next fix:

i = 1
nums[i] = -1
left = 2
right = 3

Sum:

-1 + 1 + 2 = 2

Update:

best = 2

The closest sum is:

2

Algorithm

1. Sort nums.
2. Initialize best as the sum of the first three numbers.
3. For each index i from 0 to n - 3:
   • set left = i + 1
   • set right = n - 1
4. While left < right:
   • compute the current sum
   • update best if the current sum is closer to target
   • if the current sum equals target, return target
   • if the current sum is less than target, move left
   • otherwise, move right
5. Return best.

Correctness

After sorting, for each fixed index i, the two-pointer scan considers candidate pairs to the right of i.

When the current sum is less than target, moving right left would only make the sum smaller or equal, so it cannot move the sum closer from below. The useful move is to increase left.

When the current sum is greater than target, moving left right would only make the sum larger or equal, so it cannot move the sum closer from above. The useful move is to decrease right.

At every visited triplet, the algorithm compares its distance from target with the best distance seen so far.

If a sum equals target, no closer sum is possible, so returning immediately is correct.

Since the outer loop fixes each possible first index and the inner two-pointer scan explores the relevant monotonic search space for the other two indices, the algorithm finds the unique closest sum.

Complexity

Implementation

class Solution:
    def threeSumClosest(self, nums: list[int], target: int) -> int:
        nums.sort()

        n = len(nums)
        best = nums[0] + nums[1] + nums[2]

        for i in range(n - 2):
            left = i + 1
            right = n - 1

            while left < right:
                total = nums[i] + nums[left] + nums[right]

                if abs(total - target) < abs(best - target):
                    best = total

                if total == target:
                    return target

                if total < target:
                    left += 1
                else:
                    right -= 1

        return best

Code Explanation

Sort the numbers:

nums.sort()

This lets us move pointers based on whether the current sum is too small or too large.

Initialize best with a valid triplet:

best = nums[0] + nums[1] + nums[2]

For every fixed first number:

for i in range(n - 2):

Set two pointers:

left = i + 1
right = n - 1

Compute the sum:

total = nums[i] + nums[left] + nums[right]

Update the best result if this sum is closer:

if abs(total - target) < abs(best - target):
    best = total

If we hit the target exactly:

if total == target:
    return target

Then no better answer exists.

Move the pointer based on the sum:

if total < target:
    left += 1
else:
    right -= 1

Finally:

return best

Testing

def run_tests():
    s = Solution()

    assert s.threeSumClosest([-1, 2, 1, -4], 1) == 2
    assert s.threeSumClosest([0, 0, 0], 1) == 0
    assert s.threeSumClosest([1, 1, 1, 0], -100) == 2
    assert s.threeSumClosest([1, 1, -1, -1, 3], -1) == -1
    assert s.threeSumClosest([4, 0, 5, -5, 3, 3, 0, -4, -5], -2) == -2

    print("all tests passed")

run_tests()