The triple sum closest to a target
Given an integer array nums of length at least 3 and an integer target,
choose three elements at different indices whose sum is as close to target as possible, and return
that sum. If two sums are equally close, return the smaller.
Examples
| Input | Output | Why |
|---|---|---|
nums = [-1, 2, 1, -4], target = 1 | 2 | −1 + 2 + 1 = 2, at distance 1. |
nums = [0, 2, 4, 6], target = 9 | 8 | 0 + 2 + 6 = 8 and 0 + 4 + 6 = 10 are both 1 away; 8 is smaller. |
Constraints
- 3 ≤ n ≤ 500
- −1000 ≤ nums[i] ≤ 1000
- −10⁴ ≤ target ≤ 10⁴
Hints
Hint 1
Trying every triple is O(n³). Sort first: what does the order let you do once one element is fixed?
Hint 2
With nums[i] fixed, you want a pair from the rest whose sum is as close as possible to target − nums[i]. That is the sorted two-sum walk.
Hint 3
Move the left pointer right when the sum is too small and the right pointer left when it is too big, checking every sum you see against the best so far.
Where people lose marks
- Initialising the best sum with a huge constant and then comparing distances in a 32-bit type where the subtraction overflows. Start from the first triple instead.
- Ignoring the tie rule: with sums 8 and 10 around a target of 9, returning whichever was seen first.
- Moving both pointers at once, which skips pairs.
Dry run on [6,-3,4,1,9,-1],13
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 12nums-30-1112436495best-3
Sorted: -3, -1, 1, 4, 6, 9. Target 13. Start with the first triple, -3.
-
Step 2 / 12nums-30i-11j12436495ks5best5
-3 + -1 + 9 = 5, the best so far; too small: j moves right.
-
Step 3 / 12nums-30i-1112j436495ks7best7
-3 + 1 + 9 = 7, the best so far; too small: j moves right.
-
Step 4 / 12nums-30i-111243j6495ks10best10
-3 + 4 + 9 = 10, the best so far; too small: j moves right.
-
Step 5 / 12nums-30i-11124364j95ks12best12
-3 + 6 + 9 = 12, the best so far; too small: j moves right.
-
Step 6 / 12nums-30-11i12j436495ks9best12
-1 + 1 + 9 = 9; too small: j moves right.
-
Step 7 / 12nums-30-11i1243j6495ks12best12
-1 + 4 + 9 = 12; too small: j moves right.
-
Step 8 / 12nums-30-11i124364j95ks14best12
-1 + 6 + 9 = 14; too big: k moves left.
-
Step 9 / 12nums-30-1112i43j6495ks14best12
1 + 4 + 9 = 14; too big: k moves left.
-
Step 10 / 12nums-30-1112i43j64k95s11best12
1 + 4 + 6 = 11; too small: j moves right.
-
Step 11 / 12nums-30-111243i64j95ks19best12
4 + 6 + 9 = 19; too big: k moves left.
-
Step 12 / 12nums-30-1112436495best12
Every i has been tried. The closest sum is 12.
How to think about it
Sort. For each i, set j = i + 1 and k = n − 1 and look at
s = nums[i] + nums[j] + nums[k]. Record it if it is closer than the best so far (or equally close
and smaller). Then: if s < target, advance j; if s > target, move
k left; if s = target, nothing can be closer, so return it.
Why no good sum is skipped: advancing j abandons the pairs (j, k') with
k' < k, whose sums are at most s, which is already below the target, so none is
closer from below than s. Moving k abandons sums of at least s above the
target, by the same argument. So for each i the walk sees the closest sum from below and the closest
from above, which is all the tie rule needs.
Complexity. Time O(n²) · Space O(1) beyond the sort
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def three_sum_closest(nums, target):
a = sorted(nums)
n = len(a)
best = a[0] + a[1] + a[2]
for i in range(n - 2):
j, k = i + 1, n - 1
while j < k:
s = a[i] + a[j] + a[k]
d, e = abs(s - target), abs(best - target)
if d < e or (d == e and s < best):
best = s
if s == target:
return s
if s < target:
j += 1
else:
k -= 1
return best#include <vector>
#include <algorithm>
#include <cstdlib>
int solve(std::vector<int> a, int target) {
std::sort(a.begin(), a.end());
int n = (int)a.size(), best = a[0] + a[1] + a[2];
for (int i = 0; i + 2 < n; ++i) {
int j = i + 1, k = n - 1;
while (j < k) {
int s = a[i] + a[j] + a[k];
int d = std::abs(s - target), e = std::abs(best - target);
if (d < e || (d == e && s < best)) best = s;
if (s == target) return s;
if (s < target) ++j; else --k;
}
}
return best;
}class Solution {
public int threeSumClosest(int[] nums, int target) {
int[] a = nums.clone();
java.util.Arrays.sort(a);
int n = a.length, best = a[0] + a[1] + a[2];
for (int i = 0; i + 2 < n; i++) {
int j = i + 1, k = n - 1;
while (j < k) {
int s = a[i] + a[j] + a[k];
int d = Math.abs(s - target), e = Math.abs(best - target);
if (d < e || (d == e && s < best)) best = s;
if (s == target) return s;
if (s < target) j++; else k--;
}
}
return best;
}
}function threeSumClosest(nums, target) {
const a = nums.slice().sort((x, y) => x - y), n = a.length;
let best = a[0] + a[1] + a[2];
for (let i = 0; i < n - 2; i++) {
let j = i + 1, k = n - 1;
while (j < k) {
const s = a[i] + a[j] + a[k];
const d = Math.abs(s - target), e = Math.abs(best - target);
if (d < e || (d === e && s < best)) best = s;
if (s === target) return s;
if (s < target) j++; else k--;
}
}
return best;
}fn solve(nums: &[i64], target: i64) -> i64 {
let mut a = nums.to_vec();
a.sort();
let n = a.len();
let mut best = a[0] + a[1] + a[2];
for i in 0..n - 2 {
let (mut j, mut k) = (i + 1, n - 1);
while j < k {
let s = a[i] + a[j] + a[k];
let (d, e) = ((s - target).abs(), (best - target).abs());
if d < e || (d == e && s < best) { best = s; }
if s == target { return s; }
if s < target { j += 1; } else { k -= 1; }
}
}
best
}import Data.Array
import Data.List (sort, foldl')
solve :: [Int] -> Int -> Int
solve nums target = foldl' scan start [0 .. n - 3]
where
n = length nums
a = listArray (0, n - 1) (sort nums)
start = a ! 0 + a ! 1 + a ! 2
pick best s
| d < e || (d == e && s < best) = s
| otherwise = best
where d = abs (s - target); e = abs (best - target)
scan best i = walk best (i + 1) (n - 1)
where
walk b j k
| j >= k = b
| s == target = target
| s < target = walk b' (j + 1) k
| otherwise = walk b' j (k - 1)
where s = a ! i + a ! j + a ! k
b' = pick b sVariants to try
- Count the triples with sum less than the target: when s < target, every k' between j + 1 and k also works, so add k − j and advance j.
- Four numbers: fix two with nested loops and walk the other two, O(n³).
Next problems
A palindrome, ignoring punctuation and case
Compare from both ends inward, stepping over anything that is not a letter or a digit. No cleaned copy of the string is needed.
Open the problem → Easy10 minMerge two sorted arrays
The step at the heart of merge sort: one pointer per array, and the smaller front value goes next.
Open the problem → Easy10 minMove the zeros to the end
One pointer reads every element, the other marks where the next non-zero belongs. The order of the non-zero values is kept.
Open the problem →Write a solution and run it against the real test table.
Keep going
A palindrome, ignoring punctuation and case
Compare from both ends inward, stepping over anything that is not a letter or a digit. No cleaned copy of the string is needed.
Open the problem → Easy10 minMerge two sorted arrays
The step at the heart of merge sort: one pointer per array, and the smaller front value goes next.
Open the problem → Easy10 minMove the zeros to the end
One pointer reads every element, the other marks where the next non-zero belongs. The order of the non-zero values is kept.
Open the problem → Two pointersThe pattern behind it
Two indices walking a sorted or paired structure, each step ruling out one candidate for good.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.