# NEETCODE - Two Pointers: Two Integer Sum II

From O(n²) brute force to O(n) two-pointer technique

Technology: **Python, Algorithms**  
Skill: **Two Pointers, O(n)**

## Problem Statement

Given an array of integers `numbers` that is **sorted in non-decreasing order**, find two numbers that add up to a specific `target` number.

Return the **indices** of the two numbers (1-indexed) as `[index1, index2]` where `index1 < index2`.

**Key Constraints:**
- The array is already sorted
- Exactly one solution exists
- Must use O(1) additional space
- Cannot use the same element twice
- Return 1-indexed positions (not 0-indexed)

**Example:**

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

Explanation:
1 + 2 = 3
index1 = 1, index2 = 2 (1-indexed)
```

**Constraints:**
```
2 <= numbers.length <= 1000
-1000 <= numbers[i] <= 1000
-1000 <= target <= 1000
```

## Solutions Progression

### Approach 1: Brute Force (Nested Loops)

```
def twoSum(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]  # 1-indexed

return []
```
**Time Complexity: O(n²)**
- Outer loop runs n times
- Inner loop runs (n-1), (n-2), ..., 1 times
- Total comparisons: (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ O(n²)

**Space Complexity: O(1)**
- Only using two loop variables, no additional data structures

**Why this approach works:**
- Checks every possible pair exhaustively
- Guaranteed to find the solution if it exists

**Trade-offs:**
- ✅ Simple to understand and implement
- ✅ O(1) space meets constraint
- ❌ Ignores the sorted property completely
- ❌ Wastes time checking impossible pairs

### Approach 2: Hash Map (Complement Lookup)

```
def twoSum(numbers: List[int], target: int) -> List[int]:
    seen = {}  # value -> index

for i, num in enumerate(numbers):
        complement = target - num

if complement in seen:
            return [seen[complement] + 1, i + 1]  # 1-indexed

seen[num] = i
    return []
```
**Time Complexity: O(n)**
- Single pass through array: O(n)
- Hash lookups are O(1) average case
- Total: O(n)

**Space Complexity: O(n)**
- Worst case: store all n elements in hash map

**Why this approach works:**
- For each number, check if its complement exists
- Store numbers we've seen for instant lookup

**Trade-offs:**
- ✅ Optimal time complexity
- ✅ Works on unsorted arrays too
- ❌ **Violates the O(1) space constraint**
- ❌ Doesn't leverage the sorted property

### Approach 3: Two Pointers (Optimal) ⭐

```
def twoSum(numbers: List[int], target: int) -> List[int]:
    left = 0
    right = len(numbers) - 1

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

if current_sum == target:
            return [left + 1, right + 1]  # 1-indexed
        elif current_sum < target:
            left += 1   # Need larger sum
        else:
            right -= 1  # Need smaller sum

return []
```
**Time Complexity: O(n)**
**Detailed breakdown:**
- Each iteration moves one pointer
- Left pointer moves from 0 → n-1 (worst case)
- Right pointer moves from n-1 → 0 (worst case)
- **Total pointer movements:** At most n steps
- Each step does O(1) work (addition, comparison)
- **Result: O(n)**

**Mathematical justification:**
- At each step, we eliminate at least one index from consideration
- Start with n possible positions, end with 0
- Maximum iterations = n

**Space Complexity: O(1)**
- Only two pointer variables (left, right)
- No additional data structures

**Why this approach works:**
- The key insight is the **sorted property**:
    1. **If sum is too small:** `numbers[left]` must be too small
        - All pairs with `numbers[left]` will be too small
        - Move left pointer right to get larger values
    2. **If sum is too large:** `numbers[right]` must be too large
        - All pairs with `numbers[right]` will be too large
        - Move right pointer left to get smaller values
    3. **Convergence guarantee:**
        - Pointers move toward each other
        - Eventually meet at the solution or exhaust all pairs

**Trade-offs:**
- ✅ Optimal time: O(n)
- ✅ Optimal space: O(1)
- ✅ Leverages sorted property perfectly
- ✅ Elegant and intuitive
- ❌ **Only works on sorted arrays**

## Pattern Recognition

### Core Algorithmic Pattern: Two Pointers (Opposite Ends)

This is a fundamental pattern where:
1. Start with pointers at opposite ends of a sorted array
2. Move pointers based on comparison logic
3. Converge toward the solution

### Key Insight That Unlocks the Problem
**The sorted property + two pointers = O(n) without extra space**
Most people's first instinct is hash map (from regular Two Sum). The breakthrough is recognizing:
- "Sorted" means we can make directional decisions
- If sum is wrong, we know exactly which pointer to move
- No need to remember anything → O(1) space

## Bridge to Real Systems

### Where This Algorithm Lives in Production
1. **Database Query Optimization**
   - PostgreSQL's merge join uses this exact pattern:
   ```
   -- When joining two sorted tables
   SELECT * FROM table1
   JOIN table2 ON table1.id = table2.id
   ORDER BY table1.id;
   ```
2. **Network Protocol - TCP Congestion Control**
   - TCP's Fast Retransmit uses two pointers tracking:
3. **Git Merge Algorithm**
   - Git's three-way merge uses pointers to traverse sorted commit histories:
4. **Redis Sorted Sets (ZRANGEBYLEX)**
   - Redis uses two-pointer logic for range queries on sorted sets:
5. **Google's MapReduce - Merge Phase**
   - When combining sorted outputs from reducers:

## Complexity Summary Table
| Approach | Time | Space | Pros | Cons | Use Case |
| --- | --- | --- | --- | --- | --- |
| **Brute Force** | O(n²) | O(1) | Simple, no preprocessing | Inefficient, ignores sorted property | Teaching, n < 20 |
| **Hash Map** | O(n) | O(n) | Fast, works on unsorted | Uses extra space, violates constraint | Unsorted arrays |
| **Two Pointers** ⭐ | O(n) | O(1) | Optimal time & space, elegant | **Requires sorted array** | **Production solution** |
| **Binary Search** | O(n log n) | O(1) | Alternative approach | Slower than two pointers | Academic interest |

**Winner: Two Pointers** - O(n) time, O(1) space, leverages sorted property perfectly.