A n^2 Solution, Can we do better ?


  • 84
    V

    Here is a solution in Order(N^2). I got help from this post on
    [stackoverflow][1]

    Can we improve this time complexity ?

    int threeSumClosest(vector<int> &num, int target) {        
        vector<int> v(num.begin(), num.end()); // I didn't wanted to disturb original array.
        int n = 0;
        int ans = 0;
        int sum;
        
        sort(v.begin(), v.end());
        
        // If less then 3 elements then return their sum
        while (v.size() <= 3) {
            return accumulate(v.begin(), v.end(), 0);
        }
        
        n = v.size();
        
        /* v[0] v[1] v[2] ... v[i] .... v[j] ... v[k] ... v[n-2] v[n-1]
         *                    v[i]  <=  v[j]  <= v[k] always, because we sorted our array. 
         * Now, for each number, v[i] : we look for pairs v[j] & v[k] such that 
         * absolute value of (target - (v[i] + v[j] + v[k]) is minimised.
         * if the sum of the triplet is greater then the target it implies
         * we need to reduce our sum, so we do K = K - 1, that is we reduce
         * our sum by taking a smaller number.
         * Simillarly if sum of the triplet is less then the target then we
         * increase out sum by taking a larger number, i.e. J = J + 1.
         */
        ans = v[0] + v[1] + v[2];
        for (int i = 0; i < n-2; i++) {
            int j = i + 1;
            int k = n - 1;
            while (j < k) {
                sum = v[i] + v[j] + v[k];
                if (abs(target - ans) > abs(target - sum)) {
                    ans = sum;
                    if (ans == target) return ans;
                }
                (sum > target) ? k-- : j++;
            }
        }
        return ans;
    }
    

    Edit:Thanks @thr for pointing out that. I have corrected it and also renamed 'mx' by 'ans'.
    [1]: http://stackoverflow.com/questions/2070359/finding-three-elements-in-an-array-whose-sum-is-closest-to-an-given-number


  • 10
    S

    As far as I know, O(N^2) is the best solution of this problem.


  • 0
    E

    good solution!


  • 1
    W

    neat solution. much better than mine


  • 12
    H

    No there isn't. Proof by contradiction:

    If we had subquadratic solution to this problem then we could solve all instances of 3SUM problem with the same complexity (subquadratic). but lower bound of 3SUM problem is O(n^2)


  • -6
    S

    I am guessing my soluton is O(nlgn). Tell me if I am wrong?

    public class Solution {
        public int binarySearchClosest(int[] num, int target, int start, int end){
            if(end == start + 1){
                if(target - num[start] >= num[end] - target) return end;
                else return start;
            }
            else if(end <= start) return start;
            int mid = (start + end)/2;
            if(num[mid] == target) return mid;
            else if(num[mid] < target)  return binarySearchClosest(num, target, mid, end);
            else return binarySearchClosest(num, target, start, mid);
        }
        
        public int threeSumClosest(int[] num, int target) {
            Arrays.sort(num);
            int start = 0, end = num.length - 1;
            int sumValue = 0;
            int offset = Integer.MAX_VALUE;
            while(start < end - 1){
                int item = target - num[start]- num[end];
                int idx = binarySearchClosest(num, item, start + 1, end - 1);
                if(idx == start) idx = start+1;
                else if(idx == end) idx = end -1;
                if(num[start] + num[end] + num[idx] != target){
                    int oldOfset = offset;
                    offset = Math.min(offset, Math.abs(target - num[start] - num[end] - num[idx]));
                    if(offset != oldOfset){
                        sumValue = num[start] + num[idx] + num[end];
                    }
                }
                if(num[start] + num[end] + num[idx] > target) end--;
                else if(num[start] + num[end] + num[idx] < target) start++;
                else {sumValue = target;break;}
            }
            return sumValue;
        }
    }

  • 3
    V

    Your logic is Incorrect. For eg: S ={1,2,9,28,29} T=40, Your output is 39, but correct output is 40.

    More precisely your logic of Binarysearch is wrong. because say even if num[mid] < target, it might be possible that there is some value in left subarray which is more closer to target than all values in right subarray, so in order to find closest value we need to check both the subarrays, i.e. left and right thus leading to an O(N^2) solution. ;)

    PS:Did this solution got Accepted ??


  • 0
    S

    please see my edit. And yes the solution got accepted without the change and also with the change.


  • 0
    T

    if you let mx=0 at first. what if the target is zero and the nearest solution is not zero?


  • 0
    V

    @thr: yes you are right. My mistake was that I assumed that there will always be a triplet with sum Zero, which is a big mistake. Now I have corrected that mistake by initialising 'ans' with sum of first three elements.


  • 0
    N

    I got the same solution!


  • 0
    T

    good solution, thx!


  • 0
    B

    thx so much@@@!!!


  • 0
    N

    I think your solution does not work for this case:
    num = {1,20,30,60,100};
    target = 150;

    Your output is 161, but it should be 150.


  • 0
    M

    Also, you can optimized this solution, if the distance of abs(target - num(i,j,k)) < abs(target - num(i,j-1,k)) or abs(target - num(i,j,k-1)), break the current while loop.


  • 0
    H

    Why not initialize ans=-2^32?


  • 0
    V

    @mayijie88: Yes you can do that, just a little bit of some more coding effort. ;)


  • 0
    V

    @huangbow:

    1. ans is the sum of the triplet we have currently chosen. So initially we havn't chosen anything so it doesn't makes any sense to use that value.
    2. You will have to take care of overflow issues.
    3. "while(j < k)" loop will automatically update 'ans' value on 1st iteration.

  • 0
    C
    This post is deleted!

  • 0

    Clear solution with nice comments. Thank you for your sharing!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.