3Sum Closest
Asked at Google
Problem
Given an integer array nums and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. This problem extends 3Sum by asking you to track proximity rather than an exact match.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → |
How to Think About It
Brute force: try every combination of three elements. There are O(n³) triplets. For each, compute the sum and track the closest to target. Works but too slow for large n.
Key insight: sort the array first, then fix one element and use two pointers for the other two. This reduces it to O(n²) - same as 3Sum but with a different comparison condition.
Why two pointers work here: after sorting, for a fixed i, use left = i+1 and right = n-1. If the current sum is less than target, move left right. If greater, move right left. Track the minimum absolute difference from target throughout.
The critical difference from 3Sum: instead of looking for sum == 0, you track the closest sum to target. Update your best answer whenever |sum - target| < |best - target|. Do NOT skip duplicates the same way - you want to explore all sums.
Visual walkthrough for nums = [-1, 2, 1, -4] target = 1:
Sort: [-4, -1, 1, 2]
i=0, nums[i]=-4. left=1, right=3.
-4 + -1 + 2 = -3. |(-3)-1| = 4. best=-3. sum < target, move left.
-4 + 1 + 2 = -1. |(-1)-1| = 2. best=-1. sum < target, move left.
left meets right. Next i.
i=1, nums[i]=-1. left=2, right=3.
-1 + 1 + 2 = 2. |2-1| = 1. best=2. sum > target, move right.
left meets right. Result: 2
Edge cases: exactly three elements (return their sum), target is very large or very small, all elements are the same.
Optimal Approach
Step 1: Sort the array.
Step 2: Initialize closest = sum of first three elements.
Step 3: For each index i from 0 to n-3:
- Set left = i+1, right = n-1
- Compute current = nums[i] + nums[left] + nums[right]
- If |current - target| < |closest - target|, update closest = current
- If current < target: move left right
- If current > target: move right left
- If current == target: return target immediately (perfect match)
Walkthrough with nums = [-1, 2, 1, -4] target = 1:
- Sort: [-4, -1, 1, 2]
- i=0: -4 + (-1) + 2 = -3. |diff| = 4. Closest = -3. Move left.
- i=0: -4 + 1 + 2 = -1. |diff| = 2. Closest = -1. Move left.
- i=1: -1 + 1 + 2 = 2. |diff| = 1. Closest = 2. Move right.
- Return 2.
Time: O(n^2) - outer loop O(n), inner two-pointer O(n). Space: O(1) excluding sort space.
What Trips People Up in Real Interviews
Trying brute force O(n^3) without realizing sorting enables the two-pointer O(n^2) solution. Always sort first when working with triplets.
Skipping duplicates aggressively like in 3Sum. In 3Sum Closest, you still skip duplicate i values but you should NOT skip duplicate left/right values because different combinations can yield different sums.
Forgetting to initialize closest with the sum of the first three elements. Initializing to 0 can cause incorrect comparisons if all sums are far from target.
Not returning immediately when current == target. A sum exactly equal to target is the best possible answer - no need to continue searching.
Comparing raw sums instead of absolute differences. The closest sum might be negative while target is positive. Always use |sum - target| for comparison.
Solution Code
def threeSumClosest(nums, target):
nums.sort()
closest = nums[0] + nums[1] + nums[2]
for i in range(len(nums) - 2):
lo, hi = i + 1, len(nums) - 1
while lo < hi:
current = nums[i] + nums[lo] + nums[hi]
if abs(current - target) < abs(closest - target):
closest = current
if current < target:
lo += 1
elif current > target:
hi -= 1
else:
return target
return closestFrequently Asked Questions
What is the 3Sum Closest problem?
Given an integer array nums and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. This problem extends 3Sum by asking you to track proximity rather than an exact match.
How do you solve 3Sum Closest?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask 3Sum Closest?
3Sum Closest is asked at Google. It is a medium difficulty problem.
What are common mistakes on 3Sum Closest?
- Trying brute force `O(n^3)` without realizing sorting enables the two-pointer `O(n^2)` solution. Always sort first when working with triplets.
- Skipping duplicates aggressively like in 3Sum. In 3Sum Closest, you still skip duplicate i values but you should NOT skip duplicate left/right values because different combinations can yield different sums.
- Forgetting to initialize closest with the sum of the first three elements. Initializing to 0 can cause incorrect comparisons if all sums are far from target.
- Not returning immediately when current == target. A sum exactly equal to target is the best possible answer - no need to continue searching.
- Comparing raw sums instead of absolute differences. The closest sum might be negative while target is positive. Always use |sum - target| for comparison.