0
$\begingroup$

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
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – nick.schachter Sep 16 '20 at 22:54
  • $\begingroup$ 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. $\endgroup$ – Fransebas Sep 16 '20 at 23:18
  • $\begingroup$ 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 $\endgroup$ – Fransebas Sep 16 '20 at 23:20
  • $\begingroup$ 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). $\endgroup$ – Fransebas Sep 16 '20 at 23:24
  • $\begingroup$ @nick.schachter I don't know if you saw the code, but I uploaded the wrong code but I've changed, sorry. $\endgroup$ – Fransebas Sep 16 '20 at 23:56
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.