3Sum Closest LeetCode 16 Solution for FAANG

Pattern Recognition — 3Sum Closest (LeetCode 16)

The 3Sum Closest problem is a natural extension of 3Sum. Instead of finding triplets that sum exactly to zero, we aim to find a triplet whose sum is closest to a given target. Recognizing this pattern early helps choose the right approach in interviews.

Key Clues to Spot This Problem

• Three elements are involved → think triplets.
• Target sum is given, but not necessarily zero → implies closest/absolute difference logic.
• Input array may not be sorted → consider sorting first.
• Look for phrases like: "return sum closest to target", "three numbers sum", "minimize difference".

Comparison with Two Sum & 3Sum Patterns

Problem	Input	Goal	Key Pattern
Two Sum (LC1)	Array, target	Find exact pair sum = target	Hash map → O(n) or brute-force → O(n²)
Two Sum II (LC167)	Sorted array, target	Find exact pair sum = target	Two-pointer approach → O(n)
3Sum (LC15)	Array	Find all triplets sum = 0	Sort + two-pointer inside loop → O(n²)
3Sum Closest (LC16)	Array, target	Find triplet sum closest to target	Sort + two-pointer inside loop, track minimal difference → O(n²)

ASCII Flow Example

Consider nums = [-4, -1, 1, 2], target = 1. After sorting:

Sorted nums: [-4, -1, 1, 2]
i = 0 → nums[i] = -4
left = i+1 = 1 → nums[left] = -1
right = len-1 = 3 → nums[right] = 2

Sum = -4 + (-1) + 2 = -3 → closestSum = -3 (diff = 4)
Move left → 2nd pointer to increase sum → left = 2
Sum = -4 + 1 + 2 = -1 → closer to target 1 → update closestSum = -1
Move left → left = 3 → pointers meet → i = 1
i = 1 → nums[i] = -1
left = 2 → nums[left] = 1
right = 3 → nums[right] = 2
Sum = -1 + 1 + 2 = 2 → closest to target 1 → update closestSum = 2
Pointers meet → done.
Final closestSum = 2
  

Beginner-Friendly Pattern Recognition Tips

• Always sort the array first for easier pointer movement.
• Use a variable like closestSum to track the sum with minimal absolute difference from the target.
• Outer loop fixes the first element; two inner pointers search for best sum.
• Dry-run small examples with ASCII diagrams to visualize pointer shifts.
• Compare with 3Sum: instead of exact zero sum, update only if the absolute difference improves.

Interview Tips

• Restate the problem emphasizing "closest sum to target".
• Explain why sorting helps reduce complexity and simplifies two-pointer logic.
• Show understanding of pointer movement: increment left if sum < target, decrement right if sum > target.
• Mention handling duplicates if interviewer asks about unique triplets (optional for closest sum).

Interview-Focused — Short Answer to Deliver (Two Sum II)

"Start by stating brute-force checks all pairs (O(n²)) for correctness. Then mention the optimized two-pointer approach: initialize left and right, compute sum = nums[left] + nums[right]. Move pointers toward each other based on sum comparison. Return the first valid pair. This achieves O(n) time and O(1) space. Mention handling of duplicates, minimal array size, negatives, and confirm sorted input."

One-minute checklist to say

• Restate problem and confirm constraints (sorted, indices, duplicates).
• Explain why brute-force is slow (O(n²)).
• Explain two-pointer approach, pointer movements, and early return.
• Do a dry-run on a sample array (e.g., [2,7,11,15], target=9).
• Mention edge cases and potential follow-ups: duplicates, negatives, multiple pairs.
• Highlight O(n) time and O(1) space efficiency.

Interview Script & What to Say (Two Sum II — Sorted Array)

Step-by-step script (word-for-word suggestions)

1. "I'll restate the problem: given a sorted array nums and target, return the 1-indexed positions of two numbers that sum to target. Are duplicates possible and do I return the first valid pair?"
2. "Since the array is sorted, a brute-force approach of checking all pairs is O(n²). It's correct but not optimal for large inputs."
3. "A better approach is two-pointer. Initialize left=0, right=nums.length-1. Compute sum = nums[left] + nums[right]. If sum == target, return [left+1, right+1]. If sum < target, move left++. If sum > target, move right--. This runs in O(n) time and O(1) space."
4. Dry-run a small example out loud: nums=[2,7,11,15], target=9.
5. "Edge cases: minimal array size (2), duplicates, negatives, and multiple valid pairs. Always confirm array is sorted before assuming two-pointer."

What the interviewer hears

• Clear problem restatement and constraints check.
• Recognition of input properties (sorted array) and optimal approach.
• Ability to communicate pointer movement strategy, dry run, and early exit.
• Consideration of edge cases and follow-up questions.

Solution Approach — 3Sum Closest (LeetCode 16)

The key idea is to extend the 3Sum pattern. We sort the array and use an outer loop to fix the first element, then apply two pointers (left and right) to find the triplet sum closest to the target.

Step-by-Step JavaScript Approach

1. Sort the array in ascending order.
2. Initialize a variable closestSum to track the triplet sum closest to the target.
3. Iterate over the array using index i as the first element.
4. Use two pointers: left = i + 1 and right = nums.length - 1.
5. Compute sum = nums[i] + nums[left] + nums[right].
6. If Math.abs(sum - target) < Math.abs(closestSum - target), update closestSum = sum.
7. Move pointers based on comparison:
   • If sum < target → increment left to increase sum.
   • If sum > target → decrement right to decrease sum.
   • If sum == target → exact match, return immediately.
8. Repeat until all triplets are considered.

ASCII Pointer Dry-Run Example

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

Sorted nums: [-4, -1, 1, 2]

i = 0 → nums[i] = -4
left = 1 → nums[left] = -1
right = 3 → nums[right] = 2

Sum = -4 + (-1) + 2 = -3
closestSum = -3 (abs(-3 - 1) = 4)

Since sum < target → move left
left = 2 → nums[left] = 1
Sum = -4 + 1 + 2 = -1
closestSum = -1 (abs(-1 - 1) = 2)

Since sum < target → move left
left = 3 → pointers meet → increment i

i = 1 → nums[i] = -1
left = 2 → nums[left] = 1
right = 3 → nums[right] = 2

Sum = -1 + 1 + 2 = 2
closestSum = 2 (abs(2 - 1) = 1) → updated

Pointers meet → done
Final closestSum = 2
  

JavaScript Implementation

// Function to find 3Sum Closest
function threeSumClosest(nums, target) {
  nums.sort((a, b) => a - b);
  let closestSum = nums[0] + nums[1] + nums[2];

  for (let i = 0; i < nums.length - 2; i++) {
    let left = i + 1;
    let right = nums.length - 1;

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

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

      if (sum < target) {
        left++;
      } else if (sum > target) {
        right--;
      } else {
        // Exact match
        return sum;
      }
    }
  }

  return closestSum;
}

// Example
console.log(threeSumClosest([-4, -1, 1, 2], 1)); // Output: 2
  

Beginner-Friendly Notes

• Sorting simplifies pointer movement → always consider sorting for multi-pointer problems.
• Track closestSum carefully using Math.abs for comparison.
• Exact match shortcut: if sum == target, no need to continue.
• Outer loop runs until nums.length - 2 because we need at least 3 elements.

Interview Tips

• Explain sorting and two-pointer strategy clearly to the interviewer.
• Mention why updating closestSum only when absolute difference improves is crucial.
• Dry-run small arrays to demonstrate understanding.
• Compare with 3Sum: only difference is tracking minimal difference instead of exact zero sum.

Deep Dive — 3Sum Closest (LeetCode 16)

Correctness Invariant (How to Explain)

At the start of each iteration with index i as the fixed element:

• The subarray nums[i+1..n-1] is scanned using two pointers (left, right).
• The current closestSum always holds the triplet sum closest to target found so far.
• Whenever a triplet sum is closer to target than closestSum, we update it. This invariant guarantees the final result is correct.

Pointer Movement Reasoning

• Left Pointer: moves right if sum < target → need a larger sum.
• Right Pointer: moves left if sum > target → need a smaller sum.
• This movement ensures exploration of all candidate sums without missing potential closest sums.

Variants & Trade-Offs

• Return triplet itself: Instead of just the sum, we can return [nums[i], nums[left], nums[right]].
• Multiple closest sums: Keep an array of triplets if multiple sums have the same minimal difference.
• Memory-tight variant: No extra memory needed; we only track closestSum and optional triplet array.
• Streaming input: Cannot use two pointers on streaming input directly; need a buffered window approach (rare in interviews).

Micro-Optimizations You Can Mention

• Skip duplicate fixed elements (i.e., nums[i] == nums[i-1]) to avoid redundant calculations.
• Early termination: if sum == target, return immediately — no better sum exists.
• Use Math.abs(sum - target) to track minimal difference efficiently.
• Sorting simplifies pointer movement → always sort before two-pointer traversal.

Proof Sketch (Short)

Suppose the algorithm returns closestSum. For any triplet [a,b,c], if |a+b+c - target| < |closestSum - target|, we would have updated closestSum during iteration. Conversely, if no triplet sum is closer than closestSum, the two-pointer search will have scanned all valid triplets systematically, guaranteeing correctness.

Comparison with Two Sum & 3Sum

Problem	Goal	Pattern	Pointer Logic
Two Sum I	Find exact pair sum = target	Hash Map / Brute Force	None (map-based)
Two Sum II	Find exact pair sum = target in sorted array	Two-pointer	Left-right movement depending on sum vs target
3Sum	Find triplets where sum = 0	Two-pointer after fixing one element	Move pointers to skip duplicates and sum zero
3Sum Closest	Find triplet sum closest to target	Two-pointer after fixing one element	Move left/right to minimize |sum - target|; update closestSum

Interview Tips

• Explain the invariant of closestSum and why it ensures correctness.
• Dry-run a small array with ASCII pointer movements for clarity.
• Mention micro-optimizations and early return for exact matches.
• Compare and contrast with Two Sum and 3Sum for pattern recognition in interviews.

Common Pitfalls — 3Sum Closest (LeetCode 16)

1. Forgetting to Sort the Array

Two-pointer logic requires a sorted array. If the array is not sorted:

• Pointers may move incorrectly.
• Closest sum may be missed.

Example:
nums = [1,4,2], target = 6
Without sorting, left=1, right=4 → incorrect pointer movement
  

2. Not Updating Closest Sum Correctly

Common mistake: comparing only sums greater than target or using wrong absolute difference.

Incorrect:
if (sum > target) closestSum = sum
Correct:
if (Math.abs(sum - target) < Math.abs(closestSum - target)) closestSum = sum
  

3. Pointer Off-by-One Errors

Beginner mistakes often involve:

• Not initializing left = i+1 or right = n-1.
• Using < instead of <= in loops.
• Moving pointers incorrectly (left/right) without checking sum vs target.

Example:
i=0, left=i+1=1, right=2
sum = nums[i]+nums[left]+nums[right]
If sum < target → left++ (correct)
If sum > target → right-- (correct)
Wrong pointer move may skip valid closest sums
  

4. Failing to Handle Duplicates Properly

While 3Sum Closest doesn’t require unique triplets, skipping duplicates of the fixed element nums[i] is a micro-optimization to avoid redundant calculations.

if (i > 0 && nums[i] == nums[i-1]) continue; // skip duplicate fixed element
  

5. Early Return Misunderstandings

If sum == target, it's safe to return immediately. But forgetting this can lead to unnecessary iterations.

6. Confusing 3Sum Closest with 3Sum

• 3Sum → find exact zero sum triplets, skip duplicates carefully.
• 3Sum Closest → find sum closest to target, focus on minimal difference.
• Pointer movement logic is similar but update condition is different.

7. Common Interview Errors

• Not explaining pointer strategy clearly to interviewer.
• Not mentioning sorting requirement and complexity.
• Dry-running only one example — always show at least one positive and one negative example.
• Ignoring edge cases like array length < 3.

Edge Cases — 3Sum Closest (LeetCode 16)

1. Array Length Less Than 3

If nums.length < 3, no triplet exists. Handle this early to avoid errors.

Example:
nums = [1, 2], target = 3
Output: undefined or error handling
  

2. Array Already Contains Closest Sum

Sometimes the first triplet is already closest. Always initialize closestSum properly.

nums = [1, 2, 3, 4], target = 6
Initial closestSum = nums[0]+nums[1]+nums[2] = 6 → exact match
Early return possible
  

3. Negative Numbers & Mixed Signs

Algorithm works with negatives and positives, but pointer logic must consider sorted array.

nums = [-4, -1, 1, 2], target = 1
i=0, left=1, right=3
sum = -4 + (-1) + 2 = -3 → left++
sum = -4 + 1 + 2 = -1 → left++
sum = -1 + 1 + 2 = 2 → right-- 
Closest sum = 2 (diff=1), target=1
  

4. Duplicate Numbers

Duplicates do not require skipping for correctness, but skipping repeated fixed elements reduces unnecessary iterations.

nums = [1,1,2,2,3,3], target = 6
i=0, nums[i]=1 (skip next i=1 since nums[1]=nums[0])
Reduces duplicate computation
  

5. Target Outside Array Sum Range

Target less than minimal triplet sum → closest is minimal sum. Target greater than maximal triplet sum → closest is maximal sum.

nums = [1,2,3,4], target = 20
Max sum = 2+3+4 = 9 → closestSum = 9
nums = [1,2,3,4], target = -10
Min sum = 1+2+3 = 6 → closestSum = 6
  

6. ASCII Flow for Pointer Movement

Example for nums=[-1,0,1,2,-1,-4], target=1 (sorted: [-4,-1,-1,0,1,2]):

i=0, nums[i]=-4
left=1, right=5
sum=-4+(-1)+2=-3 → move left++
sum=-4+(-1)+2=-3 → move left++
sum=-4+0+2=-2 → move left++
sum=-4+1+2=-1 → move left++
i=1, nums[i]=-1
left=2, right=5
sum=-1+(-1)+2=0 → move left++
sum=-1+0+2=1 → exact match → early return
  

7. Suggested Interview Demo

• Dry-run with small array of 4–6 elements, including negatives and duplicates.
• Explain sorting requirement, pointer initialization, movement decisions (left++ / right--).
• Show edge case where target is outside sum range.
• Highlight why skipping duplicate fixed elements is a micro-optimization.

Time & Space Complexity — 3Sum Closest

1. Time Complexity Analysis

The main algorithm uses a for loop to fix one element, and two pointers (left & right) to find the closest sum. Sorting is required first.

JavaScript implementation outline:

nums.sort((a,b) => a-b); // O(n log n)
let closestSum = nums[0]+nums[1]+nums[2];

for (let i = 0; i < nums.length-2; i++) {
    let left = i+1, right = nums.length-1;
    while (left < right) {
        const sum = nums[i]+nums[left]+nums[right];
        // update closestSum if needed
        if (sum < target) left++;
        else right--;
    }
}
  

Loop analysis: - Outer loop: O(n) - Inner while loop: Each iteration moves a pointer once → total per i is O(n) → Total time = O(n²) → Plus sorting = O(n log n) (dominated by O(n²))

2. Space Complexity

• Sorting in-place: O(1) extra (JS sort() may use O(log n) stack for some engines)
• Pointers and variables: O(1)
• Overall: O(1) extra space

3. Step-by-step Example with Space Tracking

nums = [-1, 2, 1, -4], target = 1
After sorting: [-4, -1, 1, 2]
Variables:
i=0 → nums[i]=-4
left=1 → nums[left]=-1
right=3 → nums[right]=2
sum=-4 + (-1) + 2 = -3 → closestSum updated
Pointers move: left++ → left=2
sum=-4+1+2=-1 → closestSum updated
Pointers move: left++ → left=3 → exit inner while

i=1 → nums[i]=-1
left=2, right=3
sum=-1+1+2=2 → closestSum updated
Pointers move: right-- → left=2, right=2 → exit
Final closestSum=2
Memory used: few pointers, closestSum variable → O(1)
  

4. Key Takeaways

• Time complexity is dominated by nested loop (O(n²)), not sorting.
• Space is minimal (O(1)), making this approach memory-efficient.
• Micro-optimization: early return if exact match sum === target found → avoids unnecessary iterations.
• Sorting enables pointer-based traversal instead of O(n³) brute-force.

Related Problems & Progression Path — 3Sum Closest

1. Variants & Comparisons

Problem	Array Sorted?	Goal	Time Complexity	Space Complexity	Notes
Two Sum (LC1)	No	Find pair of indices whose sum = target	O(n) optimized	O(n)	Hash map approach; array need not be sorted
Two Sum II (LC167)	Yes	Find pair of indices whose sum = target	O(n)	O(1)	Two-pointer method; efficient for sorted array
3Sum (LC15)	Yes	Find all unique triplets summing to 0	O(n²)	O(1)	Two-pointer with duplicates handling
3Sum Closest (LC16)	Yes	Find triplet sum closest to target	O(n²)	O(1)	Similar to 3Sum; early return if exact match found
4Sum (LC18)	Yes	Find quadruplets summing to target	O(n³)	O(1)	Extension of 3Sum using nested loops + two-pointer

2. Progression Path for Interview Prep

1. Master Two Sum (LC1) → hash map approach
2. Move to Two Sum II (LC167) → two-pointer approach
3. Practice 3Sum (LC15) → multiple triplets + duplicates handling
4. Learn 3Sum Closest (LC16) → pointer strategy + closest sum logic
5. Advance to 4Sum (LC18) → nested loops + pointer extensions

3. Interview Practice Strategy

• Always start by checking if array is sorted or not → choose hash map vs two-pointer.
• Dry-run small examples with ASCII pointer diagrams.
• Explain time/space trade-offs during interviews.
• Practice variants: 3Sum with target = 0, 3Sum Closest for any target, 4Sum, kSum for extension.
• Discuss micro-optimizations: early return, duplicate skipping, pointer movement reasoning.
• Compare with Two Sum I & II to show knowledge of pattern recognition in array-sum problems.

FAQs — 3Sum Closest

1. What is the 3Sum Closest Problem (LeetCode 16)?

Given an integer array nums and a target integer target, find the sum of a triplet in nums that is closest to the target. Return that sum. Example: nums = [-1,2,1,-4], target = 1 → closest sum = 2 (-1 + 2 + 1).

2. What is the recommended approach?

• Sort the array.
• Iterate with a fixed first element and use two pointers for the remaining two elements.
• Calculate the sum, track the closest sum, and move pointers based on comparison with target.
• Early return if exact match found.

3. Time and Space Complexity?

• Time: O(n²) — one loop + two pointers.
• Space: O(1) — ignoring input sorting space.

4. Key edge cases to consider?

• Array length exactly 3 → return the sum directly.
• Multiple triplets have same closest distance → any valid closest sum is fine.
• Negative numbers, zeros, and positive numbers.
• Array already sorted vs unsorted.

5. Common mistakes candidates make?

• Not sorting array → two-pointer strategy fails.
• Incorrect pointer movement logic → may skip better closest sums.
• Ignoring early return on exact match.
• Incorrect initialization of closest sum or distance.

6. Micro-optimizations to mention in interview

• Early exit if sum equals target — no need to continue.
• Skip duplicates for first element to avoid unnecessary iterations.
• Track minimum distance instead of absolute difference every iteration to reduce calculations.
• Dry-run with small array examples to show pointer movement reasoning.

7. Keywords or hints to spot this problem in interviews?

Phrases like "sum closest to target", "triplet sum", "array of integers", "find sum near target" often hint at 3Sum Closest problems.

8. Related problems to practice?

• Two Sum (LC1), Two Sum II (LC167)
• 3Sum (LC15)
• 4Sum (LC18)
• kSum variations

9. How to explain this in a FAANG interview?

1. Restate problem and confirm constraints (array length, sorting requirement).
2. Show brute-force O(n³) first to prove correctness.
3. Explain optimized two-pointer approach after sorting → O(n²) time.
4. Explain pointer movement logic with dry-run.
5. Discuss edge cases, duplicates handling, and early return optimization.
6. Optional: compare with 3Sum and Two Sum I/II to show pattern recognition.