> For the complete documentation index, see [llms.txt](https://docs-57.gitbook.io/data-structure-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs-57.gitbook.io/data-structure-and-algorithms/problems/array/two-sum-ii-input-array-is-sorted.md).

# Two Sum II - Input Array Is Sorted

{% hint style="info" %}
Array, Two Pointers
{% endhint %}

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

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 and Statements:

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

Questions to Clarify:

* **Negative Numbers**: Can the input array contain negative numbers? Yes.
* **Duplicate Numbers**: Can the input array contain duplicate numbers? No.
* **Unique Solution**: Is it guaranteed that there will always be exactly one solution? Yes.
* **Indices Required**: Do we need to return the actual indices of the solution numbers, or just the numbers themselves? Actual indices of the solution numbers.

Additional Considerations:

* **Array Size**: What are the expected size limits for the input array?
* **Time and Space Complexity**: Are there any specific time or space complexity requirements for the solution? Yes, constant extra space and `O(N)` time Complexity.

Now, all requirements are clear: we can't use a hash table, and we need to solve this problem with `O(N)` time complexity. So, the nested loop is also not valid for this problem.

### Solutions

As we know, array elements are already in sorted order, and with a sorted array, we can follow the *two-pointer* approach.

#### **Approach – Two Pointers**

***

&#x20;Initialize two pointers at the beginning and  at the end of the array and calculate sum of both pointers value if sum is equal to target number then return both pointers indices otherwise increment/decrement pointers based on sum value.

**Steps**

1. **Initialize two pointers**: `left` at the beginning and `right` at the end of the array.
2. **Iterate while pointers haven't crossed**:
   * Calculate the current `sum` of elements at left and right.
   * If the sum equals the `target`, return the indices (adding 1 for 1-indexing).
   * If the `sum` is less than the `target`, increment `left` to move towards larger values.
   * If the `sum` is greater than the `target`, decrement `right` to move towards smaller values.
3. **If no solution found**: Return an empty array.

```csharp
public class Solution
{
    public int[] TwoSum(int[] nums, int target)
    {

        int[] result = [0, 0];
        int left = 0;
        int right = nums.Length - 1;

        while (left < right)
        {
            int sum = nums[left] + nums[right];
            if (sum == target)
            {
                result[0] = left + 1; // adding 1 for 1-indexing as input is a 1-indexed array.
                result[1] = right + 1; // adding 1 for 1-indexing as input is a 1-indexed array.
                break;
            }
            else if (sum < target)
            {
                left++;
            }
            else
            {
                right--;
            }
        }

        return result;
    }

}

```

> Complexity

* **Time Complexity:** O(n)
* **Auxiliary Space:** O(1)