Trying to get NlogN solution. But the code is failing for large testcases


#1

I’m trying to get a soultion having complexity nlogn where n is the array size. But the following code is failing for large testcases.

Will this approach work?

The approach is as follows:

  1. Sort the array.
  2. keep 3 pointers p,q,r. Initially p = 0 and r = size-1. And then applying two pointer approach and extend it to calculate the value at 3rd pointer ‘q’ in the array each time and moving p to right if overall sum is less than B or else move r to left if sum is greater than B.
  3. Each time we update the variable mn if the sum is more close to B than mn is.
  4. To calculate ‘q’ we can apply binary search on the array and try to get the the ‘q’ from the array such that A[q] is closest to the value (B-A[p]-A[r]) i.e. abs(A[q]-(B-A[p]-A[r]) is minimum.
  5. So, the total complexity can then become nlogn.

Example testcase for which the below code is failing:
27 174 430 405 706 627 813 376 94 566 37 737 142 815 995 257 653 937 839 483 356 16 132 231 842 626 12 638
1107

A = [174, 430, 405, 706, 627, 813, 376, 94, 566, 37, 737, 142, 815, 995, 257, 653, 937, 839, 483, 356, 16, 132, 231, 842, 626, 12, 638]
B = 1107
Output : 1106
Expected Output : 1107

long int search(vector& A,long int target, int s, int e)
{
long int l = 0,r = A.size(),mid,res,sz = A.size();
pair<long int,long int> diff1,diff2,diff3;
while(l < r)
{
mid = (l+r)/2;
if(A[mid] < target)
l = mid+1;
else if(A[mid] > target)
r = mid-1;
else
break;
}
diff1.first = mid;
diff2.first = mid-1;
diff3.first = mid+1;
diff1.second = abs(A[mid]-target);
diff2.second = diff3.second = INT_MAX;
if(mid-1 >= 0)
diff2.second = abs(A[mid-1]-target);
if(mid+1 < sz)
diff3.second = abs(A[mid+1]-target);
if(diff1.second > diff2.second)
swap(diff1,diff2);
if(diff1.second > diff3.second)
swap(diff1,diff3);
if(diff2.second > diff3.second)
swap(diff2,diff3);
if(diff1.first == s || diff1.first == e)
{
if(diff2.first == s || diff2.first == e)
res = diff3.first;
else
res = diff2.first;
}
else
res = diff1.first;
return res;
}
int Solution::threeSumClosest(vector &A, int B) {
long int sz = A.size(),p,q,r,sum,mn;
p = 0;
r = sz-1;
sort(A.begin(),A.end());
mn = 3*((long int)A[sz-1]);
//for(int i=0;i<sz;i++)
//{
// cout<<A[i]<<" ";
//}
cout<<endl;

while(p < r)
{
    sum = (long int)(A[p]+A[r]);
    q = search(A,(long int)(B-sum),p,r);
    sum = sum + (long int)(A[q]);
    
    if(abs(sum-B) < abs(mn-B))
        mn = sum;
    //cout<<"A["<<p<<"] = "<<A[p]<<" A["<<q<<"] = "<<A[q]<<" A["<<r<<"] = "<<A[r]<<" "<<sum<<" "<<mn<<endl;
    if(sum < B)
        p++;
    else if(sum > B)
        r--;
    else
    {
        mn = B;
        break;
    }
}
return (int)mn;

}