Skip to main content

Subjects

Two Pointers — Solving Array Problems in O(n)

two-pointersarraysalgorithmsbeginnerfree
The two pointers technique — a simple pattern that solves a surprising number of array and string problems in linear time.
Share:

What Is the Two Pointers Technique?

The two pointers technique uses two index variables that move through an array or string, typically from opposite ends or at different speeds. It reduces problems that look like they need O(n²) nested loops down to a single O(n) pass.

It works when the data has some ordering or structure you can exploit — a sorted array, a linked list, or a string with specific properties.

Two Patterns

Opposite Ends

One pointer starts at the beginning, the other at the end. They move toward each other. Classic use: Two Sum on a sorted array — if the sum is too small, move the left pointer right. If too large, move the right pointer left.

Fast and Slow

Both pointers start at the same end but move at different speeds. Classic use: cycle detection in a linked list (Floyd’s tortoise and hare) or removing duplicates from a sorted array in place.

python
def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            print(f"Found: arr[{left}]={arr[left]} + arr[{right}]={arr[right]} = {target}")
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    print("No pair found")
    return []

sorted_arr = [1, 3, 5, 7, 9, 11, 15]
two_sum_sorted(sorted_arr, 12)
two_sum_sorted(sorted_arr, 20)
two_sum_sorted(sorted_arr, 100)
python
def remove_duplicates(arr):
    if not arr:
        return 0
    slow = 0
    for fast in range(1, len(arr)):
        if arr[fast] != arr[slow]:
            slow += 1
            arr[slow] = arr[fast]
    result = arr[:slow + 1]
    print(f"Unique elements: {result}")
    return slow + 1

data = [1, 1, 2, 3, 3, 3, 4, 5, 5]
count = remove_duplicates(data)
print(f"Count of unique: {count}")

Key Takeaways

  • Two pointers reduces O(n²) to O(n) when the data has exploitable structure (sorted, linked list, etc.).
  • Opposite ends: converge from both sides. Use for pair-finding on sorted arrays.
  • Fast and slow: different speeds from the same start. Use for deduplication, cycle detection, finding the middle.
  • O(1) extra space — two pointers is an in-place technique.