# 0167. Two Sum II - Input array is sorted

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Two Sum II - Input array is sorted](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0167-two-sum-ii-input-array-is-sorted)

Given an 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.

Return *the indices of the two numbers (**1-indexed**) as an integer array* `answer` *of size* `2`*, where* `1 <= answer[0] < answer[1] <= numbers.length`.

The tests are generated such that there is **exactly one solution**. You **may not** use the same element twice.
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**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**.

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

Input: numbers = [2,3,4], target = 6
Output: [1,3]

Input: numbers = [-1,0], target = -1
Output: [1,2]
```

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
Since there is exactly one solution, **two-pointers** with **dynamically adjusted indexes** could help to solve.
{% endhint %}

**Starting with the left- and right-most elements**, we sum up them to see whether the result meets the target value.&#x20;

* If the **result is greater** than the target, we **move the right-pointer forward**.
* If the **result is less** than the target, we **move the left-pointer backward**.
  {% endtab %}
  {% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # (base case)
        if len(numbers) == 2: return [1, 2] if sum(numbers) == target else [-1, -1]
        
        # ==================================================
        #  Array + Two Pointer                             =
        # ==================================================
        # time  : O(n)
        # space : O(1)
        
        l, r = 0, len(numbers) - 1
        while l < r:
            tmp = numbers[l] + numbers[r]
            if   tmp == target: return [l+1, r+1]
            elif tmp > target: r -= 1
            elif tmp < target: l += 1
                
        return [-1, -1]
        
        '''
        # ==================================================
        #  Binary Search                                   =
        # ==================================================
        # time  : O(nlog(n))
        # space : O(1)
        
        for i in range(len(numbers) - 1):
            l = i + 1
            r = len(numbers) - 1
            remain = target - numbers[i]
            
            while l <= r:
                mid = (l + r) // 2
                if   numbers[mid] == remain: return [i+1, mid+1]
                elif numbers[mid]  > remain: r = mid - 1
                elif numbers[mid]  < remain: l = mid + 1
                    
        return [-1, -1]
        '''
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**  
     * @time  : O(n)
     * @space : O(1)
     */
    
    public int[] twoSum(int[] numbers, int target) {
        int l = 0, r = numbers.length - 1;
        
        while(l < r) {
            int tmp = numbers[l] + numbers[r];
            if(tmp == target) return new int[] {l+1, r+1};
            else if(tmp > target) r--;
            else if(tmp < target) l++;
        }
        
        return new int[] {-1, -1};
    }
}
```

{% endtab %}
{% endtabs %}