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).
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; }}Video 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.