DSA Two Pointers

The two pointers technique uses two index markers that travel through a list. Each marker points at one item. Moving the markers by simple rules replaces a slow nested loop with a single pass.

Imagine two friends walking toward each other along a corridor of numbered doors. One starts at the left end and the other starts at the right end. They compare notes at each step and decide who moves. Neither friend ever walks backward, so the search finishes quickly.

Why Use Two Pointers

A beginner often checks every pair of items with two loops. That approach costs O(n²) time. Two pointers cut the cost to O(n) for many problems, especially those with sorted data or pairs.

Pattern 1: Pointers From Both Ends

Place one pointer at the start and one at the end. Move them toward the middle based on a condition.

Example: Find a Pair With a Given Sum

A sorted list holds [2, 4, 7, 11, 15]. The goal is to find two numbers that add up to 18.

def pair_with_sum(numbers, target):
    left = 0
    right = len(numbers) - 1
    while left < right:
        current = numbers[left] + numbers[right]
        if current == target:
            return (numbers[left], numbers[right])
        if current < target:
            left += 1
        else:
            right -= 1
    return None

print(pair_with_sum([2, 4, 7, 11, 15], 18))   # (7, 11)

Target = 18

[2, 4, 7, 11, 15]
 L              R     2 + 15 = 17  (too small, move L)

[2, 4, 7, 11, 15]
    L           R     4 + 15 = 19  (too big, move R)

[2, 4, 7, 11, 15]
    L       R         4 + 11 = 15  (too small, move L)

[2, 4, 7, 11, 15]
       L    R         7 + 11 = 18  (match)

A sorted list gives each move a clear meaning. Moving the left pointer raises the sum. Moving the right pointer lowers it.

Example: Reverse a List In Place

def reverse_list(items):
    left = 0
    right = len(items) - 1
    while left < right:
        items[left], items[right] = items[right], items[left]
        left += 1
        right -= 1

data = [1, 2, 3, 4, 5]
reverse_list(data)
print(data)   # [5, 4, 3, 2, 1]

Pattern 2: Slow and Fast Pointers

Both pointers start at the beginning. The fast pointer scans every item. The slow pointer marks the spot where the next useful value belongs.

Example: Remove Duplicates From a Sorted List

def remove_duplicates(numbers):
    if not numbers:
        return 0
    slow = 0
    for fast in range(1, len(numbers)):
        if numbers[fast] != numbers[slow]:
            slow += 1
            numbers[slow] = numbers[fast]
    return slow + 1

data = [1, 1, 2, 2, 3]
size = remove_duplicates(data)
print(data[:size])   # [1, 2, 3]

[1, 1, 2, 2, 3]
 S  F              same value, skip
 S     F           new value, copy next to S
[1, 2, 2, 2, 3]
    S     F        same value, skip
    S        F     new value, copy next to S
[1, 2, 3, 2, 3]
       S           first 3 items are unique

The list changes in place, so extra memory stays at O(1).

Pattern 3: Check a Palindrome

Two pointers compare characters from the outside toward the center.

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

print(is_palindrome("racecar"))   # True

When to Use This Technique

• The data is sorted, or sorting it first helps.
• The problem asks for a pair or a triplet that meets a condition.
• The task needs in-place changes with no extra list.
• A brute-force solution uses two nested loops.

Complexity Summary

• Time: O(n), since each pointer crosses the list at most once.
• Space: O(1), since only two index variables are stored.
• Sorting first adds O(n log n) when the input arrives unsorted.

Real-Life Uses

A spell checker can compare a typed word against a dictionary entry from both ends. A shopping app can find two products whose prices add up to a gift card balance. A file cleaner can remove repeated entries from a sorted list without creating a copy. Each task follows the same pointer rules shown above.

Common Mistakes

Many learners apply opposite-end pointers to unsorted data, and the movement rules stop making sense. Sort the list first or choose a different method. Another slip involves using left <= right instead of left < right, which makes a pointer compare an item with itself. Trace a three-item list by hand to confirm the loop ends correctly.

Key Points

• Two pointers replace nested loops with one pass.
• Opposite-end pointers suit sorted pairs and palindromes.
• Slow and fast pointers suit in-place cleanup tasks.
• Each pointer moves by a clear rule and never needs to return.
• The method uses constant extra space.