## Table of contents

## Open Table of contents

## Problem

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.

## Explanation/Approach

Given a sorted array of integers, the task is to find two numbers that add up to a specific target number. The sorted nature of the array can be exploited to optimize the search for the two numbers, which is a crucial hint for efficiently solving this problem.

A possible approach is using the **Two-Pointer technique**. Since the array is sorted in non-decreasing order, you can start with two pointers, one at the beginning (left) and one at the end (right) of the array. At each step, calculate the sum of the elements pointed to by the two pointers. Depending on the comparison between the sum and the target:

- If the sum is equal to the target, you’ve found the two numbers.
- If the sum is less than the target, move the left pointer to the right (increment it).
- If the sum is more than the target, move the right pointer to the left (decrement it).

Repeat these steps until the left pointer is less than the right pointer.

## Solution 1: (Two Pointers)

```
def two_sum(numbers: List[int], target: int) -> List[int]:
# Initialize two pointers at both ends of the list
left, right = 0, len(numbers) - 1
# Loop until the two pointers meet
while left < right:
# Calculate the sum of elements at both pointers
current_sum = numbers[left] + numbers[right]
# If the sum is equal to target, return the indices (1-indexed)
if current_sum == target:
return [left + 1, right + 1]
# If sum is less than target, move left pointer to the right
elif current_sum < target:
left += 1
# If sum is more than target, move right pointer to the left
else:
right -= 1
```

**Explanation**

- Start with two pointers at both ends of the array. Initialize
`left`

at 0 and`right`

at`len(numbers) - 1`

. - While
`left`

pointer is less than`right`

pointer:- Calculate
`current_sum`

as the sum of`numbers[left]`

and`numbers[right]`

. - If
`current_sum`

is equal to`target`

, return the indices`left + 1`

and`right + 1`

(since the problem requires 1-indexed array). - If
`current_sum`

is less than`target`

, increment`left`

to move towards a larger value (since the array is sorted). - If
`current_sum`

is more than`target`

, decrement`right`

to move towards a smaller value.

- Calculate
- Continue this process until the
`left`

pointer is no longer less than the`right`

pointer.

**Time and Memory Complexity**

**Time Complexity:**O(N). Each element is visited at most once, leading to linear time complexity.**Space Complexity:**O(1). Only a constant amount of extra space is used, satisfying the problem constraint of using only constant extra space.

## Solution 2: (Hash Map)

Although the two-pointer approach is more optimal for this specific problem due to the sorted nature of the array, you can also solve it using a Hash Map for general understanding. Below is the Hash Map approach explained:

```
def two_sum(numbers: List[int], target: int) -> List[int]:
# Create a hash map to store indices of numbers
index_map = {}
# Iterate through the list of numbers with index
for index, num in enumerate(numbers, start=1): # Using 1-based indexing
complement = target - num # Calculate the complement of current number
# If complement is found in hash map, return the indices
if complement in index_map:
return [index_map[complement], index]
# Otherwise, add the number and its index to the hash map
index_map[num] = index
```

**Explanation**

- Create a Hash Map (
`index_map`

) to store indices of numbers as you iterate through the array. - Iterate through the list of numbers with their index. Using
`enumerate(numbers, start=1)`

to have 1-based indexing as required by the problem statement. - For each number, calculate its complement with respect to the target (i.e.,
`complement = target - num`

). - Check if this
`complement`

is already available in the`index_map`

. If it is, that means you have found two numbers whose sum is equal to the target. Return their indices. - If the
`complement`

is not in the`index_map`

, add the current number and its index to the`index_map`

. - Continue this process for all numbers in the array.

**Time and Memory Complexity**

**Time Complexity:**O(N). You need to iterate through all elements in the array once, performing O(1) work for each due to the hash map.**Space Complexity:**O(N). You need to store all N elements in the hash map in the worst case. This solution does not satisfy the constant extra space requirement posed by the problem, but it’s provided here for educational purposes and for problems where space complexity is not a constraint.