# LeetCode 167: Two Sum II - Input Array Is Sorted

## Problem Restatement

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

The array is sorted in non-decreasing order.

We need to find two different numbers whose sum equals `target`.

Return their indices as:

```python
[index1, index2]
```

The returned indices must be 1-indexed, and:

```python
1 <= index1 < index2 <= len(numbers)
```

The problem guarantees exactly one valid answer. We cannot use the same element twice, and the solution must use only constant extra space.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Sorted integer array `numbers` and integer `target` |
| Output | Two 1-indexed positions |
| Array order | Non-decreasing |
| Valid pair | Two different elements |
| Guarantee | Exactly one solution exists |
| Space rule | Use only `O(1)` extra space |

Example function shape:

```python
def twoSum(numbers: list[int], target: int) -> list[int]:
    ...
```

## Examples

Example 1:

```python
numbers = [2, 7, 11, 15]
target = 9
```

The pair is:

```python
2 + 7 = 9
```

Their zero-indexed positions are:

```python
0, 1
```

But the problem asks for 1-indexed positions.

So the answer is:

```python
[1, 2]
```

Example 2:

```python
numbers = [2, 3, 4]
target = 6
```

The pair is:

```python
2 + 4 = 6
```

Return:

```python
[1, 3]
```

Example 3:

```python
numbers = [-1, 0]
target = -1
```

The pair is:

```python
-1 + 0 = -1
```

Return:

```python
[1, 2]
```

## First Thought: Brute Force

The simplest solution is to try every pair.

```python
class Solution:
    def twoSum(self, numbers: list[int], target: int) -> list[int]:
        n = len(numbers)

        for i in range(n):
            for j in range(i + 1, n):
                if numbers[i] + numbers[j] == target:
                    return [i + 1, j + 1]

        return []
```

This is correct because it checks every valid pair.

But it takes `O(n^2)` time.

The array is sorted, so we can do better.

## Key Insight

Because the array is sorted, we can use two pointers.

Start one pointer at the smallest number:

```python
left = 0
```

Start the other pointer at the largest number:

```python
right = len(numbers) - 1
```

Now compare:

```python
numbers[left] + numbers[right]
```

There are three cases.

| Sum compared to target | Action | Reason |
|---|---|---|
| Equal | Return indices | We found the answer |
| Too small | Move `left` right | Need a larger value |
| Too large | Move `right` left | Need a smaller value |

This works because the array is sorted.

Moving `left` right increases or keeps the left value.

Moving `right` left decreases or keeps the right value.

## Algorithm

Initialize:

```python
left = 0
right = len(numbers) - 1
```

While `left < right`:

1. Compute the sum.
2. If the sum equals `target`, return `[left + 1, right + 1]`.
3. If the sum is smaller than `target`, increment `left`.
4. If the sum is larger than `target`, decrement `right`.

The `+1` is required because the problem uses 1-indexed positions.

## Walkthrough

Use:

```python
numbers = [2, 7, 11, 15]
target = 9
```

Start:

```python
left = 0
right = 3
```

Check:

```python
numbers[left] + numbers[right] = 2 + 15 = 17
```

`17` is too large, so move `right` left.

Now:

```python
left = 0
right = 2
```

Check:

```python
2 + 11 = 13
```

`13` is still too large, so move `right` left again.

Now:

```python
left = 0
right = 1
```

Check:

```python
2 + 7 = 9
```

This matches the target.

Return 1-indexed positions:

```python
[1, 2]
```

## Correctness

At each step, the algorithm keeps the valid answer inside the range between `left` and `right`.

If the current sum is too small, then pairing `numbers[left]` with any element at or before `right` cannot reach the target unless we use a larger left value. Since the array is sorted, every value between `left + 1` and `right` is greater than or equal to `numbers[left]`. So moving `left` right is safe.

If the current sum is too large, then pairing `numbers[right]` with any element at or after `left` is too large unless we use a smaller right value. Since the array is sorted, every value before `right` is less than or equal to `numbers[right]`. So moving `right` left is safe.

The problem guarantees exactly one solution. Since each move discards only impossible pairs, the algorithm eventually reaches the valid pair and returns its 1-indexed positions.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each pointer moves inward at most `n` times |
| Space | `O(1)` | Only two pointers are stored |

## Implementation

```python
class Solution:
    def twoSum(self, numbers: list[int], target: int) -> list[int]:
        left = 0
        right = len(numbers) - 1

        while left < right:
            total = numbers[left] + numbers[right]

            if total == target:
                return [left + 1, right + 1]

            if total < target:
                left += 1
            else:
                right -= 1

        return []
```

## Code Explanation

We place one pointer at the beginning and one at the end:

```python
left = 0
right = len(numbers) - 1
```

The loop continues while the two pointers refer to different elements:

```python
while left < right:
```

Compute the current sum:

```python
total = numbers[left] + numbers[right]
```

If it matches the target:

```python
return [left + 1, right + 1]
```

we return 1-indexed positions.

If the sum is too small:

```python
left += 1
```

we need a larger number.

If the sum is too large:

```python
right -= 1
```

we need a smaller number.

The final return exists only for completeness. Valid LeetCode input guarantees a solution.

## Testing

```python
def run_tests():
    sol = Solution()

    assert sol.twoSum([2, 7, 11, 15], 9) == [1, 2]
    assert sol.twoSum([2, 3, 4], 6) == [1, 3]
    assert sol.twoSum([-1, 0], -1) == [1, 2]
    assert sol.twoSum([1, 2, 3, 4, 4, 9], 8) == [4, 5]
    assert sol.twoSum([-5, -2, 0, 3, 8], 1) == [2, 4]
    assert sol.twoSum([0, 0, 3, 4], 0) == [1, 2]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[2, 7, 11, 15]`, target `9` | Standard example |
| `[2, 3, 4]`, target `6` | Pair uses first and last |
| `[-1, 0]`, target `-1` | Negative number case |
| `[1, 2, 3, 4, 4, 9]`, target `8` | Duplicate values |
| `[-5, -2, 0, 3, 8]`, target `1` | Mixed negative and positive values |
| `[0, 0, 3, 4]`, target `0` | Same value at different indices |