# Two Sum II - Input Array Is Sorted

- **Canonical ID**: `two-sum-ii`
- **Canonical URL**: https://dsacheatsheet.com/problems/two-sum-ii
- **Difficulty**: medium
- **Patterns**: Two Pointers
- **Version**: 1.0.0 (verified 2026-11-11T21:00:00Z)
- **Original Problem**: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

## 1. Core Invariant / The Trick

Sorted order guarantees monotonic sum adjustments: if `nums[l] + nums[r] > target`, only decreasing `r` can lower the sum; if `< target`, increment `l`. Return 1-based indices.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(1)`
- **Proof**: Eliminates one row or column of the candidate matrix per step.

## 3. Minimal Idiomatic Code

### Python
```python
def twoSumSorted(numbers: list[int], target: int) -> list[int]:
    l, r = 0, len(numbers) - 1
    while l < r:
        s = numbers[l] + numbers[r]
        if s == target: return [l + 1, r + 1]
        if s < target: l += 1
        else: r -= 1
    return []
```

### TypeScript
```typescript
export function twoSumSorted(numbers: number[], target: number): number[] {
  let l = 0, r = numbers.length - 1;
  while (l < r) {
    const s = numbers[l] + numbers[r];
    if (s === target) return [l + 1, r + 1];
    if (s < target) l++; else r--;
  }
  return [];
}
```

### C++
```cpp
vector<int> twoSum(vector<int>& n, int target) {
    int l = 0, r = n.size() - 1;
    while (l < r) {
        int s = n[l] + n[r];
        if (s == target) return {l + 1, r + 1};
        s < target ? l++ : r--;
    }
    return {};
}
```

### Java
```java
int[] twoSum(int[] n, int target) {
    int l = 0, r = n.length - 1;
    while (l < r) {
        int s = n[l] + n[r];
        if (s == target) return new int[]{l + 1, r + 1};
        if (s < target) l++; else r--;
    }
    return new int[]{};
}
```

### Go
```go
func twoSum(n []int, target int) []int {
    l, r := 0, len(n)-1
    for l < r {
        s := n[l] + n[r]
        if s == target { return []int{l + 1, r + 1} }
        if s < target { l++ } else { r-- }
    }
    return nil
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Problem requires 1-based indexing `[l + 1, r + 1]`.

### Follow-ups
- 3Sum freezes one pointer and calls this 2-pointer reduction.