# 3Sum Why this O(nlogn) solution doesn't work?

I have been doing LeetCode and tackled the 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 \times \log n)$$ 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, can use help to 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
3.     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.
4.     If arr[i] + arr[m] + arr[j] == target then your finished.
5.     Otherwise if arr[i] + arr[m] + arr[j] < target then add 1 to i else subtract 1 form j.
6. Repeat 3 → 5 until j - i == 2
7. 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.

Code:

def binSearch(arr, s, e, t):
m = (s + e) // 2
r = m
d = 9999
while s <= e:
m = (s + e) // 2
if arr[m] == t:
return m
elif arr[m] > t:
e = m - 1
else:
s = m + 1

if d > abs(t - arr[m]):
d = abs(t - arr[m])
r = m
return r

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

s = 0
e = len(nums) - 1
minn = 999999
t = ()
while e - s >= 2:
left = nums[s]
right = nums[e]
remaining = target - (left + right)
m = binSearch(nums, s + 1, e - 1, remaining)
middle = nums[m]
r = left + middle + right

# print("i's: ", (s,m,e))
# print("values: ", (nums[s], nums[m], nums[e]))
# print("r", r)
# print("**************")

if r == target:
return r
elif r < target:
s += 1
else:
e -= 1

if abs(target - r) < minn:
minn = abs(target - r)
t = r
return t

• Your approach is very similar to the quadratic time algorithm described on the wikipedia page for 3SUM. It might be helpful to see the analysis presented there. – nick.schachter Sep 16 '20 at 22:54
• Is not quite the same, very similar but not the same (I'm going to put my code so you can see it better), what they do is for every i they traverse all j from i+2 to len(arr) and find the missing index by doing a B.S. between i and j. – Fransebas Sep 16 '20 at 23:18
• In my case I only go through each index once. Most probably this is wrong and there is a case where this doesn't work but I can see when – Fransebas Sep 16 '20 at 23:20
• For example in an array of size 5 the variables i and j goes through: (0,4), (0,3),(0,2), (1,4),(1,3),(2,4), and in my code it will only be (0,4), (1,4),(1,3), (1,2) - this is a posible case -. Wikipedia code will have (n*(n+1)/2) pairs and mine will have n pairs (note that n is the size of the array minus 2). – Fransebas Sep 16 '20 at 23:24
• @nick.schachter I don't know if you saw the code, but I uploaded the wrong code but I've changed, sorry. – Fransebas Sep 16 '20 at 23:56