Two Pointer: Advanced Patterns and Templates

The two-pointer technique is one of the most versatile tools in your DSA toolkit. Instead of brute-forcing with nested loops (O(n^2)), two pointers often reduce the problem to a single pass (O(n)). The key is recognizing which pattern to apply.

Pattern 1: opposite direction

Two pointers start at opposite ends and move toward each other. This works on sorted arrays or when you need to compare elements from both ends.

Template

def opposite_direction(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        # Process arr[left] and arr[right]
        if condition_met(arr[left], arr[right]):
            # Record answer
            left += 1   # or right -= 1, or both
        elif need_larger:
            left += 1
        else:
            right -= 1

Two sum (sorted array)

def two_sum_sorted(numbers, target):
    """
    Find two numbers that add up to target in a sorted array.
    Time: O(n), Space: O(1)
    """
    left, right = 0, len(numbers) - 1

    while left < right:
        current_sum = numbers[left] + numbers[right]

        if current_sum == target:
            return [left + 1, right + 1]  # 1-indexed
        elif current_sum < target:
            left += 1    # Need a larger sum
        else:
            right -= 1   # Need a smaller sum

    return []


print(two_sum_sorted([2, 7, 11, 15], 9))   # [1, 2]
print(two_sum_sorted([2, 3, 4], 6))         # [1, 3]

Why it works: Since the array is sorted, moving left right increases the sum, and moving right left decreases it. This gives us directed search instead of checking all pairs.

Container with most water

def max_area(height):
    """
    Find two lines that form a container holding the most water.
    Time: O(n), Space: O(1)
    """
    left, right = 0, len(height) - 1
    best = 0

    while left < right:
        width = right - left
        h = min(height[left], height[right])
        best = max(best, width * h)

        # Move the shorter line inward
        # Moving the taller line can never increase area
        # because height is limited by the shorter line
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return best


print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49

Key insight: Always move the pointer at the shorter line. The width decreases by 1 each step, so the only way to get more area is a taller minimum height.

Valid palindrome

def is_palindrome(s):
    """
    Check if string is a palindrome, ignoring non-alphanumeric.
    Time: O(n), Space: O(1)
    """
    left, right = 0, len(s) - 1

    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1

        if s[left].lower() != s[right].lower():
            return False

        left += 1
        right -= 1

    return True


print(is_palindrome("A man, a plan, a canal: Panama"))  # True
print(is_palindrome("race a car"))                       # False

Trapping rain water

def trap(height):
    """
    Calculate trapped rainwater using two pointers.
    Time: O(n), Space: O(1)
    """
    if not height:
        return 0

    left, right = 0, len(height) - 1
    left_max, right_max = height[left], height[right]
    water = 0

    while left < right:
        if left_max < right_max:
            left += 1
            left_max = max(left_max, height[left])
            water += left_max - height[left]
        else:
            right -= 1
            right_max = max(right_max, height[right])
            water += right_max - height[right]

    return water


print(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))  # 6

Why two pointers work here: Water at any position depends on the minimum of the maximum heights on both sides. We track running maximums from each end and process the side with the smaller maximum, since that side determines the water level.

Three sum

def three_sum(nums):
    """
    Find all unique triplets that sum to zero.
    Time: O(n^2), Space: O(1) extra
    """
    nums.sort()
    result = []

    for i in range(len(nums) - 2):
        # Skip duplicates for first element
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left, right = i + 1, len(nums) - 1
        target = -nums[i]

        while left < right:
            current = nums[left] + nums[right]
            if current == target:
                result.append([nums[i], nums[left], nums[right]])
                # Skip duplicates
                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 current < target:
                left += 1
            else:
                right -= 1

    return result


print(three_sum([-1, 0, 1, 2, -1, -4]))
# [[-1, -1, 2], [-1, 0, 1]]

Pattern 2: same direction (slow-fast)

Both pointers move in the same direction, but at different speeds or conditions. The slow pointer marks the position for the next valid element, while the fast pointer scans ahead.

Template

def same_direction(arr):
    slow = 0
    for fast in range(len(arr)):
        if should_keep(arr[fast]):
            arr[slow] = arr[fast]
            slow += 1
    return slow  # New length

Remove duplicates from sorted array

def remove_duplicates(nums):
    """
    Remove duplicates in-place, return new length.
    Time: O(n), Space: O(1)
    """
    if not nums:
        return 0

    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]

    return slow + 1


nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
length = remove_duplicates(nums)
print(f"Length: {length}, Array: {nums[:length]}")
# Length: 5, Array: [0, 1, 2, 3, 4]

Remove duplicates allowing at most K

def remove_duplicates_k(nums, k=2):
    """
    Allow at most k occurrences of each element.
    Time: O(n), Space: O(1)
    """
    if len(nums) <= k:
        return len(nums)

    slow = k
    for fast in range(k, len(nums)):
        if nums[fast] != nums[slow - k]:
            nums[slow] = nums[fast]
            slow += 1

    return slow


nums = [1, 1, 1, 2, 2, 3]
length = remove_duplicates_k(nums, k=2)
print(f"Length: {length}, Array: {nums[:length]}")
# Length: 5, Array: [1, 1, 2, 2, 3]

Move zeroes

def move_zeroes(nums):
    """
    Move all zeroes to the end while maintaining order.
    Time: O(n), Space: O(1)
    """
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1


nums = [0, 1, 0, 3, 12]
move_zeroes(nums)
print(nums)  # [1, 3, 12, 0, 0]

Remove element

def remove_element(nums, val):
    """
    Remove all occurrences of val in-place.
    Time: O(n), Space: O(1)
    """
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != val:
            nums[slow] = nums[fast]
            slow += 1
    return slow


nums = [3, 2, 2, 3]
length = remove_element(nums, 3)
print(f"Length: {length}, Array: {nums[:length]}")
# Length: 2, Array: [2, 2]

Pattern 3: fast-slow (Floyd’s)

Two pointers move at different speeds through a linked list or sequence. The fast pointer moves 2 steps while the slow pointer moves 1 step.

Detect cycle in linked list

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def has_cycle(head):
    """
    Floyd's cycle detection algorithm.
    Time: O(n), Space: O(1)
    """
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True

    return False

Why it works: If there is a cycle, the fast pointer enters the cycle first and laps the slow pointer. Since fast gains one position per step, they must eventually meet. If there is no cycle, fast reaches the end.

Find the start of a cycle

def detect_cycle(head):
    """
    Find the node where the cycle begins.
    Time: O(n), Space: O(1)
    """
    slow = fast = head

    # Phase 1: detect cycle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # No cycle

    # Phase 2: find cycle start
    # Move one pointer back to head
    # Both advance one step at a time
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next

    return slow  # Cycle start

Math behind it: Let the distance from head to cycle start be a, cycle length be c, and the meeting point be b steps into the cycle. Fast traveled a + b + k*c and slow traveled a + b. Since fast moves twice as fast: 2(a + b) = a + b + k*c, so a + b = k*c, meaning a = k*c - b. Starting from the meeting point and advancing a steps lands at the cycle start.

Find middle of linked list

def find_middle(head):
    """
    Find the middle node. For even-length lists,
    returns the second middle node.
    Time: O(n), Space: O(1)
    """
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

Happy number

def is_happy(n):
    """
    A happy number eventually reaches 1 when you repeatedly
    replace it with the sum of squares of its digits.
    Uses Floyd's cycle detection.
    Time: O(log n), Space: O(1)
    """
    def get_next(num):
        total = 0
        while num > 0:
            digit = num % 10
            total += digit * digit
            num //= 10
        return total

    slow = n
    fast = get_next(n)

    while fast != 1 and slow != fast:
        slow = get_next(slow)
        fast = get_next(get_next(fast))

    return fast == 1


print(is_happy(19))  # True (19->82->68->100->1)
print(is_happy(2))   # False (enters cycle)

Pattern 4: three pointers (Dutch National Flag)

The Dutch National Flag algorithm uses three pointers to partition an array into three sections in a single pass.

Sort colors

def sort_colors(nums):
    """
    Sort array of 0s, 1s, and 2s in-place.
    Dutch National Flag algorithm.
    Time: O(n), Space: O(1)

    Invariants:
    - [0, low): all 0s
    - [low, mid): all 1s
    - [mid, high]: unprocessed
    - (high, n): all 2s
    """
    low, mid, high = 0, 0, len(nums) - 1

    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:  # nums[mid] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
            # Don't increment mid - need to check swapped element


nums = [2, 0, 2, 1, 1, 0]
sort_colors(nums)
print(nums)  # [0, 0, 1, 1, 2, 2]

Why mid does not increment when swapping with high: The element swapped from position high has not been examined yet. It could be 0, 1, or 2, so we must check it before moving on.

Partition array around pivot

def partition_three_way(arr, pivot):
    """
    Partition array into elements < pivot, == pivot, > pivot.
    Time: O(n), Space: O(1)
    """
    low, mid, high = 0, 0, len(arr) - 1

    while mid <= high:
        if arr[mid] < pivot:
            arr[low], arr[mid] = arr[mid], arr[low]
            low += 1
            mid += 1
        elif arr[mid] == pivot:
            mid += 1
        else:
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1

    return arr


print(partition_three_way([3, 5, 2, 7, 1, 5, 8, 5], 5))
# Elements < 5, then 5s, then > 5

Choosing the right pattern

Scenario	Pattern	Examples
Sorted array, find pair	Opposite direction	Two Sum, 3Sum
Compare from both ends	Opposite direction	Palindrome, Container
In-place removal/dedup	Same direction	Remove duplicates, Move zeroes
Linked list cycle	Fast-slow	Cycle detection, Find middle
3-way partition	Three pointers	Sort colors, DNF
Subsequence check	Same direction	Is Subsequence

Advanced: merge two sorted arrays in-place

def merge_sorted(nums1, m, nums2, n):
    """
    Merge nums2 into nums1 (which has extra space at the end).
    Use opposite-direction from the END to avoid overwriting.
    Time: O(m + n), Space: O(1)
    """
    p1, p2, p = m - 1, n - 1, m + n - 1

    while p1 >= 0 and p2 >= 0:
        if nums1[p1] > nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
        p -= 1

    # Copy remaining elements from nums2
    nums1[:p2 + 1] = nums2[:p2 + 1]


nums1 = [1, 2, 3, 0, 0, 0]
merge_sorted(nums1, 3, [2, 5, 6], 3)
print(nums1)  # [1, 2, 2, 3, 5, 6]

Complexity summary

Problem	Brute Force	Two Pointer
Two Sum (sorted)	O(n^2)	O(n)
Container With Most Water	O(n^2)	O(n)
Three Sum	O(n^3)	O(n^2)
Remove Duplicates	O(n) extra space	O(1) space
Cycle Detection	O(n) space (hash set)	O(1) space
Sort Colors	O(n log n) general sort	O(n) single pass
Trapping Rain Water	O(n) with extra arrays	O(1) space

Practice problems

Problem	Pattern	Difficulty
Two Sum II (LC 167)	Opposite	Easy
Valid Palindrome (LC 125)	Opposite	Easy
Move Zeroes (LC 283)	Same direction	Easy
Remove Duplicates (LC 26)	Same direction	Easy
Linked List Cycle (LC 141)	Fast-slow	Easy
Container With Most Water (LC 11)	Opposite	Medium
3Sum (LC 15)	Opposite	Medium
Sort Colors (LC 75)	Three pointer	Medium
Trapping Rain Water (LC 42)	Opposite	Hard
Remove Duplicates II (LC 80)	Same direction	Medium
Linked List Cycle II (LC 142)	Fast-slow	Medium
Happy Number (LC 202)	Fast-slow	Easy

Key takeaways

1. Opposite direction works when the array is sorted or you need to compare from both ends. Both pointers converge toward the middle.
2. Same direction works for in-place modifications. The slow pointer marks where the next valid element goes.
3. Fast-slow works for cycle detection and finding midpoints in linked lists. The speed difference guarantees they meet if a cycle exists.
4. Three pointers extend the pattern for three-way partitioning.
5. Two pointers almost always reduce time complexity by one factor of n compared to brute force.