# 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. Sep 16, 2020 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. Sep 16, 2020 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 Sep 16, 2020 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). Sep 16, 2020 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. Sep 16, 2020 at 23:56