# 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

| Item | Meaning |
|---|---|
| Input | An integer array `nums` and an integer `target` |
| Output | The closest possible sum of three numbers |
| Index rule | Choose three distinct indices |
| Guarantee | Exactly one closest answer exists |
| Constraint | `3 <= nums.length <= 500` |

Example function shape:

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

## Examples

Example 1:

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

The triplet:

```text
[-1, 2, 1]
```

has sum:

```text
2
```

The difference from the target is:

```text
abs(2 - 1) = 1
```

No other triplet has a closer sum.

Output:

```text
2
```

Example 2:

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

The only possible triplet is:

```text
[0, 0, 0]
```

Its sum is:

```text
0
```

Output:

```text
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`.

```python
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.

| Metric | Value |
|---|---|
| Time | `O(n^3)` |
| Space | `O(1)` |

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:

```text
left = i + 1
right = n - 1
```

Now compute:

```text
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:

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

Sort:

```text
[-4, -1, 1, 2]
```

Start with the first three numbers as the initial best:

```text
best = -4 + -1 + 1 = -4
```

Fix:

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

Sum:

```text
-4 + -1 + 2 = -3
```

This is closer than `-4`, so update:

```text
best = -3
```

The sum is less than target, so move `left`.

Now:

```text
left = 2
right = 3
```

Sum:

```text
-4 + 1 + 2 = -1
```

Update:

```text
best = -1
```

Move `left` again, and this fixed `i` ends.

Next fix:

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

Sum:

```text
-1 + 1 + 2 = 2
```

Update:

```text
best = 2
```

The closest sum is:

```text
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2)` | Sorting costs `O(n log n)`, then each fixed index runs a linear two-pointer scan |
| Space | `O(1)` extra | Ignoring sorting implementation details |

## Implementation

```python
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:

```python
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:

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

For every fixed first number:

```python
for i in range(n - 2):
```

Set two pointers:

```python
left = i + 1
right = n - 1
```

Compute the sum:

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

Update the best result if this sum is closer:

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

If we hit the target exactly:

```python
if total == target:
    return target
```

Then no better answer exists.

Move the pointer based on the sum:

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

Finally:

```python
return best
```

## Testing

```python
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()
```

| Test | Why |
|---|---|
| `[-1, 2, 1, -4]`, target `1` | Standard example |
| `[0, 0, 0]`, target `1` | Only one triplet |
| `[1, 1, 1, 0]`, target `-100` | Target far below all sums |
| `[1, 1, -1, -1, 3]`, target `-1` | Exact target exists |
| Mixed positives and negatives | Checks pointer movement across sorted values |