Brute Force complexity?

Time: O(n^3) where n is the length of the input array. We have three nested loops, each iterating up to n times in the worst case.; Space: O(1) as we only use a constant amount of extra space for variables regardless of the input size.. This approach is straightforward but inefficient for large inputs due to its cubic time complexity. It's suitable for small arrays or as a baseline for understanding the problem.

Two Pointer Approach complexity?

Time: O(n^2) where n is the length of the input array. The sorting takes O(n log n), and the main loop with two pointers takes O(n^2). Since O(n^2) dominates O(n log n), the overall complexity is O(n^2).; Space: O(1) if we don't count the space used by sorting (which is O(log n) in most implementations). We only use a constant amount of extra space for variables regardless of the input size.. This approach is significantly more efficient than the brute force method for large inputs. It leverages the sorted array property and two-pointer technique to reduce the search space effectively. The key insight is that by fixing one element and using two pointers for the other two elements, we can navigate toward the target more intelligently than checking all combinations.

Binary Search Approach complexity?

Time: O(n^2 log n) where n is the length of the input array. The sorting takes O(n log n). The nested loops run O(n^2) times, and each binary search operation takes O(log n), resulting in O(n^2 log n) overall.; Space: O(1) if we don't count the space used by sorting. We only use a constant amount of extra space for variables regardless of the input size.. This approach is conceptually interesting but not as efficient as the two-pointer approach for this specific problem. While it demonstrates a creative use of binary search, the overhead of performing binary search for each pair makes it slower than the two-pointer technique. It might be more useful in scenarios where you need to find multiple closest sums or when the array is very large but already sorted.

3Sum Closest | N3mo LC

Difficulty: Medium | Acceptance: 47.17% | Paid: No

Topics: Array, Two Pointers, Sorting

Examples
Constraints
Brute Force
Two Pointer Approach
Binary Search Approach

Examples

Input

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

Output

Explanation

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Input

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

Output

Explanation

The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

Constraints

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

Brute Force

Intuition

Check all possible triplets in the array to find the one whose sum is closest to the target. Since we need three numbers, we can iterate through all combinations using three nested loops.

Steps

We will use three nested loops to generate all possible triplets from the array.
For each triplet, compute the sum and compare it with the target to determine how close it is.
Keep track of the closest sum encountered so far by comparing the absolute differences between the sums and the target.

python

def threeSumClosest(nums, target):
    closest_sum = float('inf')
    min_diff = float('inf')
    n = len(nums)
    
    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]
                diff = abs(current_sum - target)
                if diff &lt; min_diff:
                    min_diff = diff
                    closest_sum = current_sum
    return closest_sum

Complexity

Time: O(n^3) where n is the length of the input array. We have three nested loops, each iterating up to n times in the worst case.
Space: O(1) as we only use a constant amount of extra space for variables regardless of the input size.
Notes: This approach is straightforward but inefficient for large inputs due to its cubic time complexity. It’s suitable for small arrays or as a baseline for understanding the problem.

Two Pointer Approach

Intuition

After sorting the array, we can fix one element and use the two-pointer technique to find the other two elements efficiently. This reduces the problem from three dimensions to two dimensions for the inner search.

Steps

Sort the input array to enable the two-pointer technique.
Iterate through the array, fixing one element at a time as the first element of the triplet.
For each fixed element, use two pointers (left and right) to find the other two elements such that their sum is closest to the target.
Adjust the pointers based on whether the current sum is less than or greater than the target, moving toward a potentially better solution.
Keep track of the closest sum encountered throughout the process.

python

def threeSumClosest(nums, target):
    nums.sort()
    n = len(nums)
    closest_sum = nums[0] + nums[1] + nums[2]
    
    for i in range(n - 2):
        left, right = i + 1, n - 1
        
        while left &lt; right:
            current_sum = nums[i] + nums[left] + nums[right]
            
            if current_sum == target:
                return current_sum
            
            if abs(current_sum - target) &lt; abs(closest_sum - target):
                closest_sum = current_sum
            
            if current_sum &lt; target:
                left += 1
            else:
                right -= 1
    
    return closest_sum

Complexity

Time: O(n^2) where n is the length of the input array. The sorting takes O(n log n), and the main loop with two pointers takes O(n^2). Since O(n^2) dominates O(n log n), the overall complexity is O(n^2).
Space: O(1) if we don’t count the space used by sorting (which is O(log n) in most implementations). We only use a constant amount of extra space for variables regardless of the input size.
Notes: This approach is significantly more efficient than the brute force method for large inputs. It leverages the sorted array property and two-pointer technique to reduce the search space effectively. The key insight is that by fixing one element and using two pointers for the other two elements, we can navigate toward the target more intelligently than checking all combinations.

Binary Search Approach

Intuition

After sorting the array, we can fix two elements and use binary search to find the third element that makes the sum closest to the target. This can be more efficient than the two-pointer approach in some cases.

Steps

Sort the input array to enable binary search.
Iterate through the array with two nested loops to fix two elements of the triplet.
For each pair of fixed elements, calculate the required third element value to reach the target.
Use binary search to find the closest value to this required element in the remaining part of the array.
Calculate all possible sums with the two fixed elements and the closest elements found via binary search.
Keep track of the overall closest sum as we progress through all combinations.

python

def threeSumClosest(nums, target):
    nums.sort()
    n = len(nums)
    closest_sum = nums[0] + nums[1] + nums[2]
    
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            required = target - nums[i] - nums[j]
            
            # Binary search for the closest element
            left, right = j + 1, n - 1
            while left &lt; right:
                mid = (left + right) // 2
                if nums[mid] &lt; required:
                    left = mid + 1
                else:
                    right = mid
            
            # Check the element at left and its predecessor if exists
            for k in [left - 1, left]:
                if j &lt; k &lt; n:
                    current_sum = nums[i] + nums[j] + nums[k]
                    if abs(current_sum - target) &lt; abs(closest_sum - target):
                        closest_sum = current_sum
    
    return closest_sum

Complexity

Time: O(n^2 log n) where n is the length of the input array. The sorting takes O(n log n). The nested loops run O(n^2) times, and each binary search operation takes O(log n), resulting in O(n^2 log n) overall.
Space: O(1) if we don’t count the space used by sorting. We only use a constant amount of extra space for variables regardless of the input size.
Notes: This approach is conceptually interesting but not as efficient as the two-pointer approach for this specific problem. While it demonstrates a creative use of binary search, the overhead of performing binary search for each pair makes it slower than the two-pointer technique. It might be more useful in scenarios where you need to find multiple closest sums or when the array is very large but already sorted.