# LeetCode - Two Sum II - Input Array Is Sorted

## Problem statement

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.

Problem statement taken from: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted

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 * 10^4
- -1000 <= numbers[i] <= 1000
- numbers are sorted in non-decreasing order.
- -1000 <= target <= 1000
- The tests are generated such that there is exactly one solution.
``````

### Explanation

#### Binary Search

The problem is similar to our previous Two Sum problem. Instead of returning the numbers, we need to return their indices that sums up to target.

The input array is sorted, which makes it easy and direct for us to use the binary search concept. Let's check the algorithm directly.

``````- initialize i = 0, j = numbers.size() - 1
sum = 0

- loop while i < j
- sum = numbers[i] + numbers[j]

- if sum > target
- decrement: j--
- else if sum < target
- increment: i++
- else
// when the sum is equal to the target
- return [i + 1, j + 1]
- while end

- return []
``````

Let's check our algorithm in C++, Golang, and Javascript.

#### C++ solution

``````class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int i = 0, j = numbers.size() - 1;
int sum;

while(i < j) {
sum = numbers[i] + numbers[j];

if(sum > target) {
j--;
} else if(sum < target) {
i++;
} else {
return { i + 1, j + 1 };
}
}

return {};
}
};``````

#### Golang solution

``````func twoSum(numbers []int, target int) []int {
i, j := 0, len(numbers) - 1
sum := 0

for i < j {
sum = numbers[i] + numbers[j]

if sum > target {
j--
} else if sum < target {
i++
} else {
return []int{ i + 1, j + 1 }
}
}

return []int{}
}``````

#### Javascript solution

``````var twoSum = function(numbers, target) {
let i = 0, j = numbers.length - 1;
let sum = 0;

while(i < j) {
sum = numbers[i] + numbers[j];

if(sum > target) {
j--;
} else if(sum < target) {
i++;
} else {
return [i + 1, j + 1];
}
}

return [];
};``````

#### Dry Run

Let's dry-run our algorithm for Example 1.

``````Input: numbers = [2, 7, 11, 15]
target = 9

Step 1: set i = 0
j = numbers.size() - 1
= 4 - 1
= 3
sum = 0

Step 2: loop while i < j
0 < 3
true

sum = numbers[i] + numbers[j]
= numbers[0] + numbers[3]
= 2 + 15
= 17

if sum > target
17 > 9
true

j--
j = j - 1
= 3 - 1
= 2

Step 3: loop while i < j
0 < 2
true

sum = numbers[i] + numbers[j]
= numbers[0] + numbers[3]
= 2 + 11
= 13

if sum > target
13 > 9
true

j--
j = j - 1
= 2 - 1
= 1

Step 4: loop while i < j
0 < 1
true

sum = numbers[i] + numbers[j]
= numbers[0] + numbers[3]
= 2 + 7
= 9

if sum > target
9 > 9
false
else if sum < target
9 < 9
false
else
return [i + 1, j + 1]
return [0 + 1, 1 + 1]
return [1, 2]

We return the answer as [1, 2].
``````