# 167. Two Sum II - Input Array Is Sorted

LeetCode Problems

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

## Table of Content

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

1. Two Sum

## Problem statement

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

## Approach

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
``````

## Code

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--;
}
};``````

## Complexity

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