Two Pointers Templates in Python

What is two pointers technique?

Two pointer technique is using two pointers in an array to solve problems efficiently.

Templates

3 common two pointers techniques are:

• Sliding window
• Pointers from two ends
• Fast and slow pointers

Sliding Window

Sliding window can be used to search something in a subarray.

def get_counter():
    pass

def condition():
    pass

def do_something_before():
    pass

def do_something_after():
    pass

def sliding_window(arr):
    counter = get_counter()
    # outer loop to move end index
    while end < len(arr):
        end += 1
        # start index only increase when condition
        while condition():
            do_something_before()
            start += 1
    do_something_after()

Pointers from two ends

Pointers from two ends can be used when the problem can be reduced to finding two elements in an array that satisfy a condition.

def condition_left():
    pass

def condition_right():
    pass

def do_something():
    pass

def pointers_from_two_ends(arr):
    left, right = 0, len(arr)-1
    while left < right:
        if condition_left():
            left += 1
        if condition_right():
            right -= 1
        do_something()

Fast and slow pointers

Fast and slow pointers can be used to:

• detect cycles
• remove duplicates
• find middle node

def condition_slow():
    pass

def do_something():
    pass

def fast_slow_pointers(arr):
    slow = 0
    for fast in range(len(arr)):
        # only move slow pointer when condition
        if condition_slow():
            slow += 1
        do_something()