Find the Triplet Sum Nearest to a Target Value

Medium20–25 min

Topics

ArrayTwo PointerSorting

Companies

AmazonGoogleMicrosoftBloomberg

Given an integer array nums and an integer target, find the sum of exactly three different elements that lands as close as possible to target. Return that sum itself — not the triplet. You may assume there's exactly one distance-minimizing sum to report. For example, with nums = [-6, 1, 1, 1, 8] and target = 2, the triplet 1 + 1 + 1 = 3 is only 1 away from the target, closer than anything else the array can produce, so the answer is 3.

Test Case 1:

Input:nums = [-6, 1, 1, 1, 8], target = 2

Output:3

Explanation:The closest reachable sum is 1 + 1 + 1 = 3, exactly 1 away from the target — every other triplet lands farther off.

Test Case 2:

Input:nums = [0, 0, 0], target = 1

Output:0

Explanation:There's only one possible triplet, so its sum is the answer by default.

Test Case 3:

Input:nums = [1, 2, 3, 4], target = 6

Output:6

Explanation:1 + 2 + 3 hits the target exactly — nothing can beat a difference of zero.

Constraints

◆3 ≤ nums.length ≤ 500
◆-1000 ≤ nums[i] ≤ 1000
◆-10⁴ ≤ target ≤ 10⁴

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

nums (integers) — 3-12 integers, separated by commas or spaces.target

1	class Solution {
2	public int closestTripletSum(int[] nums, int target) {
3	Arrays.sort(nums);
4	int n = nums.length;
5	int best = nums[0] + nums[1] + nums[2];
6	for (int i = 0; i < n - 2; i++) {
7	int left = i + 1, right = n - 1;
8	while (left < right) {
9	int sum = nums[i] + nums[left] + nums[right];
10	if (Math.abs(sum - target) < Math.abs(best - target)) {
11	best = sum;
12	}
13	if (sum == target) {
14	return sum;
15	} else if (sum < target) {
16	left++;
17	} else {
18	right--;
19	}
20	}
21	}
22	return best;
23	}
24	}
25

-6

Variables

best-4

INITIALIZE

nums = [-6, 1, 1, 1, 8], target = 2. It's already sorted. Seed best with the sum of the first three values: -6 + 1 + 1 = -4.

Step 1 / 18

Approach & Solutions

Brute Force — Three Nested Loops

Brute

Try every combination of three distinct indices, compute each sum, and keep whichever one lands closest to target (smallest absolute difference), updating the best answer as you go.

TimeO(n³)

SpaceO(1)

Java

Try it out

class Solution {
    public int closestTripletSum(int[] nums, int target) {
        int n = nums.length;
        int best = nums[0] + nums[1] + nums[2];
        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];
                    if (Math.abs(sum - target) < Math.abs(best - target)) {
                        best = sum;
                    }
                }
            }
        }
        return best;
    }
}

Optimal — Sort + Two Pointer

Optimal

Sort the array, then fix the first number with a single loop and scan the rest with two pointers, exactly like the zero-sum-triplet search. At every step, check whether the current sum beats the best difference found so far. If the sum matches the target exactly, nothing can beat a difference of zero, so return immediately. Otherwise move left up when the sum is too small, or right down when it's too big — sorting is what lets a single comparison tell you which direction closes the gap.

TimeO(n²)

SpaceO(1) extra