Two-Pointer Technique

Jr Codex DSA Notes

Level: Beginner–Intermediate Prerequisites: Chapter 2 Time to complete: ~25 minutes

Table of Contents

1. What Two-Pointer Solves
2. Opposite-Direction Pointers
3. Worked Example: Reverse an Array In Place
4. Worked Example: Pair Sum in a Sorted Array
5. Worked Example: Palindrome Check
6. Same-Direction Pointers
7. Worked Example: Remove Duplicates from a Sorted Array
8. Recognizing When to Reach for Two-Pointer
9. Summary & Next Steps

1. What Two-Pointer Solves

A brute-force approach to many array problems checks every pair of elements — O(n²). The two-pointer technique uses two index variables that move through the array according to a rule, solving the same problem in a single O(n) pass. It's the single highest-yield pattern for turning a nested-loop solution into a linear one.

2. Opposite-Direction Pointers

One pointer starts at the beginning, one at the end, and they move toward each other:

[10, 20, 30, 40, 50]
 ^left            ^right

This shape works whenever the array is sorted (or you're comparing from both ends inward).

3. Worked Example: Reverse an Array In Place

def reverse_in_place(items):
    left, right = 0, len(items) - 1
    while left < right:
        items[left], items[right] = items[right], items[left]
        left += 1
        right -= 1
    return items
    # O(n) time, O(1) auxiliary space — no new array built

4. Worked Example: Pair Sum in a Sorted Array

Given a sorted array, find two numbers that add up to a target:

def pair_sum(sorted_items, target):
    left, right = 0, len(sorted_items) - 1
    while left < right:
        current = sorted_items[left] + sorted_items[right]
        if current == target:
            return (left, right)
        elif current < target:
            left += 1        # sum too small — need a bigger number, move left up
        else:
            right -= 1        # sum too big — need a smaller number, move right down
    return None
    # O(n) time, O(1) space — vs. O(n²) checking every pair

The brute-force version checks all n(n-1)/2 pairs — O(n²). Because the array is sorted, moving a pointer inward lets you eliminate a whole set of impossible pairs in one step, dropping to O(n).

5. Worked Example: Palindrome Check

def is_palindrome(text):
    left, right = 0, len(text) - 1
    while left < right:
        if text[left] != text[right]:
            return False
        left += 1
        right -= 1
    return True
    # O(n) time, O(1) space

6. Same-Direction Pointers

Both pointers start at the beginning; one (often called the "slow" pointer) only advances when a condition is met, while the other (the "fast" pointer) always advances:

[1, 1, 2, 2, 3]
 ^slow
 ^fast

This shape is used to compact or filter a list in place.

7. Worked Example: Remove Duplicates from a Sorted Array

def remove_duplicates(sorted_items):
    if not sorted_items:
        return 0
 
    slow = 0
    for fast in range(1, len(sorted_items)):
        if sorted_items[fast] != sorted_items[slow]:
            slow += 1
            sorted_items[slow] = sorted_items[fast]
    return slow + 1       # new length of the deduplicated prefix
    # O(n) time, O(1) space — modifies the array in place
 
items = [1, 1, 2, 2, 2, 3]
new_length = remove_duplicates(items)
print(items[:new_length])    # [1, 2, 3]

slow marks the boundary of the "clean" prefix built so far; fast scans ahead looking for the next genuinely new value. This same-direction shape reappears constantly — it's also the basis for Module 6's cycle-detection technique (fast/slow pointers on a linked list).

8. Recognizing When to Reach for Two-Pointer

Reach for two-pointer when you see:

• A sorted array and a problem about pairs, triplets, or sums.
• "In place" or "without extra space" in the problem statement.
• A palindrome or symmetry check.
• Compacting/filtering a list based on a condition, especially on sorted input.

9. Summary & Next Steps

Key Takeaways

• Two-pointer converts many O(n²) brute-force array problems into O(n) with O(1) space.
• Opposite-direction pointers (converging inward) suit sorted-array and symmetry problems.
• Same-direction pointers (slow/fast) suit in-place compaction and filtering.
• Sortedness and "in place" are the two strongest signals to reach for this pattern.

Concept Check

1. Why does pair-sum-in-a-sorted-array only work correctly because the array is sorted?
2. In the remove-duplicates example, what does the slow pointer represent at any point during the loop?
3. What's the time/space complexity improvement two-pointer typically achieves over the brute-force nested-loop version?

Next Chapter

→ Chapter 4: Sliding Window Technique

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index