[Top Interview 150] 167. Two Sum II - Input Array is Sorted

Solution)

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # Two Pointers
        left, right = 0, len(numbers)-1

        while left < right:
            # If the sum is target
            if numbers[left] + numbers[right] == target:
                return [left+1, right+1]
            
            # If the sum is greater than target
            if numbers[left] + numbers[right] > target:
                right -= 1
            
            # If the sum is less than target
            else:
                left += 1

 
 
Problem: LeetCode
 
Time Complexity: O(n)
Space Complexity: O(1)

Explanation)

There will be two pointers left and right.
 
left will start from the index 0.
right will start from the index len(numbers)-1.
 
As we iterate numbers from both ends, we'll compare the sum of two numbers with target.
 
 

Initialization)

We'll have two pointers left and right that start from both ends.
 

def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers)-1

 
 

sum == target)

The iteration will be continued until right and left both indicate the same index since we cannot use the same element.
 
If the sum of two numbers is the same as target, we obviously return the current indexes added by one (numbers is a 1-indexed array). 
 

def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers)-1

        while left < right:
            if numbers[left] + numbers[right] == target:
                return [left+1, right+1]

 
 

sum > target)

If the sum is greater than target, we need to look for a smaller element. 
 
Because numbers is an increasing list, we can easily find a smaller element by decrementing the pointer right. 
 

def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # Initialization

        while left < right:
            if numbers[left] + numbers[right] == target:
                return [left+1, right+1]
            
            if numbers[left] + numbers[right] > target:
                right -= 1

 
 

sum < target)

If the sum is less than target, we need to look for a bigger element.
 
This, also because numbers is an increasing list, can be done by incrementing left.
 

def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers)-1

        while left < right:
            if numbers[left] + numbers[right] == target:
                return [left+1, right+1]
            
            if numbers[left] + numbers[right] > target:
                right -= 1
            
            else:
                left += 1

 
 
 
I think the conditions that were given to us were too friendly. This problem has exactly one solution, and numbers is already sorted in an increasing order. But nobody hates a friendly problem right? :)