16. 3Sum Closest

Time: O(n²)

Space: O(1)

Intuition

Sort the array, then for each fixed element i use two pointers on the remainder. The sorted order lets you deterministically move closer to the target: if the current sum is too small, advance left; if too large, retreat right. Update the closest sum whenever you find a smaller gap.

Algorithm

1Sort nums.
2Initialise closest = nums[0]+nums[1]+nums[2].
3For i from 0 to n-3: set left=i+1, right=n-1.
4While left < right: compute sum = nums[i]+nums[left]+nums[right]. If |sum-target| < |closest-target|, update closest.
5If sum < target -> left++. If sum > target -> right--. If sum == target -> return target.
6Return closest.

Example Walkthrough

Input: nums = [-1,2,1,-4], target = 1 -> sorted: [-4,-1,1,2]

1.i=0(-4): left=1(-1),right=3(2). sum=-3. |diff|=4. sum<target->left++.
2.left=2(1),right=3(2). sum=-1. |diff|=2. sum<target->left++. Loop ends.
3.i=1(-1): left=2(1),right=3(2). sum=2. |diff|=1. sum>target->right--. Loop ends.
4.Closest=2.

Output: 2

Common Pitfalls

•Early return when sum == target since you cannot get closer than 0.

16.cs

// Approach: Sort the array, then use two pointers tracking the closest three-sum,
// updating the result whenever the absolute difference shrinks.
// Time: O(n²) Space: O(1)

public class Solution
{
    public int ThreeSumClosest(int[] nums, int target)
    {
        int j = 0, n = nums.Length;
        int k = 0;
        int result = 0;
        int minDiff = Int32.MaxValue;
        Array.Sort(nums);
        for (int i = 0; i < n - 2; i++)
        {
            j = i + 1;
            k = n - 1;
            while (j < k)
            {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum < target)
                    j++;
                else if (sum > target)
                    k--;
                else if (sum == target)
                {
                    return sum;
                }
                int diff = Math.Abs(sum - target);
                if (diff < minDiff)
                {
                    minDiff = diff;
                    result = sum;
                }
            }
        }

        return result;
    }
}

Was this solution helpful?