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
```