3Sum Closest medium

Problem Statement

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

Steps

1. Sort the array: Sorting the array allows us to use a two-pointer approach efficiently.
2. Iterate through the array: We iterate through the array using a single pointer i. For each element at index i, we consider it as one of the three numbers in the sum.
3. Two-pointer approach: For each i, we use two pointers, left and right, to scan the remaining array. left starts at i + 1 and right starts at n - 1.
4. Calculate the sum: We calculate the sum currentSum = nums[i] + nums[left] + nums[right].
5. Compare with the target and update the closest sum: We compare the absolute difference between currentSum and target with the absolute difference between the current closest sum (closestSum) and target. We update closestSum if we find a closer sum.
6. Adjust pointers: If currentSum is less than target, we increment left to increase the sum. If currentSum is greater than target, we decrement right to decrease the sum.
7. Return the closest sum: After iterating through all possible triplets, we return the closestSum.

Explanation

The algorithm leverages the fact that after sorting the array, we can efficiently search for triplets whose sum is close to the target using a two-pointer technique. By moving the left and right pointers, we systematically explore all possible combinations involving the element at index i. The use of absolute difference ensures that we are always tracking the sum that is closest to the target, regardless of whether the sum is greater or less than the target.

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits> // Required for numeric_limits

using namespace std;

int threeSumClosest(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    int closestSum = numeric_limits<int>::max(); // Initialize with the largest possible integer
    int minDiff = numeric_limits<int>::max(); //Initialize with the largest possible integer


    for (int i = 0; i < n - 2; ++i) {
        int left = i + 1;
        int right = n - 1;
        while (left < right) {
            int currentSum = nums[i] + nums[left] + nums[right];
            int diff = abs(currentSum - target);

            if (diff < minDiff) {
                minDiff = diff;
                closestSum = currentSum;
            }

            if (currentSum < target) {
                left++;
            } else if (currentSum > target) {
                right--;
            } else {
                return target; // Exact match found
            }
        }
    }
    return closestSum;
}

int main() {
    vector<int> nums1 = {-1, 2, 1, -4};
    int target1 = 1;
    cout << "Example 1: " << threeSumClosest(nums1, target1) << endl; // Output: 2

    vector<int> nums2 = {0, 0, 0};
    int target2 = 1;
    cout << "Example 2: " << threeSumClosest(nums2, target2) << endl; // Output: 0

    return 0;
}

Complexity

• Time Complexity: O(n^2), dominated by the nested loops. Sorting the array takes O(n log n), but this is less significant than the nested loops.
• Space Complexity: O(log n) in the best and average case for sorting (due to recursion in quicksort or mergesort), O(n) in the worst case (for sorting). If we consider in-place sorting algorithms (like heapsort), space complexity becomes O(1). The additional space used by the variables is constant, O(1).