Solution For 3sum Closest
Problem Description:
Given an array nums of n integers 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:
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).
Solution:
To solve this problem, we can use the two-pointer approach. First, we sort the given input array. This allows us to easily traverse through all the possible values of the three numbers. We then fix the first number and move the second and third numbers such that we calculate their sum and check if it is closest to the target. We then update the closest sum so far and move the second and third numbers accordingly. We keep doing this until we have checked all possible combinations of the three numbers.
Algorithm:
- Sort the given input array nums.
- Initialize a variable res to store the closest sum so far. Set it to a large number initially.
- Traverse through the array nums from left to right. Fix the first number as the i-th number.
- Initialize two pointers, left and right. Set left to i+1 and right to n-1.
- While left < right, calculate the sum of the three numbers, i.e., nums[i] + nums[left] + nums[right].
- If the sum is equal to target, return the sum.
- If the sum is less than target, increment left.
- If the sum is greater than target, decrement right.
- Check if the absolute difference between the sum and target is less than the absolute difference between res and target.
- If yes, update res with the new sum.
- Repeat steps 5-10 until all possible combinations of the three numbers have been checked.
- Return res.
Implementation:
Here is the Python code to implement the above algorithm:
def threeSumClosest(nums: List[int], target: int) -> int:
nums.sort()
n = len(nums)
res = float(‘inf’)
for i in range(n-2):
left = i+1
right = n-1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == target:
return total
elif total < target:
left += 1
else:
right -= 1
if abs(total – target) < abs(res – target):
res = total
return res
Time Complexity:
The time complexity of the above algorithm is O(n^2), where n is the length of the input array. This is because we traverse through the array twice, once to sort the array, and then to find the closest sum. Within the second traversal, we use a two-pointer approach, which takes O(n) time.
Space Complexity:
The space complexity of the above algorithm is O(1), as we are not using any extra space. We are only using a few variables to store the closest sum, pointers, and the input array.
Step by Step Implementation For 3sum Closest
class Solution { public int threeSumClosest(int[] nums, int target) { // sort the array first Arrays.sort(nums); int closestSum = nums[0] + nums[1] + nums[2]; for (int i = 0; i < nums.length - 2; i++) { int left = i + 1; int right = nums.length - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; // update closestSum if the current sum is closer to target if (Math.abs(target - sum) < Math.abs(target - closestSum)) { closestSum = sum; } // move left or right pointer based on current sum if (sum < target) { left++; } else if (sum > target) { right--; } else { // we found an exact match, no need to continue return sum; } } } return closestSum; } }
class Solution: def threeSumClosest(self, nums, target): # Sort the array nums.sort() # Set the closest variable to the max value of an integer closest = 2147483647 # Iterate through the array for i in range(len(nums) - 2): # Set left pointer to i + 1 left = i + 1 # Set right pointer to the end of the array right = len(nums) - 1 # While the left pointer is less than the right pointer while left < right: # Set the sum to be the values of nums at indices i, left, and right sum = nums[i] + nums[left] + nums[right] # If the sum is equal to the target if sum == target: # Return the sum return sum # If the sum is less than the target if sum < target: # If the sum is closer to the target than the current value of closest if target - sum < abs(target - closest): # Set closest equal to the sum closest = sum # Increment the left pointer left += 1 # If the sum is greater than the target else: # If the sum is closer to the target than the current value of closest if sum - target < abs(target - closest): # Set closest equal to the sum closest = sum # Decrement the right pointer right -= 1 # Return the closest value return closest
var threeSumClosest = function(nums, target) { // sort the array nums.sort((a, b) => a - b); // initialize the closest value to be the first sum in the array let closest = nums[0] + nums[1] + nums[2]; // iterate through the array for (let i = 0; i < nums.length - 2; i++) { // initialize left pointer at i + 1 let left = i + 1; // initialize right pointer at end of array let right = nums.length - 1; // while the left pointer is less than the right pointer while (left < right) { // calculate the sum let sum = nums[i] + nums[left] + nums[right]; // if the sum is equal to the target, return the sum if (sum === target) { return sum; // if the sum is less than the target, move the left pointer up one } else if (sum < target) { left++; // if the sum is greater than the target, move the right pointer down one } else { right--; } // if the absolute value of the sum minus the target is less than the absolute value of the closest value minus the target if (Math.abs(sum - target) < Math.abs(closest - target)) { // set the closest value to the sum closest = sum; } } } // return the closest value return closest; };
class Solution { public: int threeSumClosest(vector& nums, int target) { int result = nums[0] + nums[1] + nums[2]; int min_diff = abs(result - target); // sort the array sort(nums.begin(), nums.end()); // fix the smallest number as nums[i] for (int i = 0; i < nums.size() - 2; i++) { // start from i + 1 int left = i + 1; // end at nums.size() - 1 int right = nums.size() - 1; // until left meets right while (left < right) { // calculate the sum int sum = nums[i] + nums[left] + nums[right]; // update the result if it's closer to the target if (abs(sum - target) < min_diff) { result = sum; min_diff = abs(sum - target); } // if the sum is too small, move left if (sum < target) { left++; } // if the sum is too large, move right else { right--; } } } return result; } };
public class Solution { public int ThreeSumClosest(int[] nums, int target) { Array.Sort(nums); int closestSum = nums[0] + nums[1] + nums[2]; for (int i = 0; i < nums.Length - 2; i++) { int left = i + 1; int right = nums.Length - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum == target) { //We found an exact match, return the sum return sum; } else if (sum < target) { //The sum is too low, increment the left pointer left++; } else { //The sum is too high, decrement the right pointer right--; } //Update closestSum if the current sum is closer to the target if (Math.Abs(sum - target) < Math.Abs(closestSum - target)) { closestSum = sum; } } } return closestSum; } }