16. 3Sum Closest
Asked at Google
Difficulty
Medium
Time
O(n^2)
Space
O(1)
Pattern
Array
Companies
1
Problem
You get an integer array nums and an integer target. Pick three elements at three different positions in the array. Add them up. Among all possible choices, find the sum that is closest to target in absolute distance, and return that sum.
"Closest" means the smallest value of |sum - target|. The three indices must be distinct, but the values themselves may repeat (for example, [0,0,0] is fine). You may assume exactly one answer exists, so there is no tie to break.
A fast way to solve this: sort the array first. Then fix one element with an outer loop, and use two pointers (left and right) to scan the remaining part. If the current sum is too small, move left up; if it is too big, move right down. This avoids checking all triplets.
Pick three positions, get close to target
Constraints
- ●
3 <= nums.length <= 500 - ●
-1000 <= nums[i] <= 1000 - ●
-10^4 <= target <= 10^4
Examples
nums = [-1,2,1,-4], target = 12nums = [0,0,0], target = 10Asked At
1 companies| 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.
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.
Sort, fix one, move two pointers
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
O(n^2) timedef 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 runs in O(n^2) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.