3Sum Closest — Solution in Python, Java & C++
3Sum Closest solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Dream11.
3Sum Closest is a medium coding problem on arrays, sorting and two pointers, asked in Dream11 interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Two Pointers
- Asked at: Dream11
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array nums and an integer target, find three numbers in nums whose sum is closest to target and return that sum. Each input has exactly one closest sum.
Example 1
Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: (-1 + 2 + 1) = 2.
Example 2
Input: nums = [0,0,0], target = 1
Output: 0
Constraints
3 <= nums.length <= 12-20 <= nums[i] <= 20-60 <= target <= 60
Hints for 3Sum Closest
Hint 1
Sort, fix one element, two-pointer the rest — like 3Sum but tracking the closest sum.
Hint 2
Early-exit when the sum hits the target exactly.
How to solve 3Sum Closest
The same sorted two-pointer machinery as 3Sum, but instead of demanding an exact hit you keep the best near-miss. Sorting is what lets a single comparison tell you which way to move: if the current sum is below the target, the only way to grow it is to raise the smaller element.
Approach
- Sort the array and seed
bestwith any valid triplet sum, such as the first three values. - Fix
i, then sweepl = i + 1andr = n - 1towards each other. - At each step compute the sum and update
bestif it is closer to the target than the current best. - If the sum is below the target move
lright; if above, moverleft. - An exact match cannot be beaten — return it immediately.
Why it works
For a fixed i, sliding the pointers explores the pair sums monotonically, so the comparison against the target always points towards the region that could improve the answer — the discarded side is uniformly further away in the wrong direction. Every candidate that could be the closest is therefore examined, and tracking a running minimum of |sum - target| picks it out.
Complexity
- Time —
O(n^2) - Space —
O(n)
Pitfalls
- Seed
bestwith a real triplet sum, not0or a huge sentinel — comparing distances against an unreachable value can never improve. - Compare absolute distances to the target, not the raw sums.
- No deduplication is needed or wanted here; skipping repeats could skip the closest sum.
- Return the sum itself, not the distance.
Reference solution
Python
from typing import List
def threeSumClosest(nums: List[int], target: int) -> int:
s = sorted(nums)
best = s[0] + s[1] + s[2]
for i in range(len(s) - 2):
l, r = i + 1, len(s) - 1
while l < r:
total = s[i] + s[l] + s[r]
if abs(total - target) < abs(best - target):
best = total
if total == target:
return total
if total < target:
l += 1
else:
r -= 1
return bestJava
public static int threeSumClosest(int[] nums, int target) {
int[] s = nums.clone();
Arrays.sort(s);
int n = s.length;
int best = s[0] + s[1] + s[2];
for (int i = 0; i + 2 < n; i++) {
int l = i + 1, r = n - 1;
while (l < r) {
int sum = s[i] + s[l] + s[r];
if (Math.abs(sum - target) < Math.abs(best - target)) best = sum;
if (sum < target) l++;
else if (sum > target) r--;
else return sum;
}
}
return best;
}C++
int threeSumClosest(vector<int>& nums, int target) {
vector<int> s = nums;
sort(s.begin(), s.end());
int n = (int) s.size();
int best = s[0] + s[1] + s[2];
for (int i = 0; i + 2 < n; i++) {
int l = i + 1, r = n - 1;
while (l < r) {
int sum = s[i] + s[l] + s[r];
if (abs(sum - target) < abs(best - target)) best = sum;
if (sum < target) l++;
else if (sum > target) r--;
else return sum;
}
}
return best;
}JavaScript
var threeSumClosest = function(nums, target) {
const s = nums.slice().sort(function(a, b) { return a - b; });
let best = s[0] + s[1] + s[2];
for (let i = 0; i < s.length - 2; i++) {
let l = i + 1, r = s.length - 1;
while (l < r) {
const sum = s[i] + s[l] + s[r];
if (Math.abs(sum - target) < Math.abs(best - target)) best = sum;
if (sum === target) return sum;
if (sum < target) l++;
else r--;
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms