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 the first of our three numbers.
3. Two-pointer approach: For each number in the outer loop, use two pointers, left and right, to find the remaining two numbers. left starts at the index after the outer loop's current index, and right starts at the end of the array.
4. Calculate the sum: Calculate the sum of the three numbers (the number from the outer loop and the numbers at left and right).
5. Compare with the closest sum: Keep track of the closest sum found so far. If the absolute difference between the current sum and the target is less than the absolute difference between the closest sum and the target, update the closest sum.
6. Adjust pointers: If the current sum is less than the target, move left to the right. If the current sum is greater than the target, move right to the left.
7. Repeat: Repeat steps 4-6 until left and right cross.
8. Return the closest sum: After iterating through all numbers, return the closest sum found.

Explanation:

The algorithm's efficiency comes from the sorting and the two-pointer technique. Sorting allows us to efficiently move the left and right pointers to search for the closest sum. The two-pointer approach avoids nested loops, reducing the time complexity from O(n³) to O(n²). We use the absolute difference to ensure we find the closest sum regardless of whether the sum is greater or less than the target.

Code:

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int ThreeSumClosest(int[] nums, int target) {
        Array.Sort(nums); // Sort the array
        int closestSum = nums[0] + nums[1] + nums[2]; // Initialize closestSum

        for (int i = 0; i < nums.Length - 2; i++) {
            int left = i + 1;
            int right = nums.Length - 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²), 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 less significant than the nested loops.
• Space Complexity: O(log n) in the best and average cases (due to recursive calls in quicksort, which is often used for array sorting), and O(n) in the worst case (if the sorting algorithm uses additional space). This can be considered O(1) if we ignore the space used by the sorting algorithm because it is dominated by the size of the input array.