167. Two Sum II — Input Array Is Sorted — LeetCode(Python)

I got you!

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

Constraints:

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers is sorted in non-decreasing order.
• -1000 <= target <= 1000
• The tests are generated such that there is exactly one solution.

Solution:

l, r = 0, len(numbers) - 1
while l < r:
    if numbers[l] + numbers[r] == target:
        return [l+1, r+1]
    elif numbers[l] + numbers[r] < target:
        l += 1
    else:
        r -= 1

Explanation —

This problem is a modification of the most famous problem on LeetCode — Two Sum.

Our input array is already sorted, so we can use a two-pointer approach here.

Two pointers, l and r, are set to two ends of the array.

If the sum of the values at these indices in the array is equal to target, we return the (two pointers+1) [since, index + 1 = position as array indexing begins at 0 in Python].

If the sum is less than the target value, we increment our left pointer, since we know that our array is sorted and we need a larger value.

Similarly, otherwise, we decrement out right pointer.

We are always guaranteed a solution, so we need not return anything if they while loop is terminated, because it only terminates in the return statement.

Time and Space Complexity —

Since, we are visiting each element in the array at most once, our code takes linear time to run. Also, we are using constant extra space.

Thus, if n is the length of the array numbers,

Time Complexity: O(n)

Space Complexity: O(1)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏