LeetCode - 3Sum closest
Problem statement
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.
Problem statement taken from: https://leetcode.com/problems/3sum-closest
Example 1:
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).
Example 2:
Input: nums = [0, 0, 0], target = 1
Output: 0
Constraints:
- 3 <= nums.length <= 1000
- -1000 <= nums[i] <= 1000
- -10^4 <= target <= 10^4
Explanation
Brute force approach
A simple approach to solving the problem is to explore all the subsets of size 3 and keep a track of the difference between target and the sum of this subset. Then return the subset whose difference between sum and target is minimum.
C++ implementation of the above approach looks like this:
for (int i = 0; i < arr.size() ; i++)
{
for(int j =i + 1; j < arr.size(); j++)
{
for(int k =j + 1; k < arr.size(); k++)
{
//update the closestSum
if(abs(x - closestSum) > abs(x - (arr[i] + arr[j] + arr[k])))
closestSum = (arr[i] + arr[j] + arr[k]);
}
}
}
return closestSumSince we are using three nested loops, the time complexity of the above approach is O(N^3) and no extra space is required the space complexity is O(1).
Two pointer technique
By sorting the array, we can improve the efficiency of the algorithm. Once the array is sorted, we can use the two-pointer technique.
We traverse the array and fix the first element of the triplet. We use the two-pointer algorithm to find the closest number to target - nums[i]. Update the closest sum. Since the two-pointer takes linear time, it is better than a nested loop.
Algorithm
- if nums.size < 3
- return 0
- sort(nums.begin(), nums.end())
- set i = 0, minDiff = INT_MAX
- initialize sum
- loop while i < nums.size() - 2
- set left = i + 1
- set right = nums.size() - 1
- loop while right > left
- set temp = nums[i] + nums[left] + nums[right]
- set diff = abs(temp - target)
- if diff == 0
- return target
- if diff < minDiff
- minDiff = diff
- sum = temp
- if temp < target
- left++
- else
- right++
- loop end
- i++
- loop end
- return sum
C++ solution
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
if(nums.size() < 3){
return 0;
}
sort(nums.begin(), nums.end());
int i = 0;
int sum, minDiff = INT_MAX;
while(i < nums.size() - 2){
int left = i + 1;
int right = nums.size() - 1;
while(right > left){
int temp = nums[i] + nums[left] + nums[right];
int diff = abs(temp - target);
if(diff == 0){
return target;
}
if(diff < minDiff){
minDiff = diff;
sum = temp;
}
if(temp < target){
left++;
}
else{
right--;
}
}
i++;
}
return sum;
}
};Golang solution
const MaxUint = ^uint(0)
const MaxInt = int(MaxUint >> 1)
func absInt(x int) int{
if x < 0 {
return x*-1
}
return x
}
func threeSumClosest(nums []int, target int) int {
numsLength := len(nums)
if numsLength < 3 {
return 0
}
sort.Ints(nums)
i, sum := 0, 0
minDiff := MaxInt
for i < numsLength - 2 {
left := i + 1
right := numsLength - 1
for right > left {
temp := nums[i] + nums[left] + nums[right]
diff := absInt(temp - target)
if diff == 0 {
return target
}
if diff < minDiff {
minDiff = diff
sum = temp
}
if temp < target {
left++
} else {
right--
}
}
i++
}
return sum
}Javascript solution
var threeSumClosest = function(nums, target) {
if(nums.length < 3) {
return 0;
}
nums.sort();
let i = 0, minDiff = Number.MAX_VALUE;
let sum;
while( i < nums.length - 2 ){
let left = i + 1;
let right = nums.length - 1
while( right > left ){
let temp = nums[i] + nums[left] + nums[right];
let diff = Math.abs(temp - target);
if( diff == 0 ){
return target;
}
if( diff < minDiff ){
minDiff = diff;
sum = temp;
}
if( temp < target ){
left++;
} else {
right--;
}
}
i++;
}
return sum;
};Dry Run
Let's dry-run our algorithm to see how the solution works.
Input: nums = [-1, 2, 1, -4], target = 1
Step 1: if nums.size() < 3
4 < 3
false
Step 2: sort(nums.start(), nums.end())
- [-4, -1, 1, 2]
Step 3: int i = 0;
int sum, minDiff = INT_MAX;
Step 4: loop while i < nums.size() - 2
0 < 4 - 2
0 < 2
true
left = i + 1
= 0 + 1
= 1
right = nums.size() - 1
= 4 - 1
= 3
loop while right > left
3 > 1
true
temp = nums[i] + nums[left] + nums[right]
= nums[0] + nums[1] + nums[3]
= -4 + -1 + 2
= -3
diff = abs(temp - target)
= abs(-3 - 1)
= abs(-4)
= 4
if diff == 0
4 == 0
false
if diff < minDiff
4 < INT_MAX
true
minDiff = diff
= 4
sum = temp
= -3
if temp < target
-3 < 4
true
left++
left = 2
loop while right > left
3 > 2
true
temp = nums[i] + nums[left] + nums[right]
= nums[0] + nums[2] + nums[3]
= -4 + 1 + 2
= -1
diff = abs(temp - target)
= abs(-1 - 1)
= abs(-2)
= 2
if diff == 0
2 == 0
false
if diff < minDiff
2 < 4
true
minDiff = diff
= 2
sum = temp
= -1
if temp < target
-1 < 4
true
left++
left = 3
loop while right > left
3 > 3
false
i++
i = 1
Step 5: loop while i < nums.size() - 2
1 < 4 - 2
1 < 2
true
left = i + 1
= 1 + 1
= 2
right = nums.size() - 1
= 4 - 1
= 3
loop while right > left
3 > 2
true
temp = nums[i] + nums[left] + nums[right]
= nums[1] + nums[2] + nums[3]
= -1 + 1 + 2
= 2
diff = abs(temp - target)
= abs(2 - 1)
= abs(1)
= 1
if diff == 0
1 == 0
false
if diff < minDiff
1 < 2
true
minDiff = diff
= 1
sum = temp
= 2
if temp < target
2 < 4
true
left++
left = 3
loop while right > left
3 > 3
false
i++
i = 2
Step 6: loop while i < nums.size() - 2
2 < 4 - 2
2 < 2
false
Step 7: return sum
return 2
So the answer is 2.