# 167 Two Sum II - Input Array is Sorted

## 1. Description

Given a **1-indexed** array of integers `numers`

that is already **sorted in non-decreasing order**, find two numbers such that
they add up to a specific target. Let these two numbers be `numbers[index1]`

and `numbers[index2]`

where
\(1 \leq index1 \leq index2 \leq numbers.length\).

Return the indices of the two numbers, `index1`

and `index2`

, **added by one** as an integer array `[index1, index2]`

of length 2.

Constraints:

- The tests are generated such that there's
**exactly one solution**. You**may not**use the same element twice. - \(2 \leq numbers.length \leq 3*10^{4}\)
- \(-1000 \leq numbers[i] \leq 1000\)
- \(numbers\) is sorted in non-decreasing order
- \(-1000 \leq target \leq 1000\)

### 1.1. Examples:

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

## 2. Solution

### 2.1. Understanding the problem

A naive approach would be just start from the left and add each element with the rest of the elements that have not been added to the current element before. This would take \(O(N^{2})\) time.

However, if we consider the fact that this is a sorted array, we can start from both ends and exclude a significant amount of pairs. In fact this will cut the time down to \(O(N)\).

### 2.2. Algorithm

- We start from
`left_idx = 0`

and`right_idx = len(numbers) - 1`

. - if
`numbers[left_idx] + numbers[right_idx] == target`

, we add 1 and return the two indices.- if
`numbers[left_idx] + numbers[right_idx] < target`

, then`left_idx += 1`

- if
`numbers[left_idx] + numbers[right_idx] > target`

, then`right_idx -= 1`

- if
- go back to 2.

### 2.3. Code

def twoSum(numbers, target): """ :type numbers: List[int] :type target: int :rtype: List[int] """ left_idx = 0 right_idx = len(numbers) - 1 # could've used while True but just make sure loop will always terminate while left_idx <= right_idx: if (numbers[left_idx] + numbers[right_idx]) == target: return [left_idx+1, right_idx + 1] elif numbers[left_idx] + numbers[right_idx] < target: left_idx += 1 elif numbers[left_idx] + numbers[right_idx] > target: right_idx -= 1 # tests numbers = [2,7,11,15] target = 9 output = [1, 2] print(twoSum(numbers, target) == output) numbers, target = [2, 3, 4], 6 output = [1, 3] print(twoSum(numbers, target) == output) numbers, target = [-1, 0], -1 output = [1, 2] print(twoSum(numbers, target) == output)

```
True
```

#### 2.3.1. Complexity

##### 2.3.1.1. Time complexity:

`O(N)`

because we only traverse the array once.

##### 2.3.1.2. Space complexity:

`O(1)`

.

### 2.4. Leetcode solution

Same.

```
<<imports for typing>>
```

#### 2.4.1. Time complexity:

#### 2.4.2. Space complexity:

## 3. More analysis

### 3.1. General thoughts

The whole solution is based on the following fact:

- The array is sorted.