The O(n) Club: 3Sum Closest: When Close Enough Is As Good As It Gets

The O(n) Club: 3Sum Closest – When Close Enough Is As Good As It Gets

⚡ TL;DR

Don’t go all-in on O(n³) brute force unless you love noise and slow progress. Instead, sort, pin, and two-pointer your way to glory:

// Brute force version — not recommended for the living
int closest = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.length - 2; i++)
  for (int j = i + 1; j < nums.length - 1; j++)
    for (int k = j + 1; k < nums.length; k++)
      if (Math.abs(nums[i] + nums[j] + nums[k] - target) < Math.abs(closest - target))
        closest = nums[i] + nums[j] + nums[k];
// You deserve better.

🧠 How Devs Usually Mess This Up

🔍 What’s Actually Going On

Picture this: You, two friends, and a gift card. Your goal? Buy three things so the total is right up next to the card’s value, without overdrafting or standing in aisle 7 forever. Sort the options, fix one, then crabwalk left and right down the line with two pointers, always after the sum that hugs the target like an overenthusiastic Java tutor. Simple. Clean. Mildly magical.

🛠️ PseudoCode

• Sort the array (because chaos helps no one).
• For each index i from 0 to N-3:
  • Initialize left = i + 1, right = end.
  • While left < right:
    • Compute sum = nums[i] + nums[left] + nums[right]
    • If sum == target, return sum right away (achievement unlocked).
    • If the new sum is closer than previous best, update best.
    • If sum < target, left++ (need more); else right-- (dial it back).
• Return your best guess.

💻 The Code

public int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);
    int best = nums[0] + nums[1] + nums[2];
    for (int i = 0; i < nums.length - 2; i++) {
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (Math.abs(sum - target) < Math.abs(best - target)) {
                best = sum;
            }
            if (sum == target) {
                return sum; // Because this is as good as it gets
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    return best;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Duplicates? Totally fine — sum is king, not uniqueness.
• Triplet output? Don’t. They only want the sum.
• Array too small? Should’ve checked before — less than 3 is someone else’s emergency.
• Big arrays? Enjoy your O(n²) finesse. Leave brute-forcers in the dust.

🧠 Interviewer Brain-Tattoo

If solving for ‘close’ feels wrong, remember: perfect is the enemy of done. Sort, scan, and move on before your coffee cools off.