# Two Pointers — Part 2: Interview Problems

Six problems covering both shapes: opposite ends (sorted pairs, containers, rain water) and same direction (in-place compaction, partitioning).

## 1. Two Sum II – Input Array Is Sorted (LeetCode 167)

**🟠 Medium.** `numbers` is sorted ascending. Return the **1-indexed** positions `[i, j]` of the two numbers adding up to `target`. Use O(1) extra space.

```text
numbers = [2,7,11,15], target = 9 → [1,2]
```

**Approach.** Opposite-end pointers: too small → move left right; too big → move right left.

**Complexity.** O(n) time, O(1) space.

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

```python
def two_sum_sorted(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        s = numbers[left] + numbers[right]
        if s == target:
            return [left + 1, right + 1]
        if s < target:
            left += 1
        else:
            right -= 1
    return []
```

## 2. Move Zeroes (LeetCode 283)

**🟢 Easy.** Move all zeros to the end of `nums` **in place**, keeping the relative order of the non-zero elements.

```text
nums = [0,1,0,3,12] → [1,3,12,0,0]
```

**Approach.** Read/write pointers: copy every non-zero to `write` and advance it; then fill the rest with zeros. (A swap-based version does it in one pass.)

**Complexity.** O(n) time, O(1) space.

```typescript
function moveZeroes(nums: number[]): void {
  let write = 0;
  for (let read = 0; read < nums.length; read++) {
    if (nums[read] !== 0) {
      [nums[write], nums[read]] = [nums[read], nums[write]];
      write++;
    }
  }
}
```

```python
def move_zeroes(nums):
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1
```

## 3. 3Sum (LeetCode 15)

**🟠 Medium.** Return all **unique** triplets `[a, b, c]` from `nums` with `a + b + c = 0`.

```text
nums = [-1,0,1,2,-1,-4] → [[-1,-1,2],[-1,0,1]]
```

**Approach.** Sort. For each index `i` (skipping duplicate values), run two pointers on the rest looking for `−nums[i]`. After finding a triplet, move both pointers and skip equal values so no triplet repeats. Stop early once `nums[i] > 0`.

**Complexity.** O(n²) time, O(1) extra space besides the output (sorting may use O(n)).

```typescript
function threeSum(input: number[]): number[][] {
  const nums = [...input].sort((a, b) => a - b);
  const res: number[][] = [];
  for (let i = 0; i < nums.length - 2; i++) {
    if (nums[i] > 0) break;
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    let left = i + 1, right = nums.length - 1;
    while (left < right) {
      const s = nums[i] + nums[left] + nums[right];
      if (s < 0) left++;
      else if (s > 0) right--;
      else {
        res.push([nums[i], nums[left], nums[right]]);
        left++; right--;
        while (left < right && nums[left] === nums[left - 1]) left++;
      }
    }
  }
  return res;
}
```

```python
def three_sum(nums):
    nums = sorted(nums)
    res = []
    for i in range(len(nums) - 2):
        if nums[i] > 0:
            break
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        left, right = i + 1, len(nums) - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s < 0:
                left += 1
            elif s > 0:
                right -= 1
            else:
                res.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
    return res
```

## 4. Container With Most Water (LeetCode 11)

**🟠 Medium.** `height[i]` is a vertical line at x = i. Pick two lines that, with the x-axis, hold the most water; return that area.

```text
height = [1,8,6,2,5,4,8,3,7] → 49
```

**Approach.** Start with the widest container (`left = 0`, `right = n − 1`). The area is limited by the **shorter** line, so moving the taller line inward can only shrink the width without raising the limit. Always move the shorter one.

**Complexity.** O(n) time, O(1) space.

```typescript
function maxArea(height: number[]): number {
  let left = 0, right = height.length - 1, best = 0;
  while (left < right) {
    best = Math.max(best, (right - left) * Math.min(height[left], height[right]));
    if (height[left] < height[right]) left++; else right--;
  }
  return best;
}
```

```python
def max_area(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        best = max(best, (right - left) * min(height[left], height[right]))
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best
```

## 5. Trapping Rain Water (LeetCode 42)

**🔴 Hard.** Given bar heights, compute how much rainwater is trapped between them.

```text
height = [0,1,0,2,1,0,1,3,2,1,2,1] → 6
```

**Approach.** Water above bar i = `min(maxLeft, maxRight) − height[i]`. With two pointers, keep `leftMax` and `rightMax`. Whichever side has the **smaller** max is the bottleneck, and that side's water is known exactly (the other side has at least that tall a wall). Process that side and move inward.

**Complexity.** O(n) time, O(1) space (versus O(n) space for the prefix-max/suffix-max arrays solution).

```typescript
function trap(height: number[]): number {
  let left = 0, right = height.length - 1, leftMax = 0, rightMax = 0, water = 0;
  while (left < right) {
    if (height[left] < height[right]) {
      leftMax = Math.max(leftMax, height[left]);
      water += leftMax - height[left++];
    } else {
      rightMax = Math.max(rightMax, height[right]);
      water += rightMax - height[right--];
    }
  }
  return water;
}
```

```python
def trap(height):
    left, right = 0, len(height) - 1
    left_max = right_max = water = 0
    while left < right:
        if height[left] < height[right]:
            left_max = max(left_max, height[left])
            water += left_max - height[left]
            left += 1
        else:
            right_max = max(right_max, height[right])
            water += right_max - height[right]
            right -= 1
    return water
```

## 6. Sort Colors (LeetCode 75)

**🟠 Medium.** Sort an array of 0s, 1s and 2s in place in one pass (no library sort).

```text
nums = [2,0,2,1,1,0] → [0,0,1,1,2,2]
```

**Approach.** Dutch national flag with three pointers: everything before `low` is 0, everything after `high` is 2, `mid` scans. A 0 swaps to `low` (both advance), a 2 swaps to `high` (only `high` moves, because the swapped-in value hasn't been examined), a 1 just advances `mid`.

**Complexity.** O(n) time, O(1) space.

```typescript
function sortColors(nums: number[]): void {
  let low = 0, mid = 0, high = nums.length - 1;
  while (mid <= high) {
    if (nums[mid] === 0) { [nums[low], nums[mid]] = [nums[mid], nums[low]]; low++; mid++; }
    else if (nums[mid] === 2) { [nums[mid], nums[high]] = [nums[high], nums[mid]]; high--; }
    else mid++;
  }
}
```

```python
def sort_colors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 2:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
        else:
            mid += 1
```