# 3Sum Closest LeetCode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Bloomberg Cisco Facebook Google Microsoft Oracle Rubrik Tesla Uber VMware
CapitalOne Goldmann Sachs QualitricsViews 25

Table of Contents

## Problem Statement

3Sum Closest LeetCode Solution – 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.

```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).```

## Explanation

Brute-force: O(N^3)

• The brute force solution will be O(N^3). We end up testing every subset and updating the closest sum in every iteration.

Two Pointer Solution: O(N^2)

The question is similar to 3Sum where we would fix one element and find the other two using a binary search.

1)sort the array and Traverse around the array until nums.length-2 as we are using two pointer approach.
2)loop until two pointers don’t collide.
3)If the target is found no need to search anymore, So make flag 0
4)if the found sum is greater than the target, as the array is sorted, decrement the end to make the sum reach the target.
5)if the found sum is less than the target, as the array is sorted, increment the start to make a sum to reach the target.
6)if the sum is less than the closest sum found till then, update the closest.

## Code

### C++ Code for 3Sum Closest

```class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
if(nums.size() < 3) return 0;
int closest = nums[0]+nums[1]+nums[2];
sort(nums.begin(), nums.end());
for(int first = 0 ; first < nums.size()-2 ; ++first) {
if(first > 0 && nums[first] == nums[first-1]) continue;
int second = first+1;
int third = nums.size()-1;
while(second < third) {
int curSum = nums[first]+nums[second]+nums[third];
if(curSum == target) return curSum;
if(abs(target-curSum)<abs(target-closest)) {
closest = curSum;
}
if(curSum > target) {
--third;
} else {
++second;
}
}
}
return closest;
}
};```

### Java Code for 3Sum Closest

```class Solution {
public int threeSumClosest(int[] nums, int target) {
int result=nums[0]+nums[1]+nums[nums.length-1];
Arrays.sort(nums);
for (int i=0;i<nums.length-2;i++) {
int start=i+1,end=nums.length-1;
while(start<end) {
int sum=nums[i]+nums[start]+nums[end];
if(sum>target) end--;
else start++;
if (Math.abs(sum-target)<Math.abs(result-target)) result=sum;
}
}
return result;
}
}```

### Python Code for 3Sum Closest

```class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
diff = float('inf')
nums.sort()
for i, num in enumerate(nums):
lo, hi = i + 1, len(nums) - 1
while (lo < hi):
sum = num + nums[lo] + nums[hi]
if abs(target - sum) < abs(diff):
diff = target - sum

if sum < target:
lo += 1
else:
hi -= 1
if diff == 0:
break

return target - diff```

O(n^2)

O(1)

Translate »