3Sum Why this O(nlogn) solution doesn't work?
-
29-09-2020 - |
Question
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:
- Sort the array.
i=0
andj= last element of array
i
andj
to findm
such thatarr[m] == target - arr[i] - arr[j]
, if suchm
doesn't exist returnm
such thatarr[m]
is the closest.arr[i] + arr[m] + arr[j] == target
then your finished.arr[i] + arr[m] + arr[j] < target
then add 1 toi
else subtract 1 formj
.- Repeat 3 → 5 until
j - i == 2
- 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
Solution
This fails for, e.g., [1, 9, 55, 55, 100], t=111. The first iteration finds 110 and increases i to exclude 1 as a possibility, but the only solution, [1, 55, 55], needs 1.
The basic problem is that when you increase i or reduce j, you are assuming that the element you just advanced past is not needed -- that there exists some solution that does not include it. But this is not justified by anything, and it could well be that all solutions need that element.
A great way to test algorithm ideas like this is to write a small program that generates many small random inputs, and compare the result of your algorithm on each of them to the result of a known-correct brute-force approach.