Three Sum Closest

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:

1. 3 <= nums.length <= 500
2. -1000 <= nums[i] <= 1000
3. -10^4 <= target <= 10^4

Solve this coding problem efficiently. Provide both a naive and an optimal solution, analyze the time and space complexity of each, and discuss potential edge cases.

## Approach

This problem can be solved using a two-pointer approach after sorting the input array. The idea is to iterate through the array, and for each element, use two pointers to find the other two elements that make the sum closest to the target.

### Naive Solution

A brute-force solution would involve three nested loops to iterate through all possible triplets and find the sum closest to the target. This approach has a time complexity of O(n^3), which is not efficient.

```python
def threeSumClosest_naive(nums, target):
    n = len(nums)
    closest_sum = float('inf')
    min_diff = float('inf')

    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            for k in range(j + 1, n):
                current_sum = nums[i] + nums[j] + nums[k]
                current_diff = abs(current_sum - target)

                if current_diff < min_diff:
                    min_diff = current_diff
                    closest_sum = current_sum

    return closest_sum

Optimal Solution

The optimal solution involves sorting the array first, then using a two-pointer approach. This reduces the time complexity to O(n^2).

def threeSumClosest(nums, target):
    nums.sort()
    n = len(nums)
    closest_sum = float('inf')
    min_diff = float('inf')

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

        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            current_diff = abs(current_sum - target)

            if current_diff < min_diff:
                min_diff = current_diff
                closest_sum = current_sum

            if current_sum < target:
                left += 1
            elif current_sum > target:
                right -= 1
            else:
                return target  # Exact match found

    return closest_sum

Big(O) Run-time Analysis

Optimal Solution

1. Sorting the array: O(n log n)
2. Outer loop: O(n)
3. Inner while loop: O(n)

Therefore, the overall time complexity is O(n log n + n^2), which simplifies to O(n^2) because the n^2 term dominates.

Naive Solution

The naive solution has three nested loops, each iterating up to n times, resulting in a time complexity of O(n^3).

Big(O) Space Usage Analysis

Optimal Solution

The space complexity of the optimal solution is O(1) if we don't consider the space used for sorting. Some sorting algorithms like quicksort might take O(log n) space in the average case, but merge sort can take O(n) space. Assuming an in-place sorting algorithm is used, the space complexity remains O(1) as we only use a few extra variables.

Naive Solution

The space complexity of the naive solution is O(1) because it only uses a few extra variables and does not depend on the input size.

Edge Cases

1. Empty array: If the input array has fewer than 3 elements, the problem statement specifies that each input would have exactly one solution, so it won't occur.
2. Array with duplicate numbers: The algorithm works correctly even with duplicate numbers because it considers all possible triplets.
3. Target is very large or very small: The closest_sum is initialized to float('inf'), which handles cases where the target is significantly larger or smaller than any possible sum.
4. Exact match: If an exact match to the target is found during the two-pointer traversal, the function immediately returns the target value.