Leetcode: 167. Two Sum II - Input Array Is Sorted

• Given an array of sorted numbers

• and a target sum

• find a pair of indices in the array whose sum is equal to the given target.

• Target Sum = 13

• Output : [1, 4]

Approach 1: Brute Force

• Here the length of the array is 7 iterating for each element (pointed by the first pointer) we search the second element in the remaining elements (pointed by the second pointer) -

• 7 (Length) : 6 + 5 + 4 + 3 + 2 + 1

• N (Length) : N-1 + N-2 + N-3 + .... + 2 + 1, So the time complexity calculate as -

• Sum of first (N-1) natural numbers :

  • N : N(N+1)/2

  • N-1 : (N-1)(N-1+1)/2

  • \= N(N-1)/2

  • \= N²/2 - N/2

• Time Complexity : O(n²)

• Space Complexity : O(1)

Code:

def solve(arr,target):
    for i in range(len(arr)):
        for j in range(i+1,len(arr)):
            if arr[i]+arr[j]==target:
                return [i,j]
    return [-1,-1]

arr = [2,4,8,7,9,12,14]
target = 13
print(solve(arr,target))

Approach 2: Optimize the version

• Why given array is sorted?

• An efficient way would be to start with one pointer at the beginning and another pointer at the end.

• At every step, we will see if the numbers pointed by the two pointers add up to the target sum. If they do not, we will do one of two things:

  • If the sum of the two numbers pointed by the two pointers is greater than the target sum, this means that we need a pair with a smaller sum. We have to add a smaller value for that we have to decrement the end pointer index.

  • If the sum of the two numbers pointed by the two pointers is less than the target sum, this means that we need a pair with a greater sum. We have to add greater value for that we have to increment the start pointer.

• Time Complexity : O(n)

• Space Complexity : O(1)

Code:

def pairSum(arr,target):
    left = 0
    right = len(arr)-1

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

arr = [1, 3, 5, 6, 8, 9]
target = 11
print(pairSum(arr, target))