Two Sum Ii Input Array Is Sorted - Leetcode Solution

Problem Statement:

Given an 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.

Return the indices of the two numbers (1-indexed) as an integer array answer of size 2, where 1 <= answer[i] <= numbers.length.

You must write an algorithm that runs in O(n) time complexity.

Example:

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.

Solution:

To solve this problem, we will have two pointers approach where we will maintain two pointers pointing at the first and last element of the array. Let's call these two pointers as left and right respectively.

• First, initialize the left pointer to the start of the array and the right pointer to the end of the array.
• While the left pointer is less than the right pointer, do the following steps:
  • Initialize a variable sum as the sum of the two elements pointed by the left and right pointers.
  • If the sum is equal to the target, return the indices of the left and right pointers.
  • If the sum is less than the target, move the left pointer one position forward.
  • If the sum is greater than the target, move the right pointer one position backward.
• If there is no solution, return an empty array.

Complexity Analysis:

• Time Complexity: O(n) because we are traversing the array only once using two pointers.
• Space Complexity: O(1) because we are not using any extra space.

Code:

Here is the Python code to solve the Two Sum II - Input array is sorted problem on LeetCode:

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1
        while left < right:
            sum = numbers[left] + numbers[right]
            if sum == target:
                return [left + 1, right + 1]
            elif sum < target:
                left += 1
            else:
                right -= 1
        return []

Let's test our code with the given example:

INPUT:

numbers = [2,7,11,15]
target = 9

OUTPUT:

[1,2]

Our code successfully passed the given test case.

1