3Sum Closest medium

Problem Statement

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 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 the two-pointer technique.
2. Iterate through the array: The outer loop iterates through each number in the array. This number will be one of the three numbers in our sum.
3. Two-pointer approach: For each number from the outer loop, we use two pointers, left and right, to point to the beginning and end of the remaining unsorted portion of the array.
4. Calculate the sum: We calculate the sum of the three numbers (the number from the outer loop and the numbers pointed to by left and right).
5. Compare with the closest sum: We keep track of the closest sum found so far and update it if a closer sum is found.
6. Adjust pointers: If the sum is less than the target, we move the left pointer to the right to increase the sum. If the sum is greater than the target, we move the right pointer to the left to decrease the sum.
7. Return the closest sum: After iterating through all possible combinations, we return the closest sum found.

Explanation

The algorithm's efficiency comes from the sorting and two-pointer technique. Sorting allows us to efficiently find combinations that are close to the target. The two-pointer approach avoids redundant calculations by systematically exploring all possible pairs for a given number from the outer loop. The algorithm ensures that it considers every possible triplet while minimizing the number of calculations.

Code

function threeSumClosest(nums: number[], target: number): number {
    //Sort the array
    nums.sort((a, b) => a - b);
    let closestSum = Infinity; // Initialize with a large value

    for (let i = 0; i < nums.length - 2; i++) {
        let left = i + 1;
        let right = nums.length - 1;

        while (left < right) {
            const currentSum = nums[i] + nums[left] + nums[right];
            //Check if the current sum is closer to the target than the closest sum so far
            if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
                closestSum = currentSum;
            }

            if (currentSum < target) {
                left++; // Move left pointer to increase the sum
            } else if (currentSum > target) {
                right--; // Move right pointer to decrease the sum
            } else {
                return target; // Exact match found
            }
        }
    }
    return closestSum;
}

Complexity

• Time Complexity: O(n^2), where n is the length of the input array. This is dominated by the nested loops (outer loop iterates n-2 times, inner loop iterates at most n times in the worst case). The sorting step takes O(n log n), but this is dominated by the nested loops.

• Space Complexity: O(log n) in the best and average case due to the space used by the sorting algorithm. In the worst-case scenario (e.g., using a quicksort implementation that requires additional space for recursion), it could be O(n). However, the in-place sorting algorithms typically used in JavaScript's sort method will generally result in O(log n) space complexity.