LeetCode Problems

In this tutorial we will solve 167. Two Sum II - Input Array Is Sorted from leetcode.

Reference: 167. Two Sum II - Input Array Is Sorted

We are given a 1-indexed array of integer `numbers`

. The elements in the array is sorted in non-descending order. We are asked to find two numbers that will add up to the `target`

number.

We have to return the indices of the two numbers such that it satisfies the following condition i <= index1 < index2 <= numbers.length. We are not allowed to use the same element of the input array more than once.

We are also told that the tests are generated in such a way that there is exactly one solution.

We should try to solve this problem by using only constant extra space.

**1-indexed array** - an array that uses 1 as the starting index instead of 0.

**Non-descending order** - a sequence of elements where each successive element is greater than or equal to its previous element in the sequence. Example: 1, 2, 2, 3, 4, 5, 5, 6.

Example from leetcode.

```
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 is sorted in non-decreasing order.
-1000 <= target <= 1000
The tests are generated such that there is exactly one solution.
```

To solve this problem we will take help of **two pointers**. The first pointer `i`

will be pointing at the first element of the array. The second pointer `j`

will be pointing at the last element of the array.

In each iteration we will check if the sum of the numbers at index `i`

and `j`

adds up to the `target`

number. If yes, then we will return the indices.

If the added sum is greater than the `target`

number then we will decrement `j`

by 1. If the added sum is smaller than the `target`

number then we will increment `i`

by 1.

We will continue this till `i < j`

.

Let use look at the input numbers = [2,7,11,15], target = 9

```
target = 9
numbers = [2, 7, 11, 15]
^ ^
i j
is i < j and numbers[i] + numbers[j] === target ?
-> 2 + 15 is greater than target 9
-> decrement j
numbers = [2, 7, 11, 15]
^ ^
i j
is i < j and numbers[i] + numbers[j] === target ?
-> 2 + 11 is greater than target 9
-> decrement j
numbers = [2, 7, 11, 15]
^ ^
i j
is i < j and numbers[i] + numbers[j] === target ?
-> 2 + 7 is equal to the target 9
-> we found our numbers and the indices
```

JavaScript

```
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function(numbers, target) {
let i = 0;
let j = numbers.length - 1;
while (i < j) {
const sum = numbers[i] + numbers[j];
if (sum === target) return [i+1, j+1];
if (sum < target) i++;
else j--;
}
};
```

**Time complexity: O(n)**

We are looping through the array size n so the time complexity will be O(n).

**Space complexity: O(1)**

We are taking help of two pointers which takes constant space so the space complexity will be O(1).

ADVERTISEMENT