3Sum Closest
- mosesg1123
- May 26, 2025
- 4 min read
This is a great warm-up for array and two-pointer problems. It’s similar to the classic 3Sum, but instead of finding a triplet that adds to a specific number, we need the closest possible sum. This introduces an optimization twist that requires careful comparison and pointer movement, making it an excellent real-world scenario—think of situations where you need to get as close as possible to a threshold value without hitting it exactly, such as budget planning or resource allocation.
Problem Statement
Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers.
You may assume that each input would have exactly one solution.
Example:
Input: nums = [-1, 2, 1, -4], target = 1
Output: 2
Explanation: The sum that is closest to 1 is 2 (-1 + 2 + 1).
1. Clarify Requirements Before Jumping Into Code
We’re given an array of integers and a target number. We need to return the sum of a triplet (three numbers from the array) that is closest to the target.
Each number in the triplet must come from a different index.
Only one solution is guaranteed.
Return the actual sum, not the indices or the numbers.
No sorting constraints
Duplicates are allowed.
We’re optimizing for proximity, not exact matches.
2. Identify the Category of the Question
This is a two-pointer problem layered on top of the 3Sum pattern. It falls into the category of:
Sorting + Two Pointers
Optimization over brute force
Subset Sum Variants
When we hear “3 elements” and “closest to a target”, the 3Sum pattern is immediately useful, and “closest” usually signals the need for tracking deltas.
3. Consider a Brute‑Force Approach to Understand the Problem
The brute-force way would be:
Try all combinations of 3 elements.
Calculate the sum.
Track the one closest to the target.
That means three nested loops.
Time Complexity: O(n³)
Space Complexity: O(1)
Totally doable for very small arrays, but way too slow for larger ones.
4. Brainstorm More Solutions
This sounds very similar to the 3Sum problem - with a minor modification.
So let's start by reviewing the solution for the 3Sum problem (check out the post if you want a more thorough walkthrough):
Step 1: Sort the array.
Step 2: Loop through each element i as the first number of the triplet.
Step 3: For each element i, use two pointers:
left = i + 1
right = n - 1
While left < right, compute the current sum of the three numbers.
If it’s equal to the target, store it.
If the sum is less than the target, move the left pointer to increase the sum.
If the sum is greater than the target, move the right pointer to decrease the sum.
So now that I remember the specifics of the solution for the 3Sum problem, what modifications would I need to make in order to make it work for this problem?
Rather than check for sums equal to the target, instead I need to track the sum that is closest to my target. If I find a new sum that is closest, I update my result.
Time Complexity: O(n²)
Space Complexity: O(1)
And that's it! All we had to do was make a minor modification to the solution of a problem we've already seen!
5. Discuss Trade‑Offs Between Your Solutions
Approach | Time Complexity | Space Complexity | Pros | Cons |
Brute Force | O(n³) | O(1) | Easy to implement | Too slow for large input |
Two Pointers + Sort | O(n²) | O(1) | Efficient, standard pattern | Requires careful pointer control |
6. Write Pseudocode to Structure Your Thoughts
sort(nums)
closest = sum of first 3 elements
for i from 0 to nums.length - 2:
left = i + 1
right = nums.length - 1
while left < right:
currentSum = nums[i] + nums[left] + nums[right]
if abs(currentSum - target) < abs(closest - target):
closest = currentSum
if currentSum < target:
left += 1
else:
right -= 1
return closest
7. Consider Edge Cases
Input has exactly 3 elements → should just return their sum.
All numbers are the same.
Target is way outside the range of possible sums.
Our algorithm handles all of these fine. We always initialize closest to the sum of the first 3 elements, so we always have a valid return.
8. Write Full Code Syntax
public class ThreeSumClosest {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int closest = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.length - 2; i++) {
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (Math.abs(sum - target) < Math.abs(closest - target)) {
closest = sum;
}
if (sum < target) {
left++;
} else {
right--;
}
}
}
return closest;
}
}
9. Test Your Code
public static void main(String[] args) {
ThreeSumClosest solution = new ThreeSumClosest();
System.out.println(solution.threeSumClosest(new int[]{-1, 2, 1, -4}, 1)); // 2
System.out.println(solution.threeSumClosest(new int[]{0, 0, 0}, 1)); // 0
System.out.println(solution.threeSumClosest(new int[]{1, 1, 1, 0}, -100)); // 2
System.out.println(solution.threeSumClosest(new int[]{1, 2, 4, 8, 16}, 13)); // 13
System.out.println(solution.threeSumClosest(new int[]{1, 1, -1, -1, 3}, -1)); // -1
}
10. Key Lessons to Remember for Future Questions
Starting with the solution of a simpler but related problem is a great way to get started!
Optimization problems often follow the structure of known patterns (like 3Sum here).
Tracking a running “best candidate” is a useful approach when exact matching isn’t required.
Sorting plus two pointers can reduce a cubic solution to quadratic.
Pay attention to pointer movement rules—they’re subtle but key to correctness and efficiency.
This problem is a classic example of using controlled iteration with sorted data to solve a target proximity challenge. Mastering it lays the foundation for more advanced greedy and binary search techniques.
Good Luck and Happy Coding!
Comments