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