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 allows us to efficiently use a two-pointer approach.
2. Iterate through the array: The outer loop iterates through each element as a potential first element of the triplet.
3. Two-pointer approach: For each element, use two pointers (left and right) to find the remaining two elements in the sorted subarray.
4. Calculate the sum: Calculate the sum of the triplet (currentSum).
5. Update the closest sum: Compare the absolute difference between currentSum and target with the current minimum difference. If the new difference is smaller, update the closestSum.
6. Adjust pointers: If currentSum is less than target, move the left pointer to the right to increase the sum. If currentSum is greater than target, move the right pointer to the left to decrease the sum.
7. Return the closest sum: After iterating through all possible triplets, return the closestSum.

Explanation:

The algorithm leverages sorting to optimize the search for the triplet. By sorting the array, we can efficiently use a two-pointer technique to find pairs that complement the first element to get close to the target. The two pointers start at the beginning and end of the subarray, and we move them based on whether the current sum is less than or greater than the target, narrowing down the search space. The use of absolute difference ensures we are finding the closest sum, regardless of whether the sum is greater or less than the target.

Code:

import java.util.Arrays;

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums); // Sort the array
        int n = nums.length;
        int closestSum = nums[0] + nums[1] + nums[2]; // Initialize with the sum of the first three elements

        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];
                if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
                    closestSum = currentSum;
                }

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

Complexity:

• Time Complexity: O(n^2), dominated by the nested loops (outer loop iterates n-2 times, inner loop iterates at most n times). The sorting step takes O(n log n), but this is dominated by the nested loops.
• Space Complexity: O(log n) or O(1), depending on the sorting algorithm used. If merge sort or heap sort are used, the space complexity is O(log n). If an in-place sorting algorithm like quicksort is used, the space complexity can be O(1) in the average case. The extra space used for variables is constant.