3Sum Closest
MedPrompt
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 1:
Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).Example 2:
Input: nums = [0,0,0], target = 1
Output: 0
Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).
Constraints:
3 <= nums.length <= 500-1000 <= nums[i] <= 1000-104 <= target <= 104
Approaches
2 approaches with complexity analysis and trade-offs.
The brute-force approach is the most straightforward way to solve the problem. It involves checking every possible combination of three distinct numbers from the input array, calculating their sum, and keeping track of the sum that is closest to the given target.
Algorithm
- Initialize a variable
closestSumto the sum of the first three elements of the array. - Use three nested loops to iterate through all unique triplets of indices
(i, j, k)such thati < j < k. - For each triplet, calculate the
currentSum = nums[i] + nums[j] + nums[k]. - Compare the absolute difference
|target - currentSum|with the absolute difference|target - closestSum|. - If the
currentSumis closer to thetarget, updateclosestSumtocurrentSum. - After iterating through all possible triplets, return
closestSum.
Walkthrough
This method systematically explores all possible triplets in the array. We use three nested loops to select three distinct elements. The outer loop runs from the first element to the third-to-last, the middle loop from the element after the outer loop's current element to the second-to-last, and the inner loop from the element after the middle loop's current element to the last.
Inside the innermost loop, we compute the sum of the three selected numbers. We then find the absolute difference between this sum and the target. We maintain a variable, closestSum, initialized with the sum of the first three elements. If the current triplet's sum is closer to the target than closestSum, we update closestSum. After checking all triplets, closestSum will hold the required result.
class Solution { public int threeSumClosest(int[] nums, int target) { int n = nums.length; // Initialize with the sum of the first three elements as a baseline int closestSum = nums[0] + nums[1] + nums[2]; for (int i = 0; i < n - 2; i++) { for (int j = i + 1; j < n - 1; j++) { for (int k = j + 1; k < n; k++) { int currentSum = nums[i] + nums[j] + nums[k]; // If the current sum is closer to the target, update closestSum if (Math.abs(target - currentSum) < Math.abs(target - closestSum)) { closestSum = currentSum; } } } } return closestSum; }}Complexity
Time
O(n^3)
Space
O(1)
Trade-offs
Pros
Simple to understand and implement.
It does not require any modification of the input array, such as sorting.
Cons
Extremely inefficient due to its cubic time complexity.
Will likely result in a 'Time Limit Exceeded' error on most coding platforms for larger inputs, although it might pass given the problem's constraints (n <= 500).
A much more efficient approach involves sorting the array first. After sorting, we can iterate through the array, and for each element, use the two-pointer technique on the rest of the array to find the other two elements. The two pointers, one starting from the element after the current one and the other from the end of the array, converge towards each other, efficiently finding the triplet sum closest to the target.
Algorithm
- First, sort the input array
nums. - Initialize a variable
closestSumwith the sum of the first three elements. - Iterate through the array with a for loop, fixing one element
nums[i]at a time. - For each
nums[i], use two pointers,leftstarting ati + 1andrightstarting at the end of the array (n - 1). - While
leftis less thanright, calculate thecurrentSum = nums[i] + nums[left] + nums[right]. - If
currentSumis exactly equal totarget, returntargetimmediately. - Compare the absolute difference
|target - currentSum|with|target - closestSum|. If the current sum is closer, updateclosestSum. - If
currentSumis less thantarget, incrementleftto get a larger sum. - If
currentSumis greater thantarget, decrementrightto get a smaller sum. - After the loops complete, return
closestSum.
Walkthrough
The key to optimizing this problem is to sort the array first. Sorting allows us to use a more intelligent way to find the other two numbers instead of iterating through all pairs.
We iterate through the sorted array with a single loop, fixing the first number of our potential triplet, nums[i]. For each nums[i], we need to find two other numbers in the subarray nums[i+1...n-1] whose sum with nums[i] is as close to target as possible. This subproblem can be solved in linear time using two pointers.
We set a left pointer to i + 1 and a right pointer to n - 1. We then move these pointers inward based on the comparison of their sum with the target. If nums[i] + nums[left] + nums[right] is less than the target, we need a larger sum, so we increment left. If it's greater, we need a smaller sum, so we decrement right. At each step, we check if the current sum is closer to the target than our best-so-far sum and update it if necessary. This process continues until the left and right pointers cross.
import java.util.Arrays; class Solution { public int threeSumClosest(int[] nums, int target) { // Sort the array to enable the two-pointer approach Arrays.sort(nums); int n = nums.length; // Initialize closestSum with the sum of the first three elements int closestSum = nums[0] + nums[1] + nums[2]; // Iterate through the array to fix the first element of the triplet for (int i = 0; i < n - 2; i++) { int left = i + 1; int right = n - 1; // Use two pointers to find the other two elements while (left < right) { int currentSum = nums[i] + nums[left] + nums[right]; // If the exact sum is found, it's the closest possible. Return it. if (currentSum == target) { return target; } // Check if the current sum is closer to the target than the best we've found so far if (Math.abs(target - currentSum) < Math.abs(target - closestSum)) { closestSum = currentSum; } // Move pointers to get closer to the target if (currentSum < target) { left++; // Need a larger sum } else { right--; // Need a smaller sum } } } return closestSum; }}Complexity
Time
O(n^2)
Space
O(log n) to O(n)
Trade-offs
Pros
Significantly faster than the brute-force method, with a time complexity of O(n^2).
It's a standard and widely applicable pattern for solving
k-sumtype problems.
Cons
Requires modifying the input array by sorting it. If the original array must be preserved, a copy is needed, which increases space complexity to O(n).
Slightly more complex to implement than the brute-force approach.
Solutions
Solution
public class Solution { public int ThreeSumClosest(int[] nums, int target) { Array.Sort(nums); int ans = 1 << 30; int n = nums.Length; for (int i = 0; i < n; ++i) { int j = i + 1, k = n - 1; while (j < k) { int t = nums[i] + nums[j] + nums[k]; if (t == target) { return t; } if (Math.Abs(t - target) < Math.Abs(ans - target)) { ans = t; } if (t > target) { --k; } else { ++j; } } } return ans; }}class Solution {public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int ans = 1 << 30; int n = nums.length; for (int i = 0; i < n; ++i) { int j = i + 1, k = n - 1; while (j < k) { int t = nums[i] + nums[j] + nums[k]; if (t == target) { return t; } if (Math.abs(t - target) < Math.abs(ans - target)) { ans = t; } if (t > target) { --k; } else { ++j; } } } return ans; }}/** * @param {number[]} nums * @param {number} target * @return {number} */ var threeSumClosest = function (nums, target) { nums.sort((a, b) => a - b); let ans = 1 << 30; const n = nums.length; for (let i = 0; i < n; ++i) { let j = i + 1; let k = n - 1; while (j < k) { const t = nums[i] + nums[j] + nums[k]; if (t === target) { return t; } if (Math.abs(t - target) < Math.abs(ans - target)) { ans = t; } if (t > target) { --k; } else { ++j; } } } return ans; };class Solution {public: int threeSumClosest(vector<int> &nums, int target) { sort(nums.begin(), nums.end()); int ans = 1 << 30; int n = nums.size(); for (int i = 0; i < n; ++i) { int j = i + 1, k = n - 1; while (j < k) { int t = nums[i] + nums[j] + nums[k]; if (t == target) return t; if (abs(t - target) < abs(ans - target)) ans = t; if (t > target) --k; else ++j; } } return ans; }};class Solution: def threeSumClosest(self, nums: List[int], target: int) -> int: nums . sort() n = len(nums) ans = inf for i, v in enumerate(nums): j, k = i + 1, n - 1 while j < k: t = v + nums[j] + nums[k] if t == target: return t if abs(t - target) < abs(ans - target): ans = t if t > target: k -= 1 else: j += 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.