3Sum Closest LeetCode Solution

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