C++ O(n log n) using sort and binary search


  • 0
    A
    1. sort nums
    2. find smallest 3Sum greater than target
    3. find largest 3Sum less than target
    4. compare answers from steps 2 and 3, return the better one.
    class Solution {
    public:
        int bin_search(vector<int>& nums, int lb, int ub, int target){
            int mid;
            while(lb <= ub){
                mid = (lb + ub) / 2;
                if(nums[mid] == target){
                    return mid;
                }
                else if(nums[mid] < target){
                    lb = mid + 1;
                }
                else if(nums[mid] > target){
                    ub = mid - 1;
                }
                else
                    throw -1;
            }
            return ub;
        }
        int closest_less_than_target(vector<int>& nums, int target){
            int i=0, j=nums.size() - 1;
            int min_poss_sum;
            int ans = accumulate(nums.begin(), nums.begin() + 3, 0);
            while(i < j){
                min_poss_sum = 2 * nums[i] + nums[j];
                if(min_poss_sum > target){
                    j--;
                }
                else{
                    int ind = bin_search(nums, i+1, j-1, target - nums[i] - nums[j]);
                    if(ind > i){
                        int cand = nums[ind] + nums[i] + nums[j];
                        if(abs(target - cand) < abs(target - ans))
                            ans = cand;
                    }
                    i++;
                }
            }
            return ans;       
        }
        
        int closest_greater_than_target(vector<int>& nums, int target){
            int i=0, j=nums.size() - 1;
            int max_poss_sum;
            int ans = accumulate(nums.end() - 3, nums.end(), 0);
            while(i < j){
                max_poss_sum = nums[i] + 2 * nums[j];
                if(max_poss_sum < target){
                    i++;
                }
                else{
                    int bs_target = target - nums[i] - nums[j];
                    int ind = bin_search(nums, i+1, j-1, bs_target);
                    if(ind <= i)
                        ind += 1;
                    
                    if(ind > i && ind < j){
                        int cand = nums[ind] + nums[i] + nums[j];
                        if(abs(target - cand) < abs(target - ans))
                            ans = cand;
                    }
                    j--;
                }
            }
            return ans;       
        }
        
        
        int threeSumClosest(vector<int>& nums, int target) {
            sort(nums.begin(), nums.end());
            int ans1 = closest_greater_than_target(nums, target);
            int ans2 = closest_less_than_target(nums, target);
            if(abs(ans1 - target) < abs(ans2 - target))
                return ans1;
            else
                return ans2;
        }
    };
    

  • 0
    L

    The sort itself is O(n^2).


  • 0
    A

    @leaper
    I believe C++ sort uses Introsort, which is a variant of Quicksort that changes to Heapsort when recursion depth reaches a certain level, and has a worst case complexity of O(n log n).


  • 0
    L

    @atruecubsfan said in C++ O(n log n) using sort and binary search:

    complexity

    Thanks! Learned more :)


  • 2
    A

    @atruecubsfan Your algorithm is wrong.
    leetcode default testcase suite doesn't cover corner cases, so you got a FAKE acceptance.
    Try the following testcase:

    [-5,-4,-1,1,1,5,8]
    0

    Your answer
    -1

    Expected answer
    0
    (i.e. [-4, -1, 5])

    The min possible complexity should be O(n^2). Any claim less than that must be tested thoroughly so that the fault can be exposed.


  • 0
    A

    @ayuanx

    you're right. thanks for pointing it out.


Log in to reply
 

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