Leetcode 167 - Two Sum II - Input array is sorted

Problem Description

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.

Examples

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].

Thought Process / Intuition

Since the question said we are guaranteed a solution, and only one unique solution, we can be sure that the pair lies within the list. We can use two pointers to create pairs, starting from the start of the array and the end of the array. Then, we progressively iterate through the list depending on the result of the pair, which is possible given that the list is sorted in ascending order, until we find the solution.

Approach

1. We initialize two pointers, left and right, to the start and end of the list, respectively.
2. We iterate through the list while left is less than right.
3. If the sum of the numbers at the left and right pointers is equal to the target, we return the indices of the two numbers.
4. If the sum of the numbers at the left and right pointers is greater than the target, we decrement the right pointer.
5. If the sum of the numbers at the left and right pointers is less than the target, we increment the left pointer.

Solution

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

Complexity Analysis

Time complexity: $O(n)$

• The time complexity of the solution is $O(n)$, where $n$ is length of the list.
• The two pointers approach allows us to find the solution in a single pass through the list, making the time complexity $O(n)$.

Space complexity: $O(1)$

• The space complexity of the solution is $O(1)$, as we are using a constant amount of extra space.