1
$\begingroup$

This algorithm solves the Two-Sum problem$^1$ assuming that the input array/list is sorted.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        N = len(nums)
        l, r = 0, N-1
        while l < r:
            comp = target - nums[l]
            r = bisect_left(nums, comp, lo=l+1, hi=r+1)
            # (r == 0 or nums[r-1] <  comp) and (r == N or nums[r] >= comp)
            # but actually r != 0 since lo = l+1 <= r < hi = r+1 meaning 0 <= l < r meaning  0 < r
            # so actually, we have
            # nums[r-1] <  comp and (r == N or nums[r] >= comp)
            if r < N and nums[r] == comp:
                return l+1, r+1 # +1 to convert 0-indexed indices to 1-indexed indices
            # r == N or nums[r] > comp
            # r == N or nums[r] > target - nums[l]
            # r == N or nums[l] + nums[r] > target so do r -= 1
            # nums[r-1] < comp
            # nums[r-1] < target - nums[l]
            # nums[l] + nums[r-1] < target so do l += 1
            r -= 1
            l += 1
        return None

Simplified algorithm and without the comments:

 1 class Solution:
 2     def twoSum(self, nums: List[int], target: int) -> List[int]:
 3         N = len(nums)
 4         l, r = 0, N-1
 5         while l < r:
 6             comp = target - nums[l]
 7             r = bisect_left(nums, comp, lo=l+1, hi=r)
 8             # INVARIANT: 0 <= l < r < N
 9             if nums[r] == comp:
10                 return l+1, r+1
11             l += 1
12         return None
  • bisect_left, Python's binary search algo, is $O(\lg n)$, and
  • I believe the while l < r loop runs on the order of $\lg n$ times,

so does the algorithm have an overall time-complexity of $O((\lg n)^2)$?

$^1$: Given a list of numbers and a target value, determine if there are two numbers that add up to the target value.

$\endgroup$
14
  • 1
    $\begingroup$ I think (r == N or nums[r] >= comp) holds in the 1st iteration, only. $\endgroup$
    – greybeard
    Jun 9 at 5:01
  • 2
    $\begingroup$ "I believe the while l < r loop runs on the order of lgn times," Why do you think that? [I think this loop runs O(n) times, but I don't feel confident enough to post an answer, so I am asking the question.] $\endgroup$ Jun 9 at 5:02
  • 1
    $\begingroup$ Please argue your the while l < r loop runs on the order of $\lg n$ times. $\endgroup$
    – greybeard
    Jun 9 at 5:03
  • $\begingroup$ @greybeard, you're correct about (r == N or nums[r] >= comp). It only holds in the 1st iteration. After the first iteration, r != N, so the invariant simplifies to nums[r] >= comp. If you have any suggestions for how to make that clearer, lmk. $\endgroup$
    – joseville
    Jun 9 at 18:19
  • 1
    $\begingroup$ @greybeard Another candidate: Let's say the values are uniformly from 0 to 1000 and we want sum 400. Then the upper 60% of the numbers can get discarded right away. Similarly, for a well above-average target sum, much of the lower numbers can be discarded right away. But after that, things are "tight", the complement of one end's number is near the opposite end. So: Determine the initial l and r with one binary search each, then use the linear two-pointer search. $\endgroup$ Jun 11 at 14:25

2 Answers 2

2
$\begingroup$

Unfortunately, the worst case of this algorithm is $\Theta(n\lg n)$, which is worse than $O(n)$, the time-complexity of the usual two-pointer algorithm that solves the same problem.


Consider the case with nums = list(range(n)) and target = 3*n//2, where n is an even number.

At the start of each iteration of the while loop, r == n - 1, since line 7 will set r to n and line 10 will set r back to n-1.

Since l goes from 0 initially to n//2 at the end, increasing by 1 in each iteration, there are n//2 iterations. Each iteration takes $\Theta(\lg n)$ time because of bisect_left at line 7. The time-complexity of this case is $\Theta(n\lg n)$.

$\endgroup$
10
  • 1
    $\begingroup$ Thanks! My mistake was thinking/assuming that the solution that uses binary search should automatically be better (i.e. have better time complexity) than the standard $O(n)$ time two-pointer solution. $\endgroup$
    – joseville
    Jun 9 at 18:38
  • $\begingroup$ Your case is invalid, as the allowed limit for n is 30 times larger than the allowed limit for the numbers. (If you disregard the limit, you don't even need to read their code to answer "no", as those complexities are impossible then. I was about to show that in an answer but then realized the limit makes the argument invalid...) $\endgroup$ Jun 11 at 1:52
  • $\begingroup$ @KellyBundy What is "the allowed limit for n"? $\endgroup$
    – John L.
    Jun 11 at 2:22
  • 1
    $\begingroup$ Although the question refers to that problem at Leetcode, the intention of the question is, apparently and as you might have realized, whether the asker had found an algorithm with better time-complexity when n goes to infinity. If n is limited by a constant, all relevant computations become O(1). $\endgroup$
    – John L.
    Jun 11 at 2:41
  • 1
    $\begingroup$ Please come here to chat. $\endgroup$
    – John L.
    Jun 11 at 6:56
3
$\begingroup$

Making the same assumption as John's accepted answer, that the numbers aren't limited like on LeetCode, we can answer your question with "no" even without looking at your code. Because those complexities are impossible. You can't do better than O(n).

Consider the n even numbers 2, 4, 6, 8, ..., 2n. The sum of smallest and largest is 2n+2. As is the sum of second-smallest and second-largest, and so on. There are n/2 pairs with sum 2n+2. Now I increase one of the numbers by 1. Which creates one pair with sum 2n+3. And I make the target 2n+3. Since the increased number is the only odd number, you need it for that target. So you have to find that one number. And looking at some other number doesn't tell you any more than that that's not the one. In whatever order you look at the numbers to find the one, you might get unlucky. My number might be the last number you look at. So you can't do better than O(n).

Another way to put it:

Think of it as a game. I tell you I have n sorted numbers built as described above. Now your task is to find that odd number. You can ask me for indexes and I'll tell you their numbers. You can do whatever you want with them. Compare, add, write a song about them, ask others for help, whatever. Until you asked for n-1 numbers, you won't know where the odd one is. Why? Because I'll cheat. For whatever n-1 numbers you ask first, I'll tell you the even number. And at the end, I'll claim that the last number is the one I increased at the start of the game. Or was I really cheating? Maybe I really did increase that particular one at the start. Cheating and not cheating, those two cases are indistinguishable to you. So I don't need to have cheated for you to need to ask for n-1 numbers.

And just in case the connection from my special case of numbers to the question's arbitrary n sorted numbers isn't clear: My special case is one possible case. We could play the same game and I would act in the exact same way, but you would only know that my numbers are sorted. The difference in the game as discussed above is just that I grant you a head start. I give you additional information. And despite that, you still have to ask for n-1 numbers.

$\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.