Triplet Sum Close to Target (3Sum Closest)

• 3Sum Closest – find the sum of three elements that is nearest to a given target, where nearest means the smallest absolute difference.
• Sort + fix + sweep – mirrors 3Sum: sort the array, fix each element, two-pointer sweep the rest.
• Track best – maintain a running best sum, updating it whenever a new triplet sum has a smaller distance to the target.
• Exact match early return – if a sum equals the target exactly, return immediately since distance zero cannot be beaten.
• Complexity – O(n^2) time, O(1) extra space (excluding the sort).

What is the 3Sum Closest problem?

Given an array of integers and a target value, find three elements whose sum is closest to the target and return that sum. There is exactly one solution for each input.

package com.bank.service;

import java.util.Arrays;

public class ThreeSumClosest {
    public static int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int closest = nums[0] + nums[1] + nums[2];

        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // optional skip
            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(closest - target)) {
                    closest = sum;
                }
                if (sum == target) return sum; // exact match
                else if (sum < target) left++;
                else right--;
            }
        }
        return closest;
    }

    public static void main(String[] args) {
        int[] amounts = {-1, 2, 1, -4};
        System.out.println("Closest sum to 1: " + threeSumClosest(amounts, 1));
    }
}

Closest sum to 1: 2

How is this different from 3Sum?

Both problems share the sort-fix-sweep skeleton. The difference is the goal: 3Sum collects all triplets whose sum is exactly zero, while 3Sum Closest returns the single closest sum to a given target.

| Aspect | 3Sum | 3Sum Closest |
|---|---|---|
| Goal | All triplets summing to zero | Single closest sum to target |
| Return type | List of triplets | Single integer |
| Duplicate handling | Required for correctness | Optional (only saves work) |
| Early exit | When fixed element > 0 | When sum == target |
| Result update | Record triplet on exact match | Update closest when distance decreases |

// 3Sum: collect all triplets with sum == 0
// if (sum == 0) result.add(...)

// 3Sum Closest: track the nearest sum to target
// if (abs(sum - target) < abs(closest - target)) closest = sum

Why initialize closest to the first three elements?

Initializing closest to the sum of the first three sorted elements guarantees that closest starts as a valid triplet sum. Using Integer.MAX_VALUE as a sentinel would risk overflow when computing the absolute difference.

// SAFE: closest starts as a valid triplet sum
int closest = nums[0] + nums[1] + nums[2];

// RISKY: Integer.MAX_VALUE can cause overflow
// int closest = Integer.MAX_VALUE;  // abs(MAX_VALUE - target) may overflow

How does the two-pointer sweep chase the target?

For each fixed element, you set left = i + 1 and right = end. You compute the triplet sum and compare its distance from the target to the distance of the current best. If the sum is below the target, you move left right to increase the sum. If it is above the target, you move right left to decrease it. If it equals the target exactly, you return immediately.

// Walkthrough: nums = [-4, -1, 1, 2], target = 1
// Sorted: [-4, -1, 1, 2]
// Fix i=0 (-4): left=1, right=3
//   sum = -4 + -1 + 2 = -3, dist=4. closest=-3
//   sum < target, left++
//   sum = -4 + 1 + 2 = -1, dist=2. closest=-1
//   sum < target, left++ -> left >= right
// Fix i=1 (-1): left=2, right=3
//   sum = -1 + 1 + 2 = 2, dist=1. closest=2
//   sum > target, right-- -> left >= right
// Return 2

What are the edge cases?

The minimum input is three elements, in which case the only triplet is the answer. If the target equals the sum of any triplet, the exact match triggers an early return.

package com.bank.service;

public class ThreeSumClosestEdge {
    public static void main(String[] args) {
        // Exactly three elements
        System.out.println(ThreeSumClosest.threeSumClosest(new int[]{1, 2, 3}, 6)); // 6
        // Exact match triggers early return
        System.out.println(ThreeSumClosest.threeSumClosest(new int[]{0, 0, 0}, 0)); // 0
    }
}

6
0

What about duplicate skipping?

Duplicate skipping is optional in 3Sum Closest because the result is a single number, not a list of unique triplets. However, skipping duplicate fixed elements saves redundant work without changing the result.

// Optional but helpful:
if (i > 0 && nums[i] == nums[i - 1]) continue;
// Skips redundant fixed elements, saving some inner iterations

What are common mistakes?

The most common mistake is initializing closest incorrectly. Using a sentinel like Integer.MAX_VALUE risks overflow when computing the absolute difference.

// WRONG: may overflow
int closest = Integer.MAX_VALUE;
int dist = Math.abs(closest - target);  // overflow if target is negative

// CORRECT: use a real triplet sum
int closest = nums[0] + nums[1] + nums[2];

Another mistake is forgetting the early return on exact match, which wastes time but does not affect correctness.

When should you use this technique?

Use 3Sum Closest when you need the triplet sum nearest to a target and an exact match may not exist. In banking, this applies when combining exactly three pending amounts to approximate an obligation.

package com.bank.service;

import java.util.Arrays;

public class SettlementClosest {
    public static void main(String[] args) {
        int[] pendingAmounts = {15000, -8000, 22000, -5000, 10000};
        int obligation = 20000;
        int closest = ThreeSumClosest.threeSumClosest(pendingAmounts, obligation);
        System.out.println("Closest combination to obligation: " + closest);
    }
}

Closest combination to obligation: 17000

What should a senior engineer know?

A senior engineer should recognize that 3Sum Closest is a small variation of 3Sum, sharing the same sort-fix-sweep skeleton. The only changes are: track the closest sum instead of collecting exact matches, and return immediately on distance zero.

This pattern recognition is the real test in interviews. If you can adapt the 3Sum solution to the closest variant in under a minute, it shows you understand the skeleton rather than memorizing individual solutions.

What are common interview follow-up questions?

• Interviewers commonly ask:
• How is this different from 3Sum? (Track closest instead of collecting exact matches.)
• Do you need to handle duplicates? (Not for correctness, but skipping saves work.)
• What if there are ties? (Any one of the tied sums is acceptable.)
• Can you extend this to k-Sum Closest? (Yes, same recursive skeleton.)