Data Structures & AlgorithmsTwo-Pointer Technique

The Two-Pointer Technique

LevelIntermediate

Duration60 mins

TopicTwo-Pointer Technique

2 / 5

Same-Direction Pointers (Fast and Slow)

When Two Pointers March in the Same Direction

Some of the most elegant algorithmic solutions come from a deceptively simple idea: what if both pointers start at the same position and move in the same direction, but one moves faster than the other?

This same-direction two-pointer pattern (often called the fast and slow pointer technique or tortoise and hare) is the backbone of:

Removing duplicates from sorted arrays in-place
Partitioning arrays around a pivot
Detecting cycles in linked lists
Finding the middle element without knowing the length
In-place array transformations

The key insight is that by having two pointers move at different speeds or under different conditions, you create a read position and a write position that let you transform data in a single pass without extra memory.

What You Will Learn

This page covers the same-direction two-pointer pattern exhaustively: the conceptual model, why it achieves O(n) time with O(1) space, the reader-writer paradigm, and detailed walkthroughs of fundamental problems. You'll understand when and how to apply this pattern confidently.

The Core Mental Model

Same-direction two-pointer algorithms typically follow a reader-writer paradigm:

Fast pointer (reader): Scans through the array, examining each element
Slow pointer (writer): Tracks the position where the next valid element should go

The fast pointer runs ahead, deciding which elements to keep. The slow pointer follows behind, collecting only the keepers. At the end, everything up to the slow pointer contains the result.

Visual metaphor: Imagine two people in a library. The fast person quickly scans book spines, calling out which ones to keep. The slow person follows with a cart, collecting only the called-out books. By the time they reach the end, the cart contains exactly what's needed.

reader_writer_paradigm.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def generic_same_direction_pattern(arr):
    """
    Generic template for same-direction two-pointer.
    
    slow = write position (where valid elements go)
    fast = read position (examines every element)
    """
    slow = 0  # Position for next valid element
    
    for fast in range(len(arr)):
        if should_keep(arr[fast]):  # Condition varies by problem
            arr[slow] = arr[fast]   # Write the keeper
            slow += 1               # Advance write position
    
    # After loop: arr[0:slow] contains valid elements
    return slow  # New logical length
 
def should_keep(element):
    """Problem-specific predicate."""
    pass

Why this works:

The fast pointer visits each element exactly once → O(n) reads
The slow pointer writes at most n times (once per element) → O(n) writes
Total time: O(n)
We only use two index variables → O(1) space

Key invariant: At any point, arr[0:slow] contains all valid elements seen so far, in order.

Classic Problem: Remove Duplicates from Sorted Array

Problem Statement: Given a sorted array, remove duplicates in-place such that each unique element appears only once. Return the new length. The array modification must happen in-place with O(1) extra memory.

Example:

Input:  [1, 1, 2, 2, 2, 3]
Output: 3  (array becomes [1, 2, 3, ...])

This is the quintessential same-direction two-pointer problem.

Why In-Place?

In-place modification is crucial when you can't afford O(n) extra space—common in embedded systems, memory-constrained environments, or when processing massive datasets. The two-pointer technique achieves O(1) space by overwriting elements that are no longer needed.

Algorithm Design:

Initialize slow = 1 (first element is always unique, start writing at index 1)
Scan with fast from index 1 to end
If arr[fast] != arr[fast - 1], this is a new unique element:
- Copy it to position slow
- Increment slow
Return slow as the new length

remove_duplicates.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
def remove_duplicates(nums: list[int]) -> int:
    """
    Remove duplicates from sorted array in-place.
    
    Time: O(n) - single pass through the array
    Space: O(1) - only two pointers used
    
    Args:
        nums: Sorted array (modified in-place)
    
    Returns:
        New length after removing duplicates
    """
    if len(nums) == 0:
        return 0
    
    # First element is always unique
    # slow points to the position for next unique element
    slow = 1
    
    for fast in range(1, len(nums)):
        # If current element differs from previous, it's unique
        if nums[fast] != nums[fast - 1]:
            nums[slow] = nums[fast]  # Write unique element
            slow += 1                 # Advance write position
    
    return slow  # Number of unique elements
 
# Detailed trace
def remove_duplicates_verbose(nums: list[int]) -> int:
    """Same algorithm with step-by-step trace."""
    if len(nums) == 0:
        return 0
    
    print(f"Initial array: {nums}")
    slow = 1
    
    for fast in range(1, len(nums)):
        print(f"\nfast={fast}, slow={slow}")
        print(f"  Comparing nums[{fast}]={nums[fast]} with nums[{fast-1}]={nums[fast-1]}")
        
        if nums[fast] != nums[fast - 1]:
            print(f"  Different! Writing nums[{slow}] = {nums[fast]}")
            nums[slow] = nums[fast]
            slow += 1
            print(f"  Array now: {nums}, slow advances to {slow}")
        else:
            print(f"  Same, skipping")
    
    print(f"\nFinal: {slow} unique elements in {nums[:slow]}")
    return slow
 
# Example
nums = [1, 1, 2, 2, 2, 3]
length = remove_duplicates_verbose(nums)
print(f"\nResult: length={length}, array={nums[:length]}")

Step-by-Step Execution: [1, 1, 2, 2, 2, 3]
fast	slow	nums[fast]	nums[fast-1]	Different?	Action	Result Array
1	1	1	1	No	Skip	[1, 1, 2, 2, 2, 3]
2	1	2	1	Yes	Write & advance	[1, 2, 2, 2, 2, 3]
3	2	2	2	No	Skip	[1, 2, 2, 2, 2, 3]
4	2	2	2	No	Skip	[1, 2, 2, 2, 2, 3]
5	2	3	2	Yes	Write & advance	[1, 2, 3, 2, 2, 3]

Final result: slow = 3, meaning the first 3 elements [1, 2, 3] are the unique values.

Notice that elements after index 3 are "garbage"—they contain old values that we don't care about. The contract is that elements [0, slow) are valid; the rest is undefined.

Variant: Remove All Instances of a Value

Problem Statement: Given an array and a value val, remove all instances of that value in-place. Return the new length. The order of remaining elements may change (or be preserved, depending on requirements).

Example:

Input:  nums = [3, 2, 2, 3], val = 3
Output: 2  (array becomes [2, 2, ...])

This is similar to removing duplicates, but instead of comparing adjacent elements, we compare each element against a target value.

remove_element.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
def remove_element(nums: list[int], val: int) -> int:
    """
    Remove all instances of val from array in-place.
    
    Time: O(n) - single pass
    Space: O(1) - two pointers
    
    Args:
        nums: Array to modify
        val: Value to remove
    
    Returns:
        New length after removal
    """
    slow = 0  # Position for next element to keep
    
    for fast in range(len(nums)):
        if nums[fast] != val:
            nums[slow] = nums[fast]
            slow += 1
    
    return slow
 
# Example trace
nums = [3, 2, 2, 3]
val = 3
print(f"Before: {nums}")
length = remove_element(nums, val)
print(f"After:  {nums[:length]} (length={length})")
# Output: [2, 2] (length=2)
 
 
def remove_element_optimized(nums: list[int], val: int) -> int:
    """
    Optimized version: Minimize moves when elements to remove are rare.
    
    Idea: Swap unwanted elements with the last element, shrink array.
    This avoids unnecessary writes when there are many keeper elements.
    
    Time: O(n) - each element examined once
    Space: O(1)
    
    Caveat: Does NOT preserve order of remaining elements.
    """
    left = 0
    right = len(nums)
    
    while left < right:
        if nums[left] == val:
            # Swap with last element and shrink
            nums[left] = nums[right - 1]
            right -= 1
            # Don't advance left; need to check swapped element
        else:
            left += 1
    
    return left
 
# This version is faster when vals are rare:
# Original: [1, 2, 3, 4, 5] val=5 -> writes every element
# Optimized: [1, 2, 3, 4, 5] val=5 -> just shrinks, minimal writes

Choosing Between Variants

The basic version (scan and copy) always works correctly and preserves order. The swap-with-end version is faster when removals are rare but changes element order. Choose based on your requirements: if order matters, use the basic version; if performance is critical and order doesn't matter, consider the swap version.

Variant: Move Zeroes to End

Problem Statement: Given an array, move all zeroes to the end while maintaining the relative order of non-zero elements. Do this in-place.

Example:

Input:  [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]

This is a variant of "remove element" where instead of ignoring the removed elements, we need to place them at the end.

move_zeroes.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
def move_zeroes(nums: list[int]) -> None:
    """
    Move all zeroes to end while preserving non-zero order.
    
    Time: O(n) - single pass + one fill pass
    Space: O(1) - in-place
    
    Strategy: Two-pass
    1. Move all non-zeros to the front (using slow/fast pointers)
    2. Fill remaining positions with zeros
    """
    # Pass 1: Move non-zeros to front
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow] = nums[fast]
            slow += 1
    
    # Pass 2: Fill rest with zeros
    for i in range(slow, len(nums)):
        nums[i] = 0
 
 
def move_zeroes_one_pass(nums: list[int]) -> None:
    """
    Single-pass version using swaps.
    
    Time: O(n) - truly single pass
    Space: O(1) - in-place
    
    Strategy: Swap non-zeros to front as we find them.
    """
    slow = 0  # Points to the first zero (or end of non-zeros)
    
    for fast in range(len(nums)):
        if nums[fast] != 0:
            # Swap only if positions differ (avoid self-swap)
            if slow != fast:
                nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1
 
 
def move_zeroes_verbose(nums: list[int]) -> None:
    """Same as one-pass with detailed trace."""
    print(f"Initial: {nums}")
    slow = 0
    
    for fast in range(len(nums)):
        print(f"  fast={fast}, slow={slow}, nums[fast]={nums[fast]}")
        
        if nums[fast] != 0:
            if slow != fast:
                print(f"    Swapping positions {slow} and {fast}")
                nums[slow], nums[fast] = nums[fast], nums[slow]
                print(f"    Array: {nums}")
            else:
                print(f"    Same position, no swap needed")
            slow += 1
    
    print(f"Final: {nums}")
 
# Test
nums = [0, 1, 0, 3, 12]
move_zeroes_verbose(nums)

Trace: [0, 1, 0, 3, 12] with One-Pass Swap
fast	slow	nums[fast]	Action	Array State
0	0	0	Zero, skip	[0, 1, 0, 3, 12]
1	0	1	Non-zero, swap(0,1)	[1, 0, 0, 3, 12]
2	1	0	Zero, skip	[1, 0, 0, 3, 12]
3	1	3	Non-zero, swap(1,3)	[1, 3, 0, 0, 12]
4	2	12	Non-zero, swap(2,4)	[1, 3, 12, 0, 0]

The Fast-Slow for Cycle Detection (Floyd's Algorithm)

Perhaps the most famous use of same-direction pointers is Floyd's Cycle Detection Algorithm (also known as the tortoise and hare algorithm). While typically applied to linked lists, the principle extends to any sequence with potential cycles.

The Intuition:

Imagine two people running on a circular track at different speeds. No matter their starting positions, the faster runner will eventually "lap" the slower runner—they'll meet again.

Similarly, in a data structure with a cycle:

A slow pointer moves one step at a time
A fast pointer moves two steps at a time
If there's a cycle, the fast pointer will eventually catch up to the slow pointer
If there's no cycle, the fast pointer reaches the end first

Why These Specific Speeds?

If slow moves 1 step and fast moves 2 steps, their relative speed is 1 step per iteration. This guarantees they'll meet within one cycle length. Other speed ratios work too, but (1, 2) is simplest and sufficient.

cycle_detection.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
class ListNode:
    """Simple linked list node."""
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
 
def has_cycle(head: ListNode) -> bool:
    """
    Detect if a linked list has a cycle using Floyd's algorithm.
    
    Time: O(n) - at most n + (cycle length) iterations
    Space: O(1) - only two pointers
    
    Args:
        head: Start of the linked list
    
    Returns:
        True if cycle exists, False otherwise
    """
    if not head or not head.next:
        return False
    
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next          # Move 1 step
        fast = fast.next.next     # Move 2 steps
        
        if slow == fast:
            return True  # Pointers met -> cycle exists
    
    return False  # fast reached end -> no cycle
 
 
def find_cycle_start(head: ListNode) -> ListNode:
    """
    Find the node where the cycle begins.
    
    Mathematical insight:
    - Let x = distance from head to cycle start
    - Let y = distance from cycle start to meeting point
    - Let c = cycle length
    
    When they meet:
    - Slow traveled: x + y
    - Fast traveled: x + y + n*c (some number of full cycles)
    - Since fast = 2 * slow: x + y + n*c = 2(x + y)
    - Simplifying: x = n*c - y
    
    This means: distance from head to cycle start (x) equals
    distance from meeting point to cycle start (c - y + some cycles).
    
    So if we reset one pointer to head and move both at speed 1,
    they meet at the cycle start!
    """
    if not head or not head.next:
        return None
    
    # Phase 1: Detect cycle and find meeting point
    slow = fast = head
    has_cycle = False
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            has_cycle = True
            break
    
    if not has_cycle:
        return None
    
    # Phase 2: Find cycle start
    # Reset slow to head, keep fast at meeting point
    # Both move at speed 1 now
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    return slow  # Both point to cycle start
 
 
# Array version: find duplicate number
def find_duplicate(nums: list[int]) -> int:
    """
    Find the duplicate in [1, n] with n+1 elements (one duplicate).
    
    Key insight: Treat array as a linked list where nums[i] points to index nums[i].
    A duplicate means two indices point to the same location -> cycle!
    
    Time: O(n)
    Space: O(1)
    """
    # Phase 1: Find meeting point in the "cycle"
    slow = fast = 0
    
    while True:
        slow = nums[slow]           # One step
        fast = nums[nums[fast]]     # Two steps
        if slow == fast:
            break
    
    # Phase 2: Find cycle entry (the duplicate)
    slow = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    
    return slow
 
# Example: [1, 3, 4, 2, 2] -> 2 is the duplicate
print(find_duplicate([1, 3, 4, 2, 2]))  # Output: 2

The Duplicate Number Problem

The 'Find the Duplicate Number' problem is a classic example of how Floyd's cycle detection applies beyond linked lists. By treating array indices as 'next pointers', you convert an array problem into a cycle detection problem—elegant and O(1) space!

Finding the Middle Element

Another elegant application of fast-slow pointers: finding the middle of a sequence without knowing its length.

Problem: Given a linked list (length unknown), find its middle node.

Naive approach: Traverse once to count, traverse again to middle → O(2n) = O(n), but two passes.

Two-pointer approach: Fast moves 2 steps, slow moves 1 step. When fast reaches end, slow is at middle. → O(n), single pass.

find_middle.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
def find_middle(head: ListNode) -> ListNode:
    """
    Find the middle node of a linked list.
    
    For even length, returns the second middle node.
    Example: 1->2->3->4 returns node with value 3
    
    Time: O(n) - single pass
    Space: O(1) - two pointers
    """
    if not head:
        return None
    
    slow = fast = head
    
    # Fast moves twice as fast as slow
    # When fast reaches end, slow is at middle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    return slow
 
 
def find_middle_first(head: ListNode) -> ListNode:
    """
    For even length, returns the FIRST middle node.
    Example: 1->2->3->4 returns node with value 2
    
    Difference: Check fast.next.next instead of fast.next
    """
    if not head:
        return None
    
    slow = fast = head
    
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    
    return slow
 
 
# Why this works:
# If list has n nodes, fast takes n/2 steps before reaching end.
# Slow, moving half as fast, takes n/2 steps -> middle!
 
# Odd length:  1 -> 2 -> 3 -> 4 -> 5 -> null
#              s         f
#                   s              f
#                        s              [f off end]
# slow at node 3 ✓
 
# Even length: 1 -> 2 -> 3 -> 4 -> null  
#              s         f
#                   s              f [about to be off]
#                        s    [f would be at null.next = crash if not for condition]
# slow at node 3 ✓ (second middle)

For Arrays, It's Easier

With arrays, you can just calculate length / 2 since you know the length. The fast-slow technique shines for linked lists where length is unknown without traversal.

Partitioning Arrays

Same-direction two-pointers are essential for partitioning problems, where you need to rearrange elements based on some condition.

Problem: Given an array and a pivot value, rearrange it so all elements less than pivot come before elements greater than or equal to pivot.

This is the core of QuickSort's partition step and appears in many variations.

partition.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
def partition(nums: list[int], pivot: int) -> int:
    """
    Partition array around pivot value.
    
    After execution:
    - nums[0:result] contain elements < pivot
    - nums[result:] contain elements >= pivot
    
    Time: O(n) - single pass
    Space: O(1) - in-place
    """
    slow = 0  # Position for next element < pivot
    
    for fast in range(len(nums)):
        if nums[fast] < pivot:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1
    
    return slow  # Partition point
 
 
def partition_three_way(nums: list[int], pivot: int) -> tuple[int, int]:
    """
    Dutch National Flag partition: three regions.
    
    Result:
    - nums[0:low] contain elements < pivot
    - nums[low:high] contain elements == pivot
    - nums[high:] contain elements > pivot
    
    Uses THREE pointers for in-place O(n) solution.
    
    This is crucial for:
    - Handling duplicates in QuickSort
    - Dutch National Flag problem
    - Sort Colors (LeetCode 75)
    """
    low = 0           # Next position for < pivot
    mid = 0           # Current element to examine
    high = len(nums)  # Next position for > pivot (from end)
    
    while mid < high:
        if nums[mid] < pivot:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] > pivot:
            high -= 1
            nums[mid], nums[high] = nums[high], nums[mid]
            # Don't advance mid; need to examine swapped element
        else:  # nums[mid] == pivot
            mid += 1
    
    return low, high
 
 
# Example: Sort Colors (values are 0, 1, 2)
def sort_colors(nums: list[int]) -> None:
    """
    Sort array containing only 0, 1, 2 in-place.
    One-pass O(n) solution using three-way partition.
    """
    partition_three_way(nums, 1)  # Pivot on 1
 
# Test
colors = [2, 0, 2, 1, 1, 0]
sort_colors(colors)
print(colors)  # [0, 0, 1, 1, 2, 2]

Three-Way Partition for QuickSort

The three-way partition handles duplicate pivot values efficiently. Standard two-way partition degrades to O(n²) on arrays with many duplicates because it puts all duplicates on one side. Three-way partition groups them in the middle, achieving O(n log n) even with duplicates.

Summary: Same-Direction Pointers

You've now mastered the same-direction two-pointer pattern. Let's consolidate the key insights:

Key Takeaways

•Reader-Writer Paradigm — Fast pointer reads, slow pointer writes. This enables in-place transformations.
•Removing Elements — Whether removing duplicates or specific values, the pattern is: examine with fast, write with slow if it's a keeper.
•Cycle Detection — Floyd's algorithm uses fast(2x) and slow(1x) speeds to detect cycles in O(1) space.
•Finding Middle — When fast reaches end, slow is at middle. Works because fast moves 2x speed.
•Partitioning — Separate elements by condition using swap and advance pattern.
•O(n) Time, O(1) Space — The consistent theme: single pass, constant extra memory.

Same-Direction Two-Pointer Problem Types
Problem Type	Slow Pointer Role	Fast Pointer Role	Key Insight
Remove duplicates	Write position	Read position	Copy unique elements left
Remove by value	Write position	Read position	Skip matching values
Move zeroes	Non-zero destination	Current scanner	Swap non-zeros forward
Cycle detection	1x speed	2x speed	Fast catches slow in cycle
Find middle	1x speed	2x speed	When fast ends, slow is middle
Partition	Boundary marker	Current scanner	Swap elements across boundary

What's next:

In the next page, we'll explore opposite-direction pointers—where two pointers start at different ends and converge toward each other. This variant is essential for pair-finding problems, palindrome checks, and container optimization.

Page Complete

You now have a deep understanding of same-direction two-pointer techniques. These patterns form the foundation for in-place array manipulation, cycle detection, and efficient partitioning algorithms.

2 / 5

Loading learning content...

Data Structures & AlgorithmsTwo-Pointer Technique

The Two-Pointer Technique

LevelIntermediate

Duration60 mins

TopicTwo-Pointer Technique

2 / 5

Same-Direction Pointers (Fast and Slow)

When Two Pointers March in the Same Direction

This same-direction two-pointer pattern (often called the fast and slow pointer technique or tortoise and hare) is the backbone of:

Removing duplicates from sorted arrays in-place
Partitioning arrays around a pivot
Detecting cycles in linked lists
Finding the middle element without knowing the length
In-place array transformations

What You Will Learn

The Core Mental Model

Same-direction two-pointer algorithms typically follow a reader-writer paradigm:

Fast pointer (reader): Scans through the array, examining each element
Slow pointer (writer): Tracks the position where the next valid element should go

The fast pointer runs ahead, deciding which elements to keep. The slow pointer follows behind, collecting only the keepers. At the end, everything up to the slow pointer contains the result.

reader_writer_paradigm.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def generic_same_direction_pattern(arr):
    """
    Generic template for same-direction two-pointer.
    
    slow = write position (where valid elements go)
    fast = read position (examines every element)
    """
    slow = 0  # Position for next valid element
    
    for fast in range(len(arr)):
        if should_keep(arr[fast]):  # Condition varies by problem
            arr[slow] = arr[fast]   # Write the keeper
            slow += 1               # Advance write position
    
    # After loop: arr[0:slow] contains valid elements
    return slow  # New logical length
 
def should_keep(element):
    """Problem-specific predicate."""
    pass

Why this works:

The fast pointer visits each element exactly once → O(n) reads
The slow pointer writes at most n times (once per element) → O(n) writes
Total time: O(n)
We only use two index variables → O(1) space

Key invariant: At any point, arr[0:slow] contains all valid elements seen so far, in order.

Classic Problem: Remove Duplicates from Sorted Array

Example:

Input:  [1, 1, 2, 2, 2, 3]
Output: 3  (array becomes [1, 2, 3, ...])

This is the quintessential same-direction two-pointer problem.

Why In-Place?

Algorithm Design:

Initialize slow = 1 (first element is always unique, start writing at index 1)
Scan with fast from index 1 to end
If arr[fast] != arr[fast - 1], this is a new unique element:
- Copy it to position slow
- Increment slow
Return slow as the new length

remove_duplicates.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
def remove_duplicates(nums: list[int]) -> int:
    """
    Remove duplicates from sorted array in-place.
    
    Time: O(n) - single pass through the array
    Space: O(1) - only two pointers used
    
    Args:
        nums: Sorted array (modified in-place)
    
    Returns:
        New length after removing duplicates
    """
    if len(nums) == 0:
        return 0
    
    # First element is always unique
    # slow points to the position for next unique element
    slow = 1
    
    for fast in range(1, len(nums)):
        # If current element differs from previous, it's unique
        if nums[fast] != nums[fast - 1]:
            nums[slow] = nums[fast]  # Write unique element
            slow += 1                 # Advance write position
    
    return slow  # Number of unique elements
 
# Detailed trace
def remove_duplicates_verbose(nums: list[int]) -> int:
    """Same algorithm with step-by-step trace."""
    if len(nums) == 0:
        return 0
    
    print(f"Initial array: {nums}")
    slow = 1
    
    for fast in range(1, len(nums)):
        print(f"\nfast={fast}, slow={slow}")
        print(f"  Comparing nums[{fast}]={nums[fast]} with nums[{fast-1}]={nums[fast-1]}")
        
        if nums[fast] != nums[fast - 1]:
            print(f"  Different! Writing nums[{slow}] = {nums[fast]}")
            nums[slow] = nums[fast]
            slow += 1
            print(f"  Array now: {nums}, slow advances to {slow}")
        else:
            print(f"  Same, skipping")
    
    print(f"\nFinal: {slow} unique elements in {nums[:slow]}")
    return slow
 
# Example
nums = [1, 1, 2, 2, 2, 3]
length = remove_duplicates_verbose(nums)
print(f"\nResult: length={length}, array={nums[:length]}")

Step-by-Step Execution: [1, 1, 2, 2, 2, 3]
fast	slow	nums[fast]	nums[fast-1]	Different?	Action	Result Array
1	1	1	1	No	Skip	[1, 1, 2, 2, 2, 3]
2	1	2	1	Yes	Write & advance	[1, 2, 2, 2, 2, 3]
3	2	2	2	No	Skip	[1, 2, 2, 2, 2, 3]
4	2	2	2	No	Skip	[1, 2, 2, 2, 2, 3]
5	2	3	2	Yes	Write & advance	[1, 2, 3, 2, 2, 3]

Final result: slow = 3, meaning the first 3 elements [1, 2, 3] are the unique values.

Notice that elements after index 3 are "garbage"—they contain old values that we don't care about. The contract is that elements [0, slow) are valid; the rest is undefined.

Variant: Remove All Instances of a Value

Example:

Input:  nums = [3, 2, 2, 3], val = 3
Output: 2  (array becomes [2, 2, ...])

This is similar to removing duplicates, but instead of comparing adjacent elements, we compare each element against a target value.

remove_element.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
def remove_element(nums: list[int], val: int) -> int:
    """
    Remove all instances of val from array in-place.
    
    Time: O(n) - single pass
    Space: O(1) - two pointers
    
    Args:
        nums: Array to modify
        val: Value to remove
    
    Returns:
        New length after removal
    """
    slow = 0  # Position for next element to keep
    
    for fast in range(len(nums)):
        if nums[fast] != val:
            nums[slow] = nums[fast]
            slow += 1
    
    return slow
 
# Example trace
nums = [3, 2, 2, 3]
val = 3
print(f"Before: {nums}")
length = remove_element(nums, val)
print(f"After:  {nums[:length]} (length={length})")
# Output: [2, 2] (length=2)
 
 
def remove_element_optimized(nums: list[int], val: int) -> int:
    """
    Optimized version: Minimize moves when elements to remove are rare.
    
    Idea: Swap unwanted elements with the last element, shrink array.
    This avoids unnecessary writes when there are many keeper elements.
    
    Time: O(n) - each element examined once
    Space: O(1)
    
    Caveat: Does NOT preserve order of remaining elements.
    """
    left = 0
    right = len(nums)
    
    while left < right:
        if nums[left] == val:
            # Swap with last element and shrink
            nums[left] = nums[right - 1]
            right -= 1
            # Don't advance left; need to check swapped element
        else:
            left += 1
    
    return left
 
# This version is faster when vals are rare:
# Original: [1, 2, 3, 4, 5] val=5 -> writes every element
# Optimized: [1, 2, 3, 4, 5] val=5 -> just shrinks, minimal writes

Choosing Between Variants

Variant: Move Zeroes to End

Problem Statement: Given an array, move all zeroes to the end while maintaining the relative order of non-zero elements. Do this in-place.

Example:

Input:  [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]

This is a variant of "remove element" where instead of ignoring the removed elements, we need to place them at the end.

move_zeroes.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
def move_zeroes(nums: list[int]) -> None:
    """
    Move all zeroes to end while preserving non-zero order.
    
    Time: O(n) - single pass + one fill pass
    Space: O(1) - in-place
    
    Strategy: Two-pass
    1. Move all non-zeros to the front (using slow/fast pointers)
    2. Fill remaining positions with zeros
    """
    # Pass 1: Move non-zeros to front
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow] = nums[fast]
            slow += 1
    
    # Pass 2: Fill rest with zeros
    for i in range(slow, len(nums)):
        nums[i] = 0
 
 
def move_zeroes_one_pass(nums: list[int]) -> None:
    """
    Single-pass version using swaps.
    
    Time: O(n) - truly single pass
    Space: O(1) - in-place
    
    Strategy: Swap non-zeros to front as we find them.
    """
    slow = 0  # Points to the first zero (or end of non-zeros)
    
    for fast in range(len(nums)):
        if nums[fast] != 0:
            # Swap only if positions differ (avoid self-swap)
            if slow != fast:
                nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1
 
 
def move_zeroes_verbose(nums: list[int]) -> None:
    """Same as one-pass with detailed trace."""
    print(f"Initial: {nums}")
    slow = 0
    
    for fast in range(len(nums)):
        print(f"  fast={fast}, slow={slow}, nums[fast]={nums[fast]}")
        
        if nums[fast] != 0:
            if slow != fast:
                print(f"    Swapping positions {slow} and {fast}")
                nums[slow], nums[fast] = nums[fast], nums[slow]
                print(f"    Array: {nums}")
            else:
                print(f"    Same position, no swap needed")
            slow += 1
    
    print(f"Final: {nums}")
 
# Test
nums = [0, 1, 0, 3, 12]
move_zeroes_verbose(nums)

Trace: [0, 1, 0, 3, 12] with One-Pass Swap
fast	slow	nums[fast]	Action	Array State
0	0	0	Zero, skip	[0, 1, 0, 3, 12]
1	0	1	Non-zero, swap(0,1)	[1, 0, 0, 3, 12]
2	1	0	Zero, skip	[1, 0, 0, 3, 12]
3	1	3	Non-zero, swap(1,3)	[1, 3, 0, 0, 12]
4	2	12	Non-zero, swap(2,4)	[1, 3, 12, 0, 0]

The Fast-Slow for Cycle Detection (Floyd's Algorithm)

The Intuition:

Imagine two people running on a circular track at different speeds. No matter their starting positions, the faster runner will eventually "lap" the slower runner—they'll meet again.

Similarly, in a data structure with a cycle:

A slow pointer moves one step at a time
A fast pointer moves two steps at a time
If there's a cycle, the fast pointer will eventually catch up to the slow pointer
If there's no cycle, the fast pointer reaches the end first

Why These Specific Speeds?

cycle_detection.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
class ListNode:
    """Simple linked list node."""
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
 
def has_cycle(head: ListNode) -> bool:
    """
    Detect if a linked list has a cycle using Floyd's algorithm.
    
    Time: O(n) - at most n + (cycle length) iterations
    Space: O(1) - only two pointers
    
    Args:
        head: Start of the linked list
    
    Returns:
        True if cycle exists, False otherwise
    """
    if not head or not head.next:
        return False
    
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next          # Move 1 step
        fast = fast.next.next     # Move 2 steps
        
        if slow == fast:
            return True  # Pointers met -> cycle exists
    
    return False  # fast reached end -> no cycle
 
 
def find_cycle_start(head: ListNode) -> ListNode:
    """
    Find the node where the cycle begins.
    
    Mathematical insight:
    - Let x = distance from head to cycle start
    - Let y = distance from cycle start to meeting point
    - Let c = cycle length
    
    When they meet:
    - Slow traveled: x + y
    - Fast traveled: x + y + n*c (some number of full cycles)
    - Since fast = 2 * slow: x + y + n*c = 2(x + y)
    - Simplifying: x = n*c - y
    
    This means: distance from head to cycle start (x) equals
    distance from meeting point to cycle start (c - y + some cycles).
    
    So if we reset one pointer to head and move both at speed 1,
    they meet at the cycle start!
    """
    if not head or not head.next:
        return None
    
    # Phase 1: Detect cycle and find meeting point
    slow = fast = head
    has_cycle = False
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            has_cycle = True
            break
    
    if not has_cycle:
        return None
    
    # Phase 2: Find cycle start
    # Reset slow to head, keep fast at meeting point
    # Both move at speed 1 now
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    return slow  # Both point to cycle start
 
 
# Array version: find duplicate number
def find_duplicate(nums: list[int]) -> int:
    """
    Find the duplicate in [1, n] with n+1 elements (one duplicate).
    
    Key insight: Treat array as a linked list where nums[i] points to index nums[i].
    A duplicate means two indices point to the same location -> cycle!
    
    Time: O(n)
    Space: O(1)
    """
    # Phase 1: Find meeting point in the "cycle"
    slow = fast = 0
    
    while True:
        slow = nums[slow]           # One step
        fast = nums[nums[fast]]     # Two steps
        if slow == fast:
            break
    
    # Phase 2: Find cycle entry (the duplicate)
    slow = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    
    return slow
 
# Example: [1, 3, 4, 2, 2] -> 2 is the duplicate
print(find_duplicate([1, 3, 4, 2, 2]))  # Output: 2

The Duplicate Number Problem

Finding the Middle Element

Another elegant application of fast-slow pointers: finding the middle of a sequence without knowing its length.

Problem: Given a linked list (length unknown), find its middle node.

Naive approach: Traverse once to count, traverse again to middle → O(2n) = O(n), but two passes.

Two-pointer approach: Fast moves 2 steps, slow moves 1 step. When fast reaches end, slow is at middle. → O(n), single pass.

find_middle.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
def find_middle(head: ListNode) -> ListNode:
    """
    Find the middle node of a linked list.
    
    For even length, returns the second middle node.
    Example: 1->2->3->4 returns node with value 3
    
    Time: O(n) - single pass
    Space: O(1) - two pointers
    """
    if not head:
        return None
    
    slow = fast = head
    
    # Fast moves twice as fast as slow
    # When fast reaches end, slow is at middle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    return slow
 
 
def find_middle_first(head: ListNode) -> ListNode:
    """
    For even length, returns the FIRST middle node.
    Example: 1->2->3->4 returns node with value 2
    
    Difference: Check fast.next.next instead of fast.next
    """
    if not head:
        return None
    
    slow = fast = head
    
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    
    return slow
 
 
# Why this works:
# If list has n nodes, fast takes n/2 steps before reaching end.
# Slow, moving half as fast, takes n/2 steps -> middle!
 
# Odd length:  1 -> 2 -> 3 -> 4 -> 5 -> null
#              s         f
#                   s              f
#                        s              [f off end]
# slow at node 3 ✓
 
# Even length: 1 -> 2 -> 3 -> 4 -> null  
#              s         f
#                   s              f [about to be off]
#                        s    [f would be at null.next = crash if not for condition]
# slow at node 3 ✓ (second middle)

For Arrays, It's Easier

With arrays, you can just calculate length / 2 since you know the length. The fast-slow technique shines for linked lists where length is unknown without traversal.

Partitioning Arrays

Same-direction two-pointers are essential for partitioning problems, where you need to rearrange elements based on some condition.

Problem: Given an array and a pivot value, rearrange it so all elements less than pivot come before elements greater than or equal to pivot.

This is the core of QuickSort's partition step and appears in many variations.

partition.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
def partition(nums: list[int], pivot: int) -> int:
    """
    Partition array around pivot value.
    
    After execution:
    - nums[0:result] contain elements < pivot
    - nums[result:] contain elements >= pivot
    
    Time: O(n) - single pass
    Space: O(1) - in-place
    """
    slow = 0  # Position for next element < pivot
    
    for fast in range(len(nums)):
        if nums[fast] < pivot:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1
    
    return slow  # Partition point
 
 
def partition_three_way(nums: list[int], pivot: int) -> tuple[int, int]:
    """
    Dutch National Flag partition: three regions.
    
    Result:
    - nums[0:low] contain elements < pivot
    - nums[low:high] contain elements == pivot
    - nums[high:] contain elements > pivot
    
    Uses THREE pointers for in-place O(n) solution.
    
    This is crucial for:
    - Handling duplicates in QuickSort
    - Dutch National Flag problem
    - Sort Colors (LeetCode 75)
    """
    low = 0           # Next position for < pivot
    mid = 0           # Current element to examine
    high = len(nums)  # Next position for > pivot (from end)
    
    while mid < high:
        if nums[mid] < pivot:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] > pivot:
            high -= 1
            nums[mid], nums[high] = nums[high], nums[mid]
            # Don't advance mid; need to examine swapped element
        else:  # nums[mid] == pivot
            mid += 1
    
    return low, high
 
 
# Example: Sort Colors (values are 0, 1, 2)
def sort_colors(nums: list[int]) -> None:
    """
    Sort array containing only 0, 1, 2 in-place.
    One-pass O(n) solution using three-way partition.
    """
    partition_three_way(nums, 1)  # Pivot on 1
 
# Test
colors = [2, 0, 2, 1, 1, 0]
sort_colors(colors)
print(colors)  # [0, 0, 1, 1, 2, 2]

Three-Way Partition for QuickSort

Summary: Same-Direction Pointers

You've now mastered the same-direction two-pointer pattern. Let's consolidate the key insights:

Key Takeaways

•Reader-Writer Paradigm — Fast pointer reads, slow pointer writes. This enables in-place transformations.
•Removing Elements — Whether removing duplicates or specific values, the pattern is: examine with fast, write with slow if it's a keeper.
•Cycle Detection — Floyd's algorithm uses fast(2x) and slow(1x) speeds to detect cycles in O(1) space.
•Finding Middle — When fast reaches end, slow is at middle. Works because fast moves 2x speed.
•Partitioning — Separate elements by condition using swap and advance pattern.
•O(n) Time, O(1) Space — The consistent theme: single pass, constant extra memory.

Same-Direction Two-Pointer Problem Types
Problem Type	Slow Pointer Role	Fast Pointer Role	Key Insight
Remove duplicates	Write position	Read position	Copy unique elements left
Remove by value	Write position	Read position	Skip matching values
Move zeroes	Non-zero destination	Current scanner	Swap non-zeros forward
Cycle detection	1x speed	2x speed	Fast catches slow in cycle
Find middle	1x speed	2x speed	When fast ends, slow is middle
Partition	Boundary marker	Current scanner	Swap elements across boundary

What's next:

Page Complete

You now have a deep understanding of same-direction two-pointer techniques. These patterns form the foundation for in-place array manipulation, cycle detection, and efficient partitioning algorithms.

2 / 5