Two Sum II - Input Array Is Sorted (Leetcode 167)

Problem Link: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

Two Pointer Approach

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
          
        n=len(numbers)
        i=0
        j=n-1
        while(i<j):
            summ=numbers[i]+numbers[j]
            if(summ==target):
                return [i+1,j+1]
            elif(summ<target):
                i+=1
            else:
                j-=1
        return False

Binary Search Approach

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
          
        def bsearch(arr,l,h,k):
            if(l>h):
                return None
            mid=(l+h)//2
            if(arr[mid]==k):
                return mid
            elif(arr[mid]>k):
                return bsearch(arr,l,mid-1,k)
            else:
                return bsearch(arr,mid+1,h,k)
        
        n=len(numbers)
        for i in range(n-1):
            ind=bsearch(numbers,i+1,n-1,target-numbers[i])
            if(ind is not None):
                return [i+1,ind+1]

Last updated