Leetcode 167 Two Sum II - Input Array Is Sorted

date

Feb 11, 2023

slug

leetcode167

author

status

Public

Leetcode 167 Two Sum II - Input Array Is Sorted

Brute Force Solution

The first solution that comes into my mind is that we just iteratively check the sum from the list. Specifically, using a for loop inside another one.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i in range(len(numbers)):
            for j in range( len(numbers) -1 -i ):
                if (numbers[i] +numbers[i+j+1])>target:
                    break
                if (numbers[i] +numbers[i+j+1]) == target: 
                    return [i+1 ,i+j+2]

This solution can solve the problem, however, taking too much time. In the worse case, the time complexity is O(N^2) since we using a for loop inside another one.

Two Pointer Solution

Maybe the breakthrough might be the sorted array. Considering we have an ascending arrangement array that has the smallest number on left and the biggest on right. Since the array has been sorted. When moving the pointer to the left the value will decrease else will increase. Using such a property we can have two pointers where one from the beginning and another from the end. If the sum of the value which been pointed by the pointer is larger than the target, we move the second pointer left. On the other hand, if the value is smaller than the target we move the first pointer right.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        pointer1 = 0
        pointer2 = len(numbers)-1
        while numbers[pointer1]+numbers[pointer2] != target:
            if numbers[pointer1]+numbers[pointer2] > target:
                pointer2 -=1
            else:
                pointer1 +=1
        return [pointer1+1,pointer2+1]

Time complexity analyzation

In the last case, since each pointer is not going to cross the other, it is similar to scanning the array once. Hence, the time complexity will be O(N).