Closest Three Sum

Given an array, arr of integers, and another number target, find three integers in the array such that their sum is closest to the target. Return the sum of the three integers.

Note: If there are multiple solutions, return the maximum one.

Examples :

Input: arr[] = [-7, 9, 8, 3, 1, 1], target = 2
Output: 2
Explanation: There is only one triplet present in the array where elements are -7,8,1 whose sum is 2.

Input: arr[] = [5, 2, 7, 5], target = 13
Output: 14
Explanation: There is one triplet with sum 12 and other with sum 14 in the array. Triplet elements are 5, 2, 5 and 2, 7, 5 respectively. Since abs(13-12) ==abs(13-14) maximum triplet sum will be preferred i.e 14.

Expected Time Complexity: O(n²)
Expected Auxiliary Space: O(1)

Constraints:
3 ≤ arr.size() ≤ 10³
-10⁵ ≤ arr[i] ≤ 10⁵
1 ≤ target ≤ 10⁵

Approach 01:

#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

class Solution {
public:
    int threeSumClosest(vector<int>& arr, int target) {
        sort(arr.begin(), arr.end());  // Sort the array
        
        int n = arr.size();  // Length of the array
        int min_abs_diff = INT_MAX;  // Initialize minimum absolute difference
        int closest_sum = 0;  // Variable to store the closest sum
        
        // Iterate through the array
        for (int i = n - 1; i >= 2; --i) {
            int left = 0;  // Initialize left pointer
            int right = i - 1;  // Initialize right pointer
            
            // Two-pointer technique
            while (left < right) {
                int current_sum = arr[i] + arr[left] + arr[right];  // Calculate current triplet sum
                int abs_diff = abs(current_sum - target);  // Calculate absolute difference
                
                // Update closest sum if current absolute difference is smaller
                if (abs_diff < min_abs_diff) {
                    min_abs_diff = abs_diff;
                    closest_sum = current_sum;
                }
                // If absolute difference is the same, update closest sum to maximum of current sum and closest sum
                else if (abs_diff == min_abs_diff) {
                    closest_sum = max(current_sum, closest_sum);
                }
                
                // Adjust pointers based on the sum comparison with target
                if (current_sum < target) {
                    ++left;
                } else {
                    --right;
                }
            }
        }
        
        return closest_sum;
    }
};

from typing import List

class Solution:
    def threeSumClosest(self, arr: List[int], target: int) -> int:
        arr.sort()  # Sort the array
        
        n = len(arr)  # Length of the array
        min_abs_diff = float('inf')  # Initialize minimum absolute difference
        closest_sum = 0  # Variable to store the closest sum
        
        # Iterate through the array
        for i in range(n - 2):
            left = i + 1  # Initialize left pointer
            right = n - 1  # Initialize right pointer
            
            # Two-pointer technique
            while left < right:
                current_sum = arr[i] + arr[left] + arr[right]  # Calculate current triplet sum
                abs_diff = abs(current_sum - target)  # Calculate absolute difference
                
                # Early termination if we find an exact match
                if abs_diff == 0:
                    return target
                
                # Update closest sum if current absolute difference is smaller
                if abs_diff < min_abs_diff:
                    min_abs_diff = abs_diff
                    closest_sum = current_sum
                # If absolute difference is the same, update closest sum to maximum of current sum and closest sum
                elif abs_diff == min_abs_diff:
                    closest_sum = max(current_sum, closest_sum)
                
                # Adjust pointers based on the sum comparison with target
                if current_sum < target:
                    left += 1
                else:
                    right -= 1
        
        return closest_sum

Time Complexity

• Sorting:

  Sorting the array takes \( O(n \log n) \) time, where \( n \) is the number of elements in the array.

• Two-pointer Technique:

  The two-pointer technique runs in \( O(n^2) \) time, where \( n \) is the number of elements in the array. This is because for each element in the array, we iterate through the remaining elements using two pointers.

• Overall Time Complexity:

  The overall time complexity is dominated by the sorting step, \( O(n \log n) \), as it is more significant than the \( O(n^2) \) complexity of the two-pointer technique.

Space Complexity

• Sorting:

  The sorting operation typically takes \( O(1) \) auxiliary space if an in-place sorting algorithm like Timsort is used, or \( O(n) \) space if extra space is needed.

• Additional Space:

  The additional space used by the algorithm is \( O(1) \) since we are only using a few extra variables to store indices and results, regardless of the input size.

• Overall Space Complexity:

  The overall space complexity is \( O(1) \), indicating constant space usage beyond the input array.