Two PointersMediumO(n²) time · O(1) space

Triplet Sum Close to Target

Ramayana — The Perfect Arrow — Rama's Aim for the Eye of the Fish

लक्ष्यं निकटं यथा स्यात् तथा बाणः प्रयोज्यते। त्रयाणां संयुतं शक्त्या लक्ष्याभिमुखं नयेत्॥

*The arrow is released to land as close to the target as possible. With the combined power of three, guide it toward the goal.*

The Story

The swayamvara of Sita was unlike any other. In the great hall of Mithila, a golden fish hung from the ceiling, rotating slowly. Below it, a pool of oil reflected its image. The challenge: using only the reflection, shoot an arrow through the eye of the rotating fish.

But King Janaka had added a twist for the mathematical minds among the suitors. Before attempting the shot, each prince must solve a puzzle:

"In my treasury are weights of various measures," Janaka announced. "You must select exactly three weights whose combined mass comes closest to the sacred number 108. Not exactly 108—that would be too easy. But as close as possible. The prince who finds the closest combination proves his precision of mind before testing his precision of hand."

The weights available: [-1, 2, 1, -4, 5, 3, 10, 8]

Princes began calculating furiously. One shouted combinations: "2 + 3 + 10 = 15? No, that's far from 108..." Another tried systematic enumeration, his scribes filling scroll after scroll with triplet sums.

Rama approached differently. He first sorted the weights by value: [-4, -1, 1, 2, 3, 5, 8, 10]

"With sorted weights," Rama murmured to Lakshmana, "I can use the same technique as finding an exact sum, but instead of stopping when I find equality, I track the closest sum seen so far."

He fixed the first weight at -4. Now he needed two more weights summing as close to 112 as possible (since -4 + 112 = 108).

Using two pointers on the remaining array: - Left at -1, right at 10: -1 + 10 = 9. Total triplet sum: -4 + 9 = 5. Distance from 108: |5 - 108| = 103. Record this as best so far. - Sum 9 is less than 112, so move left pointer right. - Left at 1, right at 10: 1 + 10 = 11. Total: 7. Distance: 101. Better! Update best. - Still less than 112, move left. - Left at 2, right at 10: 2 + 10 = 12. Total: 8. Distance: 100. Better! Update. - Continue...

Rama worked through each fixed element, tracking the closest sum overall. When he fixed the element 8, using pointers at other positions: - 8 + 10 + some third element... the combinations flew by.

The key insight: at each step, the two pointers either converged toward the target or discovered they'd overshot. Unlike 3Sum where we seek exact matches, here we record every valid sum and keep track of the minimum distance.

"I don't need to find an exact match," Rama explained. "I need the sum that minimizes |sum - target|. Every pair I examine with my two pointers gives a candidate. I compare each candidate to my current best."

The algorithm completed. Rama announced: "The closest triplet sum to 108 is 13, achieved by weights 3 + 2 + 8. The distance is 95."

(Note: This example uses small numbers for illustration. In Rama's actual swayamvara, the numbers were larger and the closest sum was much nearer to 108.)

Janaka nodded approvingly. "You have shown precision of calculation. Now show precision of aim."

Rama took up the bow, drew the arrow, and—seeing only the reflection, accounting for every variable—released. The arrow sang through the air and pierced the fish's eye exactly.

"He calculated the closest solution," Lakshmana whispered to Bharata. "In archery as in algorithms: aim for the target, but when perfection is impossible, get as close as you can."

This is the Two Pointer technique for finding the triplet sum closest to a target.

The Princes' First Instinct

Check every possible triplet, calculate the sum, track the one closest to the target. O(n³) time complexity.

java

public int threeSumClosestBruteForce(int[] nums, int target) {
    int closestSum = nums[0] + nums[1] + nums[2];
    int n = nums.length;
    
    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; 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;
}

Rama's Wisdom

Rama's insight: sort the array, then for each fixed element, use two pointers to explore pair sums. Unlike exact 3Sum, we don't stop at matches—we continuously update our closest sum whenever we find a better candidate. The two pointers still move based on whether the current sum is less than or greater than the target, but we record every sum's distance to the target and keep the minimum.

java

public int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);  // Essential for two-pointer technique
    
    // Initialize with first triplet
    int closestSum = nums[0] + nums[1] + nums[2];
    
    for (int i = 0; i < nums.length - 2; i++) {
        // Skip duplicates for efficiency (optional but helpful)
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        
        int left = i + 1;
        int right = nums.length - 1;
        
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            
            // Update closest if this sum is better
            if (Math.abs(sum - target) < Math.abs(closestSum - target)) {
                closestSum = sum;
            }
            
            // Early termination: exact match found
            if (sum == target) {
                return sum;
            }
            
            // Move pointers toward target
            if (sum < target) {
                left++;   // Need larger sum
            } else {
                right--;  // Need smaller sum
            }
        }
    }
    
    return closestSum;
}

// Test with Rama's weights
public static void main(String[] args) {
    int[] weights = {-1, 2, 1, -4};
    int target = 1;
    int closest = new Solution().threeSumClosest(weights, target);
    System.out.println("Closest sum to " + target + ": " + closest);
    // Output: Closest sum to 1: 2 (triplet: -1, 1, 2)
}

Step-by-Step Walkthrough

Array: [-1, 2, 1, -4], Target: 1
Sorted: [-4, -1, 1, 2]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Initialize: closestSum = -4 + (-1) + 1 = -4
|−4 − 1| = 5

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=0: Fix nums[0]=-4, target for pair: 1-(-4)=5
     [-4, -1, 1, 2]
      i    L     R
     
     L=1, R=3: -1+2=1, sum=-4+1=-3
     |-3-1|=4 < 5 → Update! closestSum=-3
     -3 < 1 → L++
     
     L=2, R=3: 1+2=3, sum=-4+3=-1
     |-1-1|=2 < 4 → Update! closestSum=-1
     -1 < 1 → L++
     
     L=3, R=3: L >= R, done with i=0

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=1: Fix nums[1]=-1, target for pair: 1-(-1)=2
     [-4, -1, 1, 2]
           i  L  R
     
     L=2, R=3: 1+2=3, sum=-1+3=2
     |2-1|=1 < 2 → Update! closestSum=2
     2 > 1 → R--
     
     L=2, R=2: L >= R, done with i=1

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=2: Only 2 elements left (1, 2), need at least 2
     Cannot form triplet, done.

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
✅ Result: closestSum = 2
   Triplet: [-1, 1, 2] with sum 2 (distance 1 from target 1)

Deep Insight

**Why does this work?**

The two-pointer technique efficiently searches for the pair sum closest to `target - nums[i]`. By moving pointers based on whether the current sum is too small or too large, we explore the most promising candidates.

**Key differences from exact 3Sum:** 1. We don't stop at matches (though we can early-terminate if sum == target) 2. We update `closestSum` at every step, not just on exact matches 3. Duplicate skipping is optional (for efficiency, not correctness)

**The optimality guarantee:** For a fixed first element, two pointers explore all "promising" pairs. We might miss some pairs when a pointer skips, but: - If `sum < target` and we move `left++`, the skipped pairs with this right pointer would give even smaller sums (farther from target) - If `sum > target` and we move `right--`, the skipped pairs with this left pointer would give even larger sums (farther from target)

**Edge cases:** - Exactly 3 elements: Return their sum (only option) - Target achievable exactly: Early termination - All negative or all positive: Still works correctly

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n³)	O(1)	Three nested loops checking all triplets
Optimal	O(n²)	O(1)	Sorting O(n log n) + n × O(n) two-pointer searches

Pattern Recognition

✅ Find triplet closest to a target (not exact match)
✅ Optimization problem (minimize distance to target)
✅ Array can be sorted
✅ "Closest" or "nearest" in problem statement

**LeetCode Trigger Phrases:**
→ "sum closest to the target"
→ "find three integers... closest to target"
→ "minimize the difference between sum and target"

Bhagavad Gita 9.27

यत्करोषि यदश्नासि यज्जुहोषि ददासि यत्। यत्तपस्यसि कौन्तेय तत्कुरुष्व मदर्पणम्॥

Whatever you do, whatever you eat, whatever you offer in sacrifice, whatever you give, whatever austerity you practice—do that as an offering to Me.

Connection: Rama's approach embodies this teaching: every action (every sum calculated) is offered toward the goal. Even when the exact target of 108 cannot be reached, each calculation contributes to finding the closest possible sum. The algorithm doesn't despair at imperfection—it systematically works toward the best achievable result, making every comparison count toward the ultimate goal.