# algorithms – 3Sum Why this O(nlogn) solution doesn’t work?

Hi I’m doing LeetCode and I struct this problem of the 3Sum and first I tried to do a O(nlogn) solution and after seeing the proposed solution I see that the solution is O(n^2) or O(n^2 * logn) and not only that but the problem is a highly researched topic so I don’t think I found a better solution but can’t see why my approach wouldn’t work so I wan’t to see if you could help me figure it out.

The problem is the following find three numbers in an array such that `a + b + c = t`, the LeetCode problem is slightly different in which you need to find the closest sum.

My code is the following:

1. Sort the array.

2. Start with two pointers `i=0` and `j= last element of array`

1. Use binary search between `i` and `j` to find `m` such that `arr(m) == target - arr(i) - arr(j)`, if such `m` doesn’t exist return `m` such that `arr(m)` is the closest.
2. If `arr(i) + arr(m) + arr(j) == target` then your finished.
3. Otherwise if `arr(i) + arr(m) + arr(j) < target` then add 1 to `i` else subtract 1 form `j`.
3. Repeat 3 -> 5 until `j - i == 2`

4. Return the best found `i,m,j`

The logic in step 5 is that if the solution found is less than the target then we should increase `i` such that our next guess is bigger.

problem https://leetcode.com/problems/3sum-closest/

Code:

``````def findPair(nums, s, e, t): # O(log n)
i = s
j = e
d = 9999999999
r1 = r2 = 0
while i < j:
val = nums(i) + nums(j)
if abs(t - val) < d:
d = abs(t - val)
r1, r2 = i, j
if val == t:
return (i, j)
elif val > t:
j -= 1
else:
i += 1

return (r1, r2)

class Solution:
def threeSumClosest(self, nums, target: int) -> int:
nums.sort()

s = 0
L = len(nums)
res = 0
d = 9999999999
for i in range(L-2): # O(n)
j, k = findPair(nums, i + 1, L - 1, target - nums(i))
val = nums(i) + nums(j) + nums(k)
if abs(target - val) < d:
d = abs(target - val)
res = val

return res
$$```$$
``````