# Two Sum II - Input Array Is Sorted
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted)
Canonical: https://scaleengineer.com/dsa/problems/two-sum-ii-input-array-is-sorted
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Infosys](https://scaleengineer.com/companies/infosys), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Oracle](https://scaleengineer.com/companies/oracle), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [Yandex](https://scaleengineer.com/companies/yandex), [eBay](https://scaleengineer.com/companies/ebay), [Zomato](https://scaleengineer.com/companies/zomato)
---
## 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**.

# Approaches
## Brute Force (Nested Loops)
The most straightforward approach is to check every possible pair of numbers in the array to see if they sum up to the target. This is done using two nested loops.
**Time:** O(n^2) · **Space:** O(1)
**Pros:** Simple to understand and implement.; Works for unsorted arrays as well.
**Cons:** Highly inefficient, leading to a "Time Limit Exceeded" error on larger datasets.; Fails to utilize the key information that the input array is sorted.
### Explanation
This method involves iterating through each element of the array and then, for each element, iterating through the rest of the array to find a pair that sums to the target. 

For an element at index `i`, we search for another element at index `j` (where `j > i`) such that `numbers[i] + numbers[j] == target`. While simple, this approach is computationally expensive as it checks every possible pair.

```java
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[i] + numbers[j] == target) {
                    return new int[]{i + 1, j + 1};
                }
            }
        }
        // This part is unreachable because a solution is guaranteed.
        return new int[]{-1, -1};
    }
}
```
### Algorithm
- Use a nested loop structure. The outer loop iterates from the first element to the second-to-last element with index `i`.
- The inner loop iterates from the element after `i` to the last element with index `j`.
- Inside the inner loop, check if `numbers[i] + numbers[j]` equals the `target`.
- If the sum is equal to the target, we have found our pair. Return a new array containing their 1-based indices, `[i + 1, j + 1]`.
- Since the problem guarantees that exactly one solution exists, we are sure to find a pair and return from within the loops.

## Using Binary Search
A better approach leverages the fact that the array is sorted. For each element `numbers[i]`, we can search for its complement (`target - numbers[i]`) in the rest of the array using binary search, which is much faster than a linear scan.
**Time:** O(n log n) · **Space:** O(1)
**Pros:** Significantly more efficient than the brute-force approach.; Correctly utilizes the sorted property of the array.
**Cons:** Not the most optimal solution as a linear time solution exists.
### Explanation
We can improve upon the brute-force approach by utilizing the sorted nature of the array. We iterate through the array with a single loop. For each element `numbers[i]`, we determine the value we need to find, which is `complement = target - numbers[i]`. Instead of scanning linearly for this complement, we can use the much more efficient binary search algorithm on the remainder of the array (from index `i+1` onwards).

```java
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            int complement = target - numbers[i];
            int low = i + 1;
            int high = numbers.length - 1;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (numbers[mid] == complement) {
                    return new int[]{i + 1, mid + 1};
                } else if (numbers[mid] < complement) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
        }
        // Unreachable code as a solution is guaranteed.
        return new int[]{-1, -1};
    }
}
```
### Algorithm
- Iterate through the array with an index `i` from `0` to `n-1`.
- For each `numbers[i]`, calculate `complement = target - numbers[i]`.
- Perform a binary search for `complement` in the subarray to the right of `i`, i.e., from index `i + 1` to `n - 1`.
- If the binary search finds the `complement` at index `j`, we have found our pair and can return `[i + 1, j + 1]`.

## Two Pointers
The most optimal approach uses two pointers, one starting at the beginning of the array and the other at the end. By comparing the sum of the values at these pointers with the target, we can intelligently move the pointers inwards to find the solution in a single pass.
**Time:** O(n) · **Space:** O(1)
**Pros:** Optimal time complexity, as it requires only a single pass through the array.; Optimal space complexity, meeting the problem's constraint of constant extra space.; Elegant and easy to implement.
**Cons:** This approach is only applicable because the input array is sorted.
### Explanation
This is the most efficient solution and fully exploits the sorted property of the array. We use two pointers, `left` starting at the first element (index 0) and `right` starting at the last element (index `n-1`).

We then check the sum of the values at these two pointers:
- If `numbers[left] + numbers[right]` equals the `target`, we have found our solution.
- If the sum is less than the `target`, we need a larger sum. Since the array is sorted, we can achieve this by moving the `left` pointer to the right (`left++`), which points to a larger value.
- If the sum is greater than the `target`, we need a smaller sum. We move the `right` pointer to the left (`right--`), which points to a smaller value.

We repeat this process until the pointers meet. Since a solution is guaranteed, we will find the pair before `left` and `right` cross.

```java
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int currentSum = numbers[left] + numbers[right];
            if (currentSum == target) {
                return new int[]{left + 1, right + 1};
            } else if (currentSum < target) {
                left++;
            } else { // currentSum > target
                right--;
            }
        }
        // Unreachable code as a solution is guaranteed.
        return new int[]{-1, -1};
    }
}
```
### Algorithm
- Initialize a pointer `left` to `0` and a pointer `right` to `n-1`.
- While `left < right`:
  - Calculate `sum = numbers[left] + numbers[right]`.
  - If `sum == target`, we found the pair. Return `[left+1, right+1]`.
  - If `sum < target`, the sum is too small. We need a larger number, so we increment `left`.
  - If `sum > target`, the sum is too large. We need a smaller number, so we decrement `right`.

# Solutions
### Java

```java
class Solution {
public
  int[] twoSum(int[] numbers, int target) {
    for (int i = 0, j = numbers.length - 1;;) {
      int x = numbers[i] + numbers[j];
      if (x == target) {
        return new int[]{i + 1, j + 1};
      }
      if (x < target) {
        ++i;
      } else {
        --j;
      }
    }
  }
}

```

### JavaScript

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

```

### CPP

```cpp
class Solution {
public:
  vector<int> twoSum(vector<int> &numbers, int target) {
    for (int i = 0, j = numbers.size() - 1;;) {
      int x = numbers[i] + numbers[j];
      if (x == target) {
        return {i + 1, j + 1};
      }
      if (x < target) {
        ++i;
      } else {
        --j;
      }
    }
  }
};

```

### Python

```python
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]: i, j = 0, len(numbers) - 1 while i < j: x = numbers[i] + numbers[j] if x == target: return [i + 1, j + 1] if x < target: i += 1 else: j -= 1

```