28. 3Sum Closest

🔗 LeetCode Problem: 16. 3Sum Closest
📊 Difficulty: Medium
🏷️ Topics: Array, Two Pointers, Sorting

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
Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

Constraints: - 3 <= nums.length <= 500 - -1000 <= nums[i] <= 1000 - -10^4 <= target <= 10^4

---

🎨 Visual Understanding

The Problem Visualized

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

All possible triplet sums:
[-1, 2, 1]   → -1 + 2 + 1 = 2    Distance from target: |2 - 1| = 1 ✓
[-1, 2, -4]  → -1 + 2 - 4 = -3   Distance from target: |-3 - 1| = 4
[-1, 1, -4]  → -1 + 1 - 4 = -4   Distance from target: |-4 - 1| = 5
[2, 1, -4]   → 2 + 1 - 4 = -1    Distance from target: |-1 - 1| = 2

Closest sum to target = 2
Answer: 2

Key Difference from 3Sum

3Sum Problem:
Find triplets that sum to EXACTLY 0
Return: All unique triplets
Example: [[-1, 0, 1], [-1, -1, 2]]

3Sum Closest:
Find ONE triplet sum CLOSEST to target
Return: Single sum value (not triplet itself)
Example: 2

Measuring "Closest"

Target = 1

Sum = 2  → Distance = |2 - 1| = 1
Sum = -1 → Distance = |-1 - 1| = 2
Sum = 5  → Distance = |5 - 1| = 4

Closest sum = 2 (smallest distance)

---

🎯 Approach 1: Brute Force

The Most Natural Thinking 💭

Core Logic:

Try all possible triplet combinations:
1. Use three nested loops
2. Calculate sum for each triplet
3. Track sum closest to target
4. Return closest sum

Why This Works: - Checks all possible triplets - Guaranteed to find closest sum - Simple to understand

Why This Fails Requirements: - Time complexity O(n³) - Too slow for larger arrays - Not optimal for interviews

Implementation

public int threeSumClosest(int[] nums, int target) {
    int n = nums.length;
    int closestSum = nums[0] + nums[1] + nums[2];

    // Try all possible triplets
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                int sum = nums[i] + nums[j] + nums[k];

                // Update if this sum is closer to target
                if (Math.abs(sum - target) < Math.abs(closestSum - target)) {
                    closestSum = sum;
                }
            }
        }
    }

    return closestSum;
}

⏰ Time: O(n³) - three nested loops
💾 Space: O(1) - only storing closestSum

---

✅ Approach 2: Sort + Two Pointers (Optimal)

The Breakthrough Insight 💡

Core Logic:

Similar to 3Sum, but track closest sum instead of exact match:

1. SORT the array first
2. FIX one number (outer loop)
3. Use TWO POINTERS to find best pair
4. Track sum closest to target
5. Early exit if exact match found

Key difference from 3Sum:
- Don't need to find ALL triplets
- Don't need to avoid duplicates
- Stop if we find exact target sum

Visual Explanation:

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

i=0: Fix -4
     [-4, -1, 1, 2]
       i   L     R

     sum = -4 + (-1) + 2 = -3
     distance = |-3 - 1| = 4
     closestSum = -3

     -3 < 1 → need larger sum → L++

     sum = -4 + 1 + 2 = -1
     distance = |-1 - 1| = 2
     closestSum = -1 (better!)

i=1: Fix -1
     [-4, -1, 1, 2]
           i  L  R

     sum = -1 + 1 + 2 = 2
     distance = |2 - 1| = 1
     closestSum = 2 (better!)

     2 > 1 → need smaller sum → R--

     sum = -1 + 1 + 1 = 1
     EXACT MATCH! Return immediately

Decision Rules:

If current sum < target:
  → Sum too small, need larger → move left++

If current sum > target:
  → Sum too large, need smaller → move right--

If current sum == target:
  → Perfect match! Return immediately

Implementation

public int threeSumClosest(int[] nums, int target) {
    // Step 1: Sort the array
    Arrays.sort(nums);

    int n = nums.length;
    int closestSum = nums[0] + nums[1] + nums[2];

    // Step 2: Fix first number, use two pointers for rest
    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];

            // Update closest sum if current is closer
            if (Math.abs(sum - target) < Math.abs(closestSum - target)) {
                closestSum = sum;
            }

            // Early exit if exact match
            if (sum == target) {
                return target;
            }

            // Move pointers based on comparison
            if (sum < target) {
                left++;   // Need larger sum
            } else {
                right--;  // Need smaller sum
            }
        }
    }

    return closestSum;
}

⏰ Time: O(n²) - O(n log n) for sorting + O(n²) for nested loops
💾 Space: O(1) - excluding sorting space

---

🔍 Step-by-Step Execution

Example: nums = [-1, 2, 1, -4], target = 1

Step 0: Sort the array
═══════════════════════════════════════════════════════════════════
Original: [-1, 2, 1, -4]
Sorted:   [-4, -1, 1, 2]

Initialize: closestSum = -4 + (-1) + 1 = -4


Iteration i=0: nums[i] = -4
═══════════════════════════════════════════════════════════════════
Fixed number: -4
left = 1, right = 3

Loop iteration 1:
  sum = -4 + (-1) + 2 = -3
  distance = |-3 - 1| = 4
  closestSum distance = |-4 - 1| = 5

  |-3 - 1| < |-4 - 1| → Update closestSum = -3

  -3 < 1 → sum too small → left++

Loop iteration 2:
  left = 2, right = 3
  sum = -4 + 1 + 2 = -1
  distance = |-1 - 1| = 2
  closestSum distance = |-3 - 1| = 4

  |-1 - 1| < |-3 - 1| → Update closestSum = -1

  -1 < 1 → sum too small → left++

Loop iteration 3:
  left = 3, right = 3
  left >= right → STOP


Iteration i=1: nums[i] = -1
═══════════════════════════════════════════════════════════════════
Fixed number: -1
left = 2, right = 3

Loop iteration 1:
  sum = -1 + 1 + 2 = 2
  distance = |2 - 1| = 1
  closestSum distance = |-1 - 1| = 2

  |2 - 1| < |-1 - 1| → Update closestSum = 2 ✓

  2 > 1 → sum too large → right--

Loop iteration 2:
  left = 2, right = 2
  left >= right → STOP


Iteration i=2: Out of bounds (i < n - 2)
═══════════════════════════════════════════════════════════════════


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: 2
Distance from target: |2 - 1| = 1 (closest possible)
═══════════════════════════════════════════════════════════════════

Another Example: nums = [0, 0, 0], target = 1

Step 0: Sort
nums = [0, 0, 0]  (already sorted)

Initialize: closestSum = 0 + 0 + 0 = 0

Iteration i=0: nums[0] = 0
═══════════════════════════════════════════════════════════════════
Fixed: 0
left = 1, right = 2

sum = 0 + 0 + 0 = 0
distance = |0 - 1| = 1
closestSum distance = |0 - 1| = 1

Distance same, but let's continue...

0 < 1 → left++
left = 2, right = 2 → STOP

Result: 0

---

🔍 Edge Cases

Case 1: Target equals exact sum
Input: nums = [-1, 0, 1], target = 0
Output: 0
Explanation: -1 + 0 + 1 = 0 (exact match)

Case 2: All same numbers
Input: nums = [1, 1, 1], target = 3
Output: 3
Explanation: 1 + 1 + 1 = 3 (exact match)

Case 3: All same numbers, different target
Input: nums = [1, 1, 1], target = 0
Output: 3
Explanation: 1 + 1 + 1 = 3 (closest possible)

Case 4: Minimum array size
Input: nums = [0, 1, 2], target = 3
Output: 3
Explanation: 0 + 1 + 2 = 3 (exact match)

Case 5: Large positive numbers
Input: nums = [1, 2, 4, 8, 16, 32, 64, 128], target = 82
Output: 82
Explanation: 2 + 16 + 64 = 82 (exact match)

Case 6: Negative target
Input: nums = [-1, 2, 1, -4], target = -5
Output: -4
Explanation: -4 + (-1) + 1 = -4 (closest to -5)

Case 7: All negative numbers
Input: nums = [-5, -4, -3, -2, -1], target = -10
Output: -10
Explanation: -5 + -4 + -1 = -10 (exact match)

Case 8: Mix with zero
Input: nums = [-1, 0, 1, 2], target = 1
Output: 1
Explanation: Multiple ways: -1 + 0 + 2 = 1 or 0 + 1 + 0 (but only one zero)
Actually: -1 + 1 + 1 (but only one 1)
Let me recalculate: -1 + 0 + 2 = 1 ✓

---

Common Mistakes

Mistake 1: Not sorting the array
❌ Wrong: 
    public int threeSumClosest(int[] nums, int target) {
        // Missing: Arrays.sort(nums);
        ...
    }
✓ Right: 
    Arrays.sort(nums);
Reason: Need sorted array for two pointers technique

Mistake 2: Wrong initial closest sum
❌ Wrong: 
    int closestSum = Integer.MAX_VALUE;
✓ Right: 
    int closestSum = nums[0] + nums[1] + nums[2];
Reason: Need actual valid sum, not arbitrary large value

Mistake 3: Not using Math.abs for distance comparison
❌ Wrong: 
    if (sum - target < closestSum - target) {
        closestSum = sum;
    }
✓ Right: 
    if (Math.abs(sum - target) < Math.abs(closestSum - target)) {
        closestSum = sum;
    }
Reason: Distance must be absolute value (both positive and negative)

Mistake 4: Not returning early on exact match
❌ Wrong: 
    if (sum == target) {
        closestSum = sum;
        // Continue loop
    }
✓ Right: 
    if (sum == target) {
        return target;  // Early exit
    }
Reason: Can't get closer than exact match

Mistake 5: Wrong loop boundary
❌ Wrong: 
    for (int i = 0; i < n; i++) {
        ...
    }
✓ Right: 
    for (int i = 0; i < n - 2; i++) {
        ...
    }
Reason: Need room for two more elements

Mistake 6: Returning closestSum distance instead of sum
❌ Wrong: 
    return Math.abs(closestSum - target);
✓ Right: 
    return closestSum;
Reason: Problem asks for the SUM, not the distance

Mistake 7: Not moving pointers correctly
❌ Wrong: 
    if (sum < target) {
        right--;  // Wrong direction!
    }
✓ Right: 
    if (sum < target) {
        left++;   // Need larger sum
    } else {
        right--;  // Need smaller sum
    }
Reason: Move left for larger sum, right for smaller sum

---

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Brute Force
  Time: O(n³)
  Space: O(1)
  Use: Only for understanding, not for interviews

Approach 2: Sort + Two Pointers (RECOMMENDED)
  Time: O(n²)
  Space: O(1)
  Use: Optimal solution, best for interviews

🔑 The Core Insight

Similar to 3Sum, but with key differences:

Similarities:
1. Sort array first
2. Fix one number, use two pointers for rest
3. O(n²) time complexity

Differences:
1. Track CLOSEST sum, not exact matches
2. NO need to handle duplicates
3. Can return early on exact match
4. Return single SUM value, not list of triplets

Strategy:
- Fix i, use left and right pointers
- Track closest sum using Math.abs(sum - target)
- Move pointers: sum < target → left++, sum > target → right--
- Early exit: sum == target → return immediately

🎯 Pattern Recognition

Problem Type: Finding Optimal Triplet
Core Pattern: Sort + Two Pointers + Tracking Optimal

When to Apply:
✓ Need to find triplet with specific property
✓ Optimization problem (closest, largest, smallest)
✓ Array can be sorted
✓ Can use greedy pointer movement

Key Techniques:
→ Sort array first
→ Fix one element, two pointers for rest
→ Track optimal value during iteration
→ Early exit on perfect match
→ Use Math.abs for distance calculations

Related Problems:
- 3Sum (LC 15) - Find exact sum
- 4Sum (LC 18) - Find quadruplets
- 3Sum Smaller (LC 259) - Count triplets
- Two Sum (LC 1) - Foundation

🧠 Interview Strategy

Step 1: "Need triplet sum closest to target"
Step 2: "Similar to 3Sum with two pointers"
Step 3: "Track closest using absolute difference"
Step 4: "Can exit early if exact match found"
Step 5: "O(n²) time, O(1) space"

Key Points to Mention:
- Sort array first for two pointers
- Track closest sum, not all sums
- Early exit optimization
- No duplicate handling needed
- Distance measured with Math.abs

---

📝 Quick Revision Notes

🎯 Core Concept:

Similar to 3Sum but track the closest sum to target using absolute difference. Can exit early on exact match.

⚡ Quick Implementation:

public int threeSumClosest(int[] a, int target) {
    int len = a.length;
    int res = a[0] + a[1] + a[2]; // for now, initialize

    // // Approach 1 - brute force. Lets understand first.        
    // for(int i = 0; i < len - 2; i++) { // since 2 pointers, its len - 2
    //     for(int j = i + 1; j < len - 1; j++) {
    //         for(int k = j + 1; k < len; k++) {
    //             int sum = a[i] + a[j] + a[k];
    //             // closest of k1 or k2 to target is found by whichever of
    //             // |k1 - target| or |k2 - target| is smaller. If |k1 - target| is
    //             // smaller than |k2 - target|, k1 is close to target and is result.
    //             if(Math.abs(sum - target) < Math.abs(res - target)) {
    //                 res = sum;
    //             }
    //         }
    //     }
    // }

    // Approach 2 - sorting and 2 pointers (which deduces to 2 sum)
    Arrays.sort(a);
    for(int i = 0; i < len - 2; i++) {
        // skip duplicates - place 1
        if(i > 0 && a[i] == a[i - 1]) {
            continue;
        }

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

        while (left < right) {
            int sum = a[i] + a[left] + a[right];
            if(sum == target) {
                return sum;
            } else if (Math.abs(sum - target) < Math.abs(res - target)) {
                res = sum;
            }

            // decision on next move (left or right)
            if(sum < target) {
                left++; // normally move to get close to target
                // skip duplicates
                while (left < right && a[left] == a[left - 1]) {
                    left++;   
                }                    
            } else {
                right--; // normally move to get close to target
                // skip duplicates
                while(left < right && a[right] == a[right + 1]) {
                    right--;
                }
            }
        }
    }

    return res;
}

🔑 Key Insights:

• Sort first: Enable two pointers technique
• Initial closest: Use nums[0] + nums[1] + nums[2] (actual valid sum)
• Distance comparison: Use Math.abs(sum - target) for both directions
• Pointer movement: sum < target → left++, sum > target → right--
• Early exit: if (sum == target) return target; (can't get closer)
• Return value: Return the SUM itself, not the distance
• Time: O(n²), Space: O(1)
• No duplicate handling: Don't need to skip duplicates like 3Sum
• Loop boundary: i < n - 2 (need room for 3 elements)

🎪 Memory Aid:

"SORT, FIX one, TRACK closest, EXIT on exact!"
Think: "Like 3Sum but find CLOSEST, not ALL"

---

Related Patterns

• 3Sum (LC 15)
• Two Sum (LC 1)
• 4Sum (LC 18)
• 3Sum Smaller (LC 259)
• Two Sum II - Input Array Is Sorted (LC 167)

---

Happy practicing! 🎯