Closest Triplet Sum
MediumTwo Pointers
Problem
A nutrition app wants to combine three different foods from nums (their calorie values, three different positions) so the total is as close as possible to target calories.
Return the triplet sum with the smallest absolute difference from target. If two sums are equally close (one above and one below), return the smaller sum.
Example 1
- Input:
- nums = [4, -1, 2, 7, -3], target = 5
- Output:
- 5
4 + 2 + (-1) = 5 hits the target exactly.
Example 2
- Input:
- nums = [1, 4, 6, 9], target = 15
- Output:
- 14
1 + 4 + 9 = 14 and 1 + 6 + 9 = 16 are both 1 away; the smaller wins.
Example 3
- Input:
- nums = [1, 1, 1], target = 10
- Output:
- 3
Constraints
- 3 ≤ nums.length ≤ 1000
- -1000 ≤ nums[i] ≤ 1000
- -10^4 ≤ target ≤ 10^4
Hint
Show the first hint
As with finding exact triplets, fix one value and treat the other two as a pair problem.
Walkthrough
How to approach it
01Clarify before coding
- Return the sum or the indices? The sum.
- What if two sums are equally close? Return the smaller one.
- Is there always at least one triplet? Yes, n ≥ 3.
02Brute force
Evaluate every triple of indices and keep the best sum with the tie rule.
Cost: O(n³): about 1.7·10^8 triples for n = 1000, borderline-to-slow and not what the interviewer wants.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.