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:

- Sort the array.
- 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.
- Each time we update the variable mn if the sum is more close to B than mn is.
- 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.
- 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;
```

}