Two Sum II - Input Array is Sorted

  • 0

    Click here to see the full article post

  • 0

    Below is the code I tried to test but it keeps telling me Line 3: error: <identifier> expected.
    I'm confused since this code is almost the same as solution. or Error : Line 3: error: illegal start of type. Anyone can help find the problem? I am using java.

    public class Solution {
            public vector<int> twoSum(vector<int>& numbers, int target){
                int low = 0, high = numbers.size()-1;
                while(low< high){
                    int sum= numbers[low]+ numbers[high];
                    if(sum == target){
                        return {low+1, high+1};
                    else if(sum< target){
                return {-1,-1};

  • -2

    If you are bad, use Java. This is the only advice you need.

  • 1

    I believe binary search is still applicable to this question. I read some existing posts. Most of them used binary search for one value, and their algorithm could be described as following:

    for(i = 0; i < nums; i++)
       num1 = nums[i]; 
       num2 = target - num1;
       binary search num2 in nums[i:], if found, return the index of num1, num2

    Their approach actually takes O(nlogn) time. The worst case is num1 and num2 is the center. It takes log(n-1)+log(n-2)+..log(n/2) ~ nlogn

    My idea is using binary search with only one loop. The worst case is:

    • the input arry contains same values, or
    • num1 and num2 is in the center is
      then every time we move the cursor by 1, which takes O(n). In other cases my approach is faster than linear scan.

    We could start with left = 0, right = nums.size()-1, and mid = left+right.
    Since the input vector is sorted, we know nums[left] < nums[mid] < nums[right], so that: nums[left] + nums[mid] < nums[left] + nums[right] < nums[mid] + nums[right].

    If nums[left] + nums[mid] > target, the 2 number we are looking for must be within nums[left:mid-1]. Similarly, if nums[right] + nums[mid] < target, the 2 number we are looking for must be within nums[mid+1:right].

    Following is an accepted C++ implemetaion.

    class Solution {
       vector<int> twoSum(vector<int>& numbers, int target) {
           int left = 0, right = numbers.size()-1; 
           vector<int> ret; 
           while (left < right){
               int mid = left + (right-left)/2; 
               int sum = numbers[left] + numbers[right]; 
               if (sum == target){
               else if (sum < target){
                   left = (numbers[mid] + numbers[right] < target)?mid:left+1;
                   right = (numbers[mid] + numbers[left] > target)?mid:right-1;
           return ret; 

  • 0

    You have to consider overflow case. Doesn't work for a test case of numbers={1, 2, 3, 2147483647}, target=3.

  • 0

    This logic yields time error in Python. I implemented binary search in Python which has O(nlogn) complexity:

    class Solution(object):
        def twoSum(self, numbers, target):
            :type numbers: List[int]
            :type target: int
            :rtype: List[int]
            i = 0
            for i in range(0, len(numbers)):
                num1 = numbers[i]
                target_new = target - num1
                j = i + 1
                k = len(numbers) - 1
                while j <= k:
                    if numbers[j] == target_new:
                        return [i+1 ,j+1]
                    elif k - j == 1:
                        if numbers[k] == target_new:
                            return [i+1, k+1]
                        middle = int((j + k)/2)
                        if target_new < numbers[middle]:
                            k = middle
                        elif target_new > numbers[middle]:
                            j = middle
                            return [i+1, middle+1]

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.