Problem Statement in English

You’re given a sorted array of integers nums. Your task is to return the indices of 2 numbers that add up to target. Such a pair is guaranteed to exist.

Use 1 based indexing.

Approach

We can definitely brute force this by using a nested loop, but there’s a better approach.

The 2 Pointer Technique. We maintain a left and right pointer. If the sum of elements pointer by this pointer equals the target then we’re done.

Otherwise, we need to move the left or right pointer. Now, the important thing to note here is that the input array is sorted in ascending order. This means that the elements get progressively larger as we move from left to right.

So:

  • if the sum of elements pointed by the pointer is larger than necessary, we move the right pointer towards the left, as this will make the value pointed to by the right pointer smaller
  • if the sum is smaller than the target, we move the left pointer to the right, as this makes the value pointed to by the left pointer larger

Take a look at the code now.

Solution in Python


class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # initialise the pointer
        l, r = 0, len(numbers) - 1

        # run code while left pointer is before the right one
        while l < r:
            # current sum of elements pointed to by the pointers
            s = numbers[l] + numbers[r]

            # if the sum is the required one, we're done
            if s == target:
                # since we've to use 1 based indexing
                return [l + 1, r + 1]
            # if the sum is smaller than the target
            elif s < target:
                # move left pointer towards the right
                l += 1
            else:
                # move the right pointer towards the left
                r -= 1

        # to get my linter to stop screaming at me
        return []

Complexity

  • Time: $O(n)$
    Since we iterate over $n$ elements at most.

  • Space: $O(1)$
    Since we store a few integer variables.

And we are done.