Problem Summary

You are given an integer array nums and an integer target.
Your task is to find three distinct integers in the array such that their sum is closest to target.
Return that sum.

There is guaranteed to be exactly one solution.

Example
Input: nums = [-1, 2, 1, -4], target = 1
Output: 2
Explanation: The closest sum is 2 from (-1 + 2 + 1).

Constraints

• Array length is at least 3.
• Values may be negative, zero, or positive.
• The expected time complexity is O(n²).

---

Approach

The classic way to solve this is to use the two-pointer technique, similar to the 3Sum problem.

Key observations

1. If we sort the array, we can fix one number and then move two pointers to search for the best sum.
2. Sorting lets us:
   • move the left pointer right to increase the sum,
   • move the right pointer left to decrease the sum.
3. Keep track of the closest sum found so far by comparing absolute differences.

Why this works

Sorting puts the numbers in increasing order.
That means when you fix one index i, you can control the total sum by adjusting the other two pointers deterministically.

This avoids checking all O(n³) combinations.
Instead, for each i you only do one O(n) pass with two pointers, giving O(n²) total time.

Step-by-step logic

1. Sort the array.
2. Initialize closestSum as the sum of the first three elements.
3. Loop i from 0 to n – 3:
   • Set left = i + 1 and right = n - 1.
   • While left < right:
     • Compute sum = nums[i] + nums[left] + nums[right].
     • If this sum is closer to target, update closestSum.
     • If sum < target, move left pointer.
     • If sum > target, move right pointer.
     • If sum == target, return sum immediately.
4. Return closestSum.

---

Java Code (Optimal O(n²) Solution)

import java.util.Arrays;

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;

        int closest = nums[0] + nums[1] + nums[2];

        for (int i = 0; i < n - 2; i++) {

            int left = i + 1;
            int right = n - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (Math.abs(sum - target) < Math.abs(closest - target)) {
                    closest = sum;
                }

                if (sum < target) {
                    left++;
                } else if (sum > target) {
                    right--;
                } else {
                    return sum;   // exact match; cannot get closer
                }
            }
        }

        return closest;
    }
}

---

Dry Run (Step-by-Step)

Input
nums = [-1, 2, 1, -4], target = 1

Step 1: Sort

nums = [-4, -1, 1, 2]

Step 2: Initialize

closest = -4 + -1 + 1 = -4

i = 0 (nums[i] = -4)

left = 1 (value -1), right = 3 (value 2)

1. sum = -4 + -1 + 2 = -3
   Closer to target than -4 → update closest = -3
   sum < target → left++ → left = 2
2. sum = -4 + 1 + 2 = -1
   |-1 – 1| = 2, closer than |-3 – 1| = 4 → update closest = -1
   sum < target → left = 3 → stop

i = 1 (nums[i] = -1)

left = 2, right = 3

1. sum = -1 + 1 + 2 = 2
   |2 – 1| = 1, closer than |-1 – 1| = 2 → update closest = 2
   sum > target → right–

right becomes 2 → pointers meet → stop.

Loop ends.

Final answer: 2

---

Complexity Analysis

Time Complexity:
O(n²) — sorting plus two-pointer scanning for each element.

Space Complexity:
O(1) extra space (not counting sorting).

---

Edge Cases

• All numbers are large → method still works.
• All numbers negative or all positive → two-pointer logic still applies.
• Sorted or unsorted input array → algorithm sorts first.