Leet 16 – 3Sum Closest

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:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

My Solution:

This seems again like Leet 3Sum – I need to find a way to get close to a certain number using combinations of 3 nums of any list.

Since the target is not positive anymore I can’t eliminate certain cases, but still using sort will help me advance along certain operations and neglect other directions that will just decrease further.

#include<bits/stdc++.h>

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        
        int diff = INT_MAX, res = 0;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size()-2;i++)
        {
            for(int j=i+1,k=nums.size()-1;j<k;)
            {
                int sum = nums[i] + nums[j] + nums[k];
                if(sum == target) return target;
                if(diff>abs(sum-target))
                {
                    res=sum;
                    diff=abs(sum-target);
                }
               (sum>target) ? k-- : j++;
            }
        }
        return res;
    }
};

Time Complexity:

O(nlog(n) +n^2) – O(nlog(n)) because I’m sorting the vectors + O(n*n) because we are traversing every vector against all other vectors and using two indexes(pointers/pivots) without this heuristic of avoiding unnecessary paths this would be an (On^3).

Space Complexity:

O(1) -Constant because I create a list of vectors, ahead of time