Two Pointers

---

When to Use

• Sorted array or string — find a pair satisfying a condition
• In-place element removal or rearrangement
• Comparing elements from both ends simultaneously
• Avoid O(n²) brute force on array pair problems

Signal phrases: "sorted array", "pair that sums to", "in-place", "palindrome", "container", "trap", "remove duplicates"

---

Patterns

1. Opposite Ends (Converging)

Start one pointer at left, one at right — move inward based on condition.

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

Key insight: Works because array is sorted — moving left pointer up increases sum, moving right pointer down decreases it. Guaranteed to find the pair if it exists.

---

2. Same Direction (Fast / Slow)

Both pointers start at left — fast pointer scouts ahead, slow pointer marks the "write position".

# Remove duplicates in-place from sorted array
def remove_duplicates(nums):
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

# Move zeroes to end, maintain relative order
def move_zeroes(nums):
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1

Key insight: slow is always the last "valid" position. fast scans everything. When fast finds something useful, copy it to slow and advance slow.

---

3. Three Pointers (Fix one + Two Pointer on the rest)

Fix the outer element at index i, run two-pointer on i+1 to end.

def three_sum(nums):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue                          # skip outer duplicates
        left, right = i + 1, len(nums) - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left+1]: left += 1
                while left < right and nums[right] == nums[right-1]: right -= 1
                left += 1; right -= 1
            elif s < 0:
                left += 1
            else:
                right -= 1
    return result

Key insight: Skip duplicates at both the outer loop (i) AND the inner pointers after a match — otherwise you get duplicate triplets in the result.

---

4. Two Pointer with Height Tracking (Container / Trapping Water)

Move the pointer on the smaller side — the larger side can only get worse if you move it.

# LC 11 — Container With Most Water
def maxArea(height):
    left, right = 0, len(height) - 1
    max_water = 0
    while left < right:
        water = min(height[left], height[right]) * (right - left)
        max_water = max(max_water, water)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_water

# LC 42 — Trapping Rain Water (O(1) space)
def trap(height):
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0
    while left <= right:           # <= not < — meeting point must be processed
        if left_max <= right_max:
            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

Key insight — why move the smaller side? The water/area is bounded by the shorter wall. Moving the taller side inward can only decrease width without any guarantee of a taller replacement. Moving the shorter side is the only move that could improve the result.

Key insight — while left <= right (not <): When left == right, both pointers are at the same bar — this is the peak. If you skip it with <, you miss the water it can trap. The meeting point must be processed.

---

Key Problems

---

Complexity

• Time: O(n) — single pass, two pointers together traverse the array once
• Space: O(1) — in-place, no extra structures

Sorting prerequisite: Converging two-pointer problems usually require a sorted array. If unsorted — either sort first O(n log n) or use a hashmap instead.