15% off all plans & roadmaps Use code
See plans3Sum Closest
- LeetCode 16
- Medium
- Two Pointers
- Converging (Sorted Array Target Sum)
Updated
TL;DR: Sort the array, fix the first number of the triple, then move two pointers inward over the rest. Each move discards candidates that cannot beat the current best, which brings the search down to O(n^2).
Problem
Given an integer array nums of length n and an integer target, find three integers in nums whose sum is as close as possible to target.
Return the sum of those three integers.
You may assume that each input has exactly one solution.
Example 1
Input: nums = [-1,2,1,-4], target = 1 Output: 2 Explanation: The sum closest to the target is 2. (-1 + 2 + 1 = 2).
Example 2
Input: nums = [0,0,0], target = 1 Output: 0 Explanation: The sum closest to the target is 0. (0 + 0 + 0 = 0).
Constraints
3 <= nums.length <= 500-1000 <= nums[i] <= 1000-10^4 <= target <= 10^4
Constraints that matter
- n up to 500 means there are about 2 * 10^7 triples (500 choose 3 is 20,708,500). Checking every triple is too slow to be the intended answer, so the solution must skip most of them.
- Values stay between -1000 and 1000, so any triple sum lies between -3000 and 3000. Plain 32-bit integers hold every sum with room to spare, and overflow is not a concern.
- n is at least 3, so the first three values always form a valid triple. You can seed the best answer with that sum instead of an arbitrary number.
- Because the answer is a sum and not indices, the order of the array does not matter. Sorting is allowed, and it does not change the answer.
Hints
Hint 1
The problem asks for a triple whose sum lands near a target.
Hint 2
Try every triple of distinct positions.
Solution
Intuition
The problem asks for a triple whose sum lands near a target. Checking all triples costs cubic time. The useful observation is that the answer depends only on the values, not on their positions. You can sort the array without losing any candidate.
Picture bags sorted by weight on a shelf, with one hand on the lightest bag and one on the heaviest. The hands are the left and right pointers, and each move discards a bag that cannot bring the total closer.
After sorting, fix the first number nums[i]. The rest of the problem becomes a pair search: find two later numbers whose sum is closest to target - nums[i]. A converging Two Pointers scan solves that pair search in linear time, because the sorted order tells you which pointer to move.
Recognise this pattern by its shape. You see a sorted array, a target sum, and a question about a fixed-size group of values. Sorting followed by converging pointers is the standard answer for 3Sum, 3Sum Closest and Two Sum II.
Worked example
Input: nums = [-1, 2, 1, -4], target = 1 Output: 2 Explanation: Four triples exist. Their sums are 2, -3, -4 and -1. The sum 2 is 1 away from the target, and no other triple is that close, so 2 is the answer.
Approach 1: Brute force
Try every triple of distinct positions. For each triple, compute its sum and keep the sum whose distance to the target is smallest. The loops never use the sorted order, so every triple gets checked, and most of the work lands far from the target.
Steps
- Set
bestto the sum of the first three numbers. - Loop
ifrom 0 to n - 1. - Inside that, loop
jfrom i + 1 to n - 1. - Inside that, loop
kfrom j + 1 to n - 1. - Compare the distance |target - sum| with the best distance. Keep the sum that is closer.
- Return
best.
Dry run
Start with best = -1 + 2 + 1 = 2, which is distance 1 from the target.
| Triple (indices) | Values | Sum | Distance | Best after |
|---|---|---|---|---|
| (0, 1, 2) | -1, 2, 1 | 2 | 1 | 2 |
| (0, 1, 3) | -1, 2, -4 | -3 | 4 | 2 |
| (0, 2, 3) | -1, 1, -4 | -4 | 5 | 2 |
| (1, 2, 3) | 2, 1, -4 | -1 | 2 | 2 |
No later triple gets closer than distance 1, so the trace ends at 2.
Complexity
| Time | O(n^3) |
|---|---|
| Space | O(1) |
Let n be the length of nums. The loops pick i < j < k, which gives n(n-1)(n-2)/6 triples, so the work is proportional to n^3. Each triple does constant work: one sum, two absolute values and one comparison. The code stores only best and the three indices, so the extra space is O(1).
PythonTested in our runner
from typing import List, Optional
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
n = len(nums)
best = nums[0] + nums[1] + nums[2]
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
s = nums[i] + nums[j] + nums[k]
if abs(target - s) < abs(target - best):
best = s
return bestJavaTested in our runner
class Solution {
public int threeSumClosest(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 s = nums[i] + nums[j] + nums[k];
if (Math.abs(target - s) < Math.abs(target - best)) {
best = s;
}
}
}
}
return best;
}
}C++Tested in our runner
using namespace std;
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int n = nums.size();
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 s = nums[i] + nums[j] + nums[k];
if (abs(target - s) < abs(target - best)) {
best = s;
}
}
}
}
return best;
}
};JavaScriptTested in our runner
var threeSumClosest = function(nums, target) {
const n = nums.length;
let best = nums[0] + nums[1] + nums[2];
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
for (let k = j + 1; k < n; k++) {
const s = nums[i] + nums[j] + nums[k];
if (Math.abs(target - s) < Math.abs(target - best)) {
best = s;
}
}
}
}
return best;
};GoTested in our runner
func threeSumClosest(nums []int, target int) int {
n := len(nums)
best := nums[0] + nums[1] + nums[2]
abs := func(x int) int { if x < 0 { return -x }; return x }
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
for k := j + 1; k < n; k++ {
s := nums[i] + nums[j] + nums[k]
if abs(target-s) < abs(target-best) { best = s }
}
}
}
return best
}C#Tested in our runner
public class Solution {
public int threeSumClosest(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 s = nums[i] + nums[j] + nums[k];
if (Math.Abs(target - s) < Math.Abs(target - best)) {
best = s;
}
}
}
}
return best;
}
}The Converging (Sorted Array Target Sum) infographic is part of Pro
A one-page visual of the pattern: when it applies, the steps and the invariant to keep.
Unlock the infographicSolution pattern
Converging (Sorted Array Target Sum)
Part of Two Pointers
Approach 2: Sort, then converging two pointersOptimalConverging (Sorted Array Target Sum)
What's slow: the brute force checks about n^3 / 6 triples, and nearly all of them are far from the target. It never uses the fact that nearby values are grouped together after sorting.
The insight that fixes it: after sorting, fix i and search the pairs to its right with left at i + 1 and right at the last index. If the sum is below the target, any pair using the same left with a smaller right has an even smaller sum, so left must move right. If the sum is above the target, any pair using the same right with a larger left has an even larger sum, so right must move left.
Each move throws away one index that cannot beat the current best. That means each first number needs only a linear scan, and the whole search takes O(n^2) after the sort.
Steps
- Sort
numsin ascending order. - Seed
bestwith the sum of the first three sorted values. - Loop
ifrom 0 to n - 3. - Set
leftto i + 1 andrightto n - 1. - While
left < right, compute the sum. Keep it if its distance to the target is smaller than the best distance. - If the sum equals the target, return it. If the sum is below the target, move
leftright. Otherwise moverightleft. - After all values of
iare checked, returnbest.
Dry run
The array sorts to [-4, -1, 1, 2]. The table tracks the state after each step. Distance means |target - sum| with target = 1.
| Step | i | left | right | Sum | Distance | Best | Action |
|---|---|---|---|---|---|---|---|
| 0 | sort, seed | - | - | - | - | -4 | Array is [-4, -1, 1, 2] |
| 1 | 0 | 1 | 3 | -3 | 4 | -3 | Sum is below 1, move left right |
| 2 | 0 | 2 | 3 | -1 | 2 | -1 | Sum is below 1, move left right |
| 3 | 0 | 3 | 3 | - | - | -1 | Left equals right, next i |
| 4 | 1 | 2 | 3 | 2 | 1 | 2 | Sum is above 1, move right left |
| 5 | 1 | 2 | 2 | - | - | 2 | Left equals right, loop ends |
The loop ends with best = 2, which matches the expected output.
Complexity
| Time | O(n^2) |
|---|---|
| Space | O(1) beyond the sort |
Let n be the length of nums. Sorting costs O(n log n), and the outer loop runs about n - 2 times. For a fixed i, left and right only move toward each other, so they take at most n - i - 1 steps in total. Summing over all i gives about n^2 / 2 steps, so the scan is O(n^2), and the whole algorithm is O(n^2) because n^2 dominates n log n. Extra space is constant for the pointers and best, plus whatever stack or buffer the sort uses.
PythonTested in our runner
from typing import List, Optional
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
arr = sorted(nums) # copy, so the caller's list is untouched
n = len(arr)
best = arr[0] + arr[1] + arr[2]
for i in range(n - 2):
left, right = i + 1, n - 1
while left < right:
s = arr[i] + arr[left] + arr[right]
if abs(target - s) < abs(target - best):
best = s
if s == target:
return s
if s < target:
left += 1
else:
right -= 1
return bestJavaTested in our runner
import java.util.*;
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int n = nums.length;
int best = nums[0] + nums[1] + nums[2];
for (int i = 0; i < n - 2; i++) {
int left = i + 1;
int right = n - 1;
while (left < right) {
int s = nums[i] + nums[left] + nums[right];
if (Math.abs(target - s) < Math.abs(target - best)) {
best = s;
}
if (s == target) {
return s;
}
if (s < target) {
left++;
} else {
right--;
}
}
}
return best;
}
}C++Tested in our runner
using namespace std;
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int n = nums.size();
int best = nums[0] + nums[1] + nums[2];
for (int i = 0; i < n - 2; ++i) {
int left = i + 1;
int right = n - 1;
while (left < right) {
int s = nums[i] + nums[left] + nums[right];
if (abs(target - s) < abs(target - best)) {
best = s;
}
if (s == target) {
return s;
}
if (s < target) {
++left;
} else {
--right;
}
}
}
return best;
}
};JavaScriptTested in our runner
var threeSumClosest = function(nums, target) {
nums.sort((a, b) => a - b);
const n = nums.length;
let best = nums[0] + nums[1] + nums[2];
for (let i = 0; i < n - 2; i++) {
let left = i + 1;
let right = n - 1;
while (left < right) {
const s = nums[i] + nums[left] + nums[right];
if (Math.abs(target - s) < Math.abs(target - best)) {
best = s;
}
if (s === target) {
return s;
}
if (s < target) {
left++;
} else {
right--;
}
}
}
return best;
};GoTested in our runner
import "sort"
func threeSumClosest(nums []int, target int) int {
sort.Ints(nums)
n := len(nums)
best := nums[0] + nums[1] + nums[2]
abs := func(x int) int { if x < 0 { return -x }; return x }
for i := 0; i < n-2; i++ {
left, right := i+1, n-1
for left < right {
s := nums[i] + nums[left] + nums[right]
if abs(target-s) < abs(target-best) { best = s }
if s == target { return s }
if s < target { left++ } else { right-- }
}
}
return best
}C#Tested in our runner
public class Solution {
public int threeSumClosest(int[] nums, int target) {
Array.Sort(nums);
int n = nums.Length;
int best = nums[0] + nums[1] + nums[2];
for (int i = 0; i < n - 2; i++) {
int left = i + 1;
int right = n - 1;
while (left < right) {
int s = nums[i] + nums[left] + nums[right];
if (Math.Abs(target - s) < Math.Abs(target - best)) {
best = s;
}
if (s == target) {
return s;
}
if (s < target) {
left++;
} else {
right--;
}
}
}
return best;
}
}Common mistakes
- Comparing raw sums with
if s < bestinstead of distances. The result can sit far from the target. Compareabs(target - s)withabs(target - best). - Seeding
best = 0with a fixed value. For[1, 1, 1]and target 100 the answer is 3, and 0 is never a reachable sum. Seedbestwith the sum of a real triple, such as the first three values. - Writing
right = ninstead ofright = n - 1. The first read ofnums[right]falls off the end of the array. Keeprighton the last valid index. - Moving the wrong pointer, as in
if s < target: right -= 1. A sum below the target needs a larger value, soleftmoves right. Movingrightleft only lowers the sum further. - Reusing indices in the brute force loops, such as
for j in range(n)inside the loop overi. That counts one element twice. Startjati + 1andkatj + 1. - Skipping the sort, or sorting after the pointer loop starts. The pointer moves depend on sorted order, so the scan can miss the closest triple.
Edge cases
- Array of length 3, such as
[5, 9, 1]with target 0. There is only one triple, so the answer is its sum, 15, whatever the target. - All values equal, such as
[0, 0, 0]with target 1. Every triple sums to 0, so the answer is 0. - Target below every possible sum, such as
[1, 2, 3, 4]with target -100. The closest sum is the smallest triple, 1 + 2 + 3 = 6. - Target above every possible sum, such as
[1, 2, 3, 4]with target 100. The closest sum is the largest triple, 2 + 3 + 4 = 9. - Exact match early in the scan, such as
[-1, 2, 1, -4]with target 2. The triple (-1, 2, 1) sums to 2, so the algorithm returns 2 as soon as it finds it. - Duplicates with negatives, such as
[-1, -1, -1, 2]with target 0. The triples sum to -3 and 0, so the answer is 0. Duplicate values need no special handling here.
Follow-ups interviewers ask
- What if the array is already sorted?
- Skip the sort, which saves O(n log n) work. The pointer scan still costs O(n^2), so the overall bound stays the same and only the constant factor changes. The brute force cannot use the sorted order in the same way, so it stays O(n^3).
- Can you do it in O(1) extra space?
- The pointers and
bestalready use O(1) extra space. The sort is the part that matters. Heapsort sorts in place with O(1) extra space, but it is slower in practice. Python's sort and Java's object sorts use O(n) buffer space in the worst case, and Java's primitive sort uses O(log n) stack space. - What if the array does not fit in memory?
- Sort the data with an external merge sort, which writes a sorted file in chunks and merges them. Each value of
ithen needs one pass that reads from both ends of the sorted file with two cursors. The work becomes I/O bound, with about n sequential passes, so read the file in large buffered blocks to keep the passes cheap.
3Sum Closest FAQ
What is the time complexity of 3Sum Closest?
The sorted two pointer solution runs in O(n^2) time, where n is the array length. The sort costs O(n log n), and the scan over all first numbers costs O(n^2) in total. The brute force triple loop is O(n^3).
Why use two pointers for 3Sum Closest?
Sorting makes the pair search monotone. When the sum is below the target, the current right cannot help with this left, so left moves right. Each move discards one candidate, which lets every first number finish in linear time.
Can 3Sum Closest be solved in O(1) extra space?
Partly. The pointers and the best sum use O(1) extra space, but the sort may not. Heapsort keeps the sort at O(1) extra space, while typical library sorts use O(log n) or O(n) extra space. If the space bound is strict, use heapsort.
Is 3Sum Closest the same as 3Sum?
No. 3Sum looks for triples that sum to exactly zero and must skip duplicate triples in the output. 3Sum Closest looks for the single sum nearest a target, so it needs no duplicate handling.
Does Python's sort change the input list in 3Sum Closest?
Yes, nums.sort() sorts the caller's list in place. sorted(nums) returns a new list and leaves the input alone. Both give the same answer, but use sorted if the caller reuses the list.
Asked at
See which companies ask this — Pro
Related problems
- 3Sum · same technique: Converging (Sorted Array Target Sum)
- Container With Most Water · same technique: Converging (Sorted Array Target Sum)
- Two Sum II - Input Array Is Sorted · same technique: Converging (Sorted Array Target Sum)
- 4Sum · same technique: Converging (Sorted Array Target Sum)
- Boats to Save People · same technique: Converging (Sorted Array Target Sum)
- Trapping Rain Water · next harder, same pattern
- Sort Colors · same pattern: Two Pointers
- Longest Palindromic Substring · same pattern: Two Pointers
- Remove Nth Node From End of List · same pattern: Two Pointers
- Find the Duplicate Number · same pattern: Two Pointers