Solution For 3sum Closest

Problem Description:

Given an array nums of n integers 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:

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).

Solution:

To solve this problem, we can use the two-pointer approach. First, we sort the given input array. This allows us to easily traverse through all the possible values of the three numbers. We then fix the first number and move the second and third numbers such that we calculate their sum and check if it is closest to the target. We then update the closest sum so far and move the second and third numbers accordingly. We keep doing this until we have checked all possible combinations of the three numbers.

Algorithm:

1. Sort the given input array nums.
2. Initialize a variable res to store the closest sum so far. Set it to a large number initially.
3. Traverse through the array nums from left to right. Fix the first number as the i-th number.
4. Initialize two pointers, left and right. Set left to i+1 and right to n-1.
5. While left < right, calculate the sum of the three numbers, i.e., nums[i] + nums[left] + nums[right].
6. If the sum is equal to target, return the sum.
7. If the sum is less than target, increment left.
8. If the sum is greater than target, decrement right.
9. Check if the absolute difference between the sum and target is less than the absolute difference between res and target.
10. If yes, update res with the new sum.
11. Repeat steps 5-10 until all possible combinations of the three numbers have been checked.
12. Return res.

Implementation:

Here is the Python code to implement the above algorithm:

def threeSumClosest(nums: List[int], target: int) -> int:
nums.sort()
n = len(nums)
res = float(‘inf’)
for i in range(n-2):
left = i+1
right = n-1
while left < right:
total = nums[i] + nums[left] + nums[right] if total == target:
return total
elif total < target:
left += 1
else:
right -= 1
if abs(total – target) < abs(res – target):
res = total
return res

Time Complexity:

The time complexity of the above algorithm is O(n^2), where n is the length of the input array. This is because we traverse through the array twice, once to sort the array, and then to find the closest sum. Within the second traversal, we use a two-pointer approach, which takes O(n) time.

Space Complexity:

The space complexity of the above algorithm is O(1), as we are not using any extra space. We are only using a few variables to store the closest sum, pointers, and the input array.

Step by Step Implementation For 3sum Closest

class Solution { 
    public int threeSumClosest(int[] nums, int target) {
        // sort the array first
        Arrays.sort(nums);
        int closestSum = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.length - 2; i++) {
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                // update closestSum if the current sum is closer to target
                if (Math.abs(target - sum) < Math.abs(target - closestSum)) {
                    closestSum = sum;
                }
                // move left or right pointer based on current sum
                if (sum < target) {
                    left++;
                } else if (sum > target) {
                    right--;
                } else {
                    // we found an exact match, no need to continue
                    return sum;
                }
            }
        }
        return closestSum;
    }
}

class Solution:
  def threeSumClosest(self, nums, target):
    # Sort the array
    nums.sort()
    # Set the closest variable to the max value of an integer
    closest = 2147483647
    # Iterate through the array
    for i in range(len(nums) - 2):
      # Set left pointer to i + 1
      left = i + 1
      # Set right pointer to the end of the array
      right = len(nums) - 1
      # While the left pointer is less than the right pointer
      while left < right:
        # Set the sum to be the values of nums at indices i, left, and right
        sum = nums[i] + nums[left] + nums[right]
        # If the sum is equal to the target
        if sum == target:
          # Return the sum
          return sum
        # If the sum is less than the target
        if sum < target:
          # If the sum is closer to the target than the current value of closest
          if target - sum < abs(target - closest):
            # Set closest equal to the sum
            closest = sum
          # Increment the left pointer
          left += 1
        # If the sum is greater than the target
        else:
          # If the sum is closer to the target than the current value of closest
          if sum - target < abs(target - closest):
            # Set closest equal to the sum
            closest = sum
          # Decrement the right pointer
          right -= 1
    # Return the closest value
    return closest

var threeSumClosest = function(nums, target) {
    // sort the array
    nums.sort((a, b) => a - b);
    // initialize the closest value to be the first sum in the array
    let closest = nums[0] + nums[1] + nums[2];
    // iterate through the array
    for (let i = 0; i < nums.length - 2; i++) {
        // initialize left pointer at i + 1
        let left = i + 1;
        // initialize right pointer at end of array
        let right = nums.length - 1;
        // while the left pointer is less than the right pointer
        while (left < right) {
            // calculate the sum
            let sum = nums[i] + nums[left] + nums[right];
            // if the sum is equal to the target, return the sum
            if (sum === target) {
                return sum;
            // if the sum is less than the target, move the left pointer up one
            } else if (sum < target) {
                left++;
            // if the sum is greater than the target, move the right pointer down one    
            } else {
                right--;
            }
            // if the absolute value of the sum minus the target is less than the absolute value of the closest value minus the target
            if (Math.abs(sum - target) < Math.abs(closest - target)) {
                // set the closest value to the sum
                closest = sum;
            }
        }
    }
    // return the closest value
    return closest;
};

class Solution {
public:
    int threeSumClosest(vector& nums, int target) {
        int result = nums[0] + nums[1] + nums[2];
        int min_diff = abs(result - target);
        // sort the array
        sort(nums.begin(), nums.end());
        // fix the smallest number as nums[i]
        for (int i = 0; i < nums.size() - 2; i++) {
            // start from i + 1
            int left = i + 1;
            // end at nums.size() - 1
            int right = nums.size() - 1;
            // until left meets right
            while (left < right) {
                // calculate the sum
                int sum = nums[i] + nums[left] + nums[right];
                // update the result if it's closer to the target
                if (abs(sum - target) < min_diff) {
                    result = sum;
                    min_diff = abs(sum - target);
                }
                // if the sum is too small, move left
                if (sum < target) {
                    left++;
                }
                // if the sum is too large, move right
                else {
                    right--;
                }
            }
        }
        return result;
    }
};

public class Solution {
    public int ThreeSumClosest(int[] nums, int target) {
        Array.Sort(nums);
        int closestSum = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.Length - 2; i++)
        {
            int left = i + 1;
            int right = nums.Length - 1;
            while (left < right)
            {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == target)
                {
                    //We found an exact match, return the sum
                    return sum;
                }
                else if (sum < target)
                {
                    //The sum is too low, increment the left pointer
                    left++;
                }
                else
                {
                    //The sum is too high, decrement the right pointer
                    right--;
                }
                //Update closestSum if the current sum is closer to the target
                if (Math.Abs(sum - target) < Math.Abs(closestSum - target))
                {
                    closestSum = sum;
                }
            }
        }
        return closestSum;
    }
}