# 3Sum Closest
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/3sum-closest)
Canonical: https://scaleengineer.com/dsa/problems/3sum-closest
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Google](https://scaleengineer.com/companies/google), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [Zoho](https://scaleengineer.com/companies/zoho), [tcs](https://scaleengineer.com/companies/tcs)
---
## Problem
Given an integer array `nums` of length `n` and an integer `target`, find three integers in `nums` such that the sum is closest to `target`.

Return _the sum of the three integers_.

You may assume that each input would have exactly one solution.

**Example 1:**

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

**Example 2:**

**Input:** nums = [0,0,0], target = 1
**Output:** 0
**Explanation:** The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

**Constraints:**

* `3 <= nums.length <= 500`
* `-1000 <= nums[i] <= 1000`
* `-104 <= target <= 104`

# Approaches
## Brute Force with Triple Nested Loops
The brute-force approach is the most straightforward way to solve the problem. It involves checking every possible combination of three distinct numbers from the input array, calculating their sum, and keeping track of the sum that is closest to the given target.
**Time:** O(n^3) · **Space:** O(1)
**Pros:** Simple to understand and implement.; It does not require any modification of the input array, such as sorting.
**Cons:** Extremely inefficient due to its cubic time complexity.; Will likely result in a 'Time Limit Exceeded' error on most coding platforms for larger inputs, although it might pass given the problem's constraints (n <= 500).
### Explanation
This method systematically explores all possible triplets in the array. We use three nested loops to select three distinct elements. The outer loop runs from the first element to the third-to-last, the middle loop from the element after the outer loop's current element to the second-to-last, and the inner loop from the element after the middle loop's current element to the last.

Inside the innermost loop, we compute the sum of the three selected numbers. We then find the absolute difference between this sum and the target. We maintain a variable, `closestSum`, initialized with the sum of the first three elements. If the current triplet's sum is closer to the target than `closestSum`, we update `closestSum`. After checking all triplets, `closestSum` will hold the required result.

```java
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int n = nums.length;
        // Initialize with the sum of the first three elements as a baseline
        int closestSum = nums[0] + nums[1] + nums[2];

        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    int currentSum = nums[i] + nums[j] + nums[k];
                    // If the current sum is closer to the target, update closestSum
                    if (Math.abs(target - currentSum) < Math.abs(target - closestSum)) {
                        closestSum = currentSum;
                    }
                }
            }
        }
        return closestSum;
    }
}
```
### Algorithm
- Initialize a variable `closestSum` to the sum of the first three elements of the array.
- Use three nested loops to iterate through all unique triplets of indices `(i, j, k)` such that `i < j < k`.
- For each triplet, calculate the `currentSum = nums[i] + nums[j] + nums[k]`.
- Compare the absolute difference `|target - currentSum|` with the absolute difference `|target - closestSum|`.
- If the `currentSum` is closer to the `target`, update `closestSum` to `currentSum`.
- After iterating through all possible triplets, return `closestSum`.

## Sorting with Two Pointers
A much more efficient approach involves sorting the array first. After sorting, we can iterate through the array, and for each element, use the two-pointer technique on the rest of the array to find the other two elements. The two pointers, one starting from the element after the current one and the other from the end of the array, converge towards each other, efficiently finding the triplet sum closest to the target.
**Time:** O(n^2) · **Space:** O(log n) to O(n)
**Pros:** Significantly faster than the brute-force method, with a time complexity of O(n^2).; It's a standard and widely applicable pattern for solving `k-sum` type problems.
**Cons:** Requires modifying the input array by sorting it. If the original array must be preserved, a copy is needed, which increases space complexity to O(n).; Slightly more complex to implement than the brute-force approach.
### Explanation
The key to optimizing this problem is to sort the array first. Sorting allows us to use a more intelligent way to find the other two numbers instead of iterating through all pairs.

We iterate through the sorted array with a single loop, fixing the first number of our potential triplet, `nums[i]`. For each `nums[i]`, we need to find two other numbers in the subarray `nums[i+1...n-1]` whose sum with `nums[i]` is as close to `target` as possible. This subproblem can be solved in linear time using two pointers.

We set a `left` pointer to `i + 1` and a `right` pointer to `n - 1`. We then move these pointers inward based on the comparison of their sum with the target. If `nums[i] + nums[left] + nums[right]` is less than the target, we need a larger sum, so we increment `left`. If it's greater, we need a smaller sum, so we decrement `right`. At each step, we check if the current sum is closer to the target than our best-so-far sum and update it if necessary. This process continues until the `left` and `right` pointers cross.

```java
import java.util.Arrays;

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        // Sort the array to enable the two-pointer approach
        Arrays.sort(nums);
        int n = nums.length;
        // Initialize closestSum with the sum of the first three elements
        int closestSum = nums[0] + nums[1] + nums[2];

        // Iterate through the array to fix the first element of the triplet
        for (int i = 0; i < n - 2; i++) {
            int left = i + 1;
            int right = n - 1;

            // Use two pointers to find the other two elements
            while (left < right) {
                int currentSum = nums[i] + nums[left] + nums[right];

                // If the exact sum is found, it's the closest possible. Return it.
                if (currentSum == target) {
                    return target;
                }

                // Check if the current sum is closer to the target than the best we've found so far
                if (Math.abs(target - currentSum) < Math.abs(target - closestSum)) {
                    closestSum = currentSum;
                }

                // Move pointers to get closer to the target
                if (currentSum < target) {
                    left++; // Need a larger sum
                } else {
                    right--; // Need a smaller sum
                }
            }
        }
        return closestSum;
    }
}
```
### Algorithm
- First, sort the input array `nums`.
- Initialize a variable `closestSum` with the sum of the first three elements.
- Iterate through the array with a for loop, fixing one element `nums[i]` at a time.
- For each `nums[i]`, use two pointers, `left` starting at `i + 1` and `right` starting at the end of the array (`n - 1`).
- While `left` is less than `right`, calculate the `currentSum = nums[i] + nums[left] + nums[right]`.
- If `currentSum` is exactly equal to `target`, return `target` immediately.
- Compare the absolute difference `|target - currentSum|` with `|target - closestSum|`. If the current sum is closer, update `closestSum`.
- If `currentSum` is less than `target`, increment `left` to get a larger sum.
- If `currentSum` is greater than `target`, decrement `right` to get a smaller sum.
- After the loops complete, return `closestSum`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int ThreeSumClosest(int[] nums, int target) {
        Array.Sort(nums);
        int ans = 1 << 30;
        int n = nums.Length;
        for (int i = 0; i < n; ++i) {
            int j = i + 1, k = n - 1;
            while (j < k) {
                int t = nums[i] + nums[j] + nums[k];
                if (t == target) {
                    return t;
                }
                if (Math.Abs(t - target) < Math.Abs(ans - target)) {
                    ans = t;
                }
                if (t > target) {
                    --k;
                } else {
                    ++j;
                }
            }
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
public
  int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);
    int ans = 1 << 30;
    int n = nums.length;
    for (int i = 0; i < n; ++i) {
      int j = i + 1, k = n - 1;
      while (j < k) {
        int t = nums[i] + nums[j] + nums[k];
        if (t == target) {
          return t;
        }
        if (Math.abs(t - target) < Math.abs(ans - target)) {
          ans = t;
        }
        if (t > target) {
          --k;
        } else {
          ++j;
        }
      }
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @param {number} target * @return {number} */ var threeSumClosest =
  function (nums, target) {
    nums.sort((a, b) => a - b);
    let ans = 1 << 30;
    const n = nums.length;
    for (let i = 0; i < n; ++i) {
      let j = i + 1;
      let k = n - 1;
      while (j < k) {
        const t = nums[i] + nums[j] + nums[k];
        if (t === target) {
          return t;
        }
        if (Math.abs(t - target) < Math.abs(ans - target)) {
          ans = t;
        }
        if (t > target) {
          --k;
        } else {
          ++j;
        }
      }
    }
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  int threeSumClosest(vector<int> &nums, int target) {
    sort(nums.begin(), nums.end());
    int ans = 1 << 30;
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
      int j = i + 1, k = n - 1;
      while (j < k) {
        int t = nums[i] + nums[j] + nums[k];
        if (t == target)
          return t;
        if (abs(t - target) < abs(ans - target))
          ans = t;
        if (t > target)
          --k;
        else
          ++j;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int: nums . sort() n = len(nums) ans = inf for i, v in enumerate(nums): j, k = i + 1, n - 1 while j < k: t = v + nums[j] + nums[k] if t == target: return t if abs(t - target) < abs(ans - target): ans = t if t > target: k -= 1 else: j += 1 return ans

```