Two Pointers Patterns: Complete Reference¶

def two_pointers_template(sequence):
    """
    Generic two pointers template.

    Key components:
    1. Initialization: Set up pointer positions based on strategy
    2. Invariant: Condition that guides pointer movement
    3. Movement Rules: Deterministic pointer advancement
    4. Termination: Pointers meet or cross
    5. Update: Record answer when condition is satisfied
    """
    left, right = initialize_pointers(sequence)
    answer = initial_answer()

    while not termination_condition(left, right):
        # EVALUATE: Check current state against problem goal
        current_value = evaluate(sequence, left, right)

        # UPDATE ANSWER: Record if current state is optimal
        answer = update_answer(answer, current_value)

        # MOVE: Advance pointers based on invariant
        if should_move_left(current_value, target):
            left += 1
        else:
            right -= 1

    return answer

def opposite_pointers_template(arr, target):
    """
    Opposite pointers for sorted array search.

    Time Complexity: O(n) - each pointer moves at most n times
    Space Complexity: O(1) - constant extra space
    """
    left, right = 0, len(arr) - 1
    answer = None

    while left < right:
        current = compute_value(arr, left, right)

        if current == target:
            # Found exact match
            return process_match(arr, left, right)
        elif current < target:
            # Need larger value: move left pointer right
            left += 1
        else:
            # Need smaller value: move right pointer left
            right -= 1

    return answer

def same_direction_template(arr, condition):
    """
    Same-direction (reader/writer) pattern for in-place modification.

    Time Complexity: O(n) - single pass through array
    Space Complexity: O(1) - in-place modification

    Invariant: arr[0:write_index] contains all valid elements seen so far.
    """
    write_index = 0

    for read_index in range(len(arr)):
        if condition(arr, read_index, write_index):
            arr[write_index] = arr[read_index]
            write_index += 1

    return write_index  # New logical length

def fast_slow_cycle_detection(head):
    """
    Floyd's cycle detection algorithm.

    Phase 1: Detect if cycle exists
    Phase 2: Find cycle start (if needed)

    Time Complexity: O(n) - at most 2n steps
    Space Complexity: O(1) - only two pointers
    """
    # Phase 1: Detect cycle
    slow = fast = head

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

        if slow == fast:
            # Cycle detected
            break
    else:
        # No cycle (fast reached end)
        return None

    # Phase 2: Find cycle start
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next

    return slow  # Cycle start node

def find_middle(head):
    """
    Find middle element using fast-slow pointers.

    When fast reaches end, slow is at middle.
    For even length, returns second middle element.
    """
    slow = fast = head

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

    return slow

def dutch_national_flag(arr, pivot=1):
    """
    Dutch National Flag algorithm (three-way partition).

    Partitions array into three regions:
    - Elements < pivot
    - Elements == pivot
    - Elements > pivot

    Time Complexity: O(n) - single pass
    Space Complexity: O(1) - in-place swaps

    Invariant at each step:
    - arr[0:low] contains elements < pivot
    - arr[low:mid] contains elements == pivot
    - arr[high+1:] contains elements > pivot
    - arr[mid:high+1] is unclassified
    """
    low, mid, high = 0, 0, len(arr) - 1

    while mid <= high:
        if arr[mid] < pivot:
            # Move to "less than" region
            arr[low], arr[mid] = arr[mid], arr[low]
            low += 1
            mid += 1
        elif arr[mid] > pivot:
            # Move to "greater than" region
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1
            # Don't increment mid — swapped element is unclassified
        else:
            # Element equals pivot — already in correct region
            mid += 1

def partition_by_parity(arr):
    """
    Partition array so all even numbers come before odd numbers.

    Two regions: [0, write) = even, [write, n) = odd
    """
    write = 0

    for read in range(len(arr)):
        if arr[read] % 2 == 0:
            arr[write], arr[read] = arr[read], arr[write]
            write += 1

    return arr

def three_sum_template(nums, target=0):
    """
    Find all unique triplets that sum to target.

    Algorithm:
    1. Sort array
    2. For each element nums[i], find pairs (j, k) where j > i, k > j
    3. Use opposite pointers for inner search
    4. Skip duplicates at all levels

    Time Complexity: O(n²) - n iterations × n two-pointer search
    Space Complexity: O(1) extra (excluding output)
    """
    nums.sort()
    n = len(nums)
    result = []

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

        # Early termination: smallest possible sum too large
        if nums[i] + nums[i + 1] + nums[i + 2] > target:
            break

        # Skip: largest possible sum too small
        if nums[i] + nums[n - 2] + nums[n - 1] < target:
            continue

        # Two-pointer search for remaining pair
        left, right = i + 1, n - 1

        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]

            if current_sum == target:
                result.append([nums[i], nums[left], nums[right]])

                # Skip duplicates for second element
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                # Skip duplicates for third element
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1

                left += 1
                right -= 1
            elif current_sum < target:
                left += 1
            else:
                right -= 1

    return result

def merge_sorted_arrays(arr1, arr2):
    """
    Merge two sorted arrays into one sorted array.

    Time Complexity: O(m + n) - each element processed once
    Space Complexity: O(m + n) - output array
    """
    i, j = 0, 0
    result = []

    while i < len(arr1) and j < len(arr2):
        if arr1[i] <= arr2[j]:
            result.append(arr1[i])
            i += 1
        else:
            result.append(arr2[j])
            j += 1

    # Append remaining elements
    result.extend(arr1[i:])
    result.extend(arr2[j:])

    return result

def merge_in_place(nums1, m, nums2, n):
    """
    Merge nums2 into nums1 in-place.

    Key insight: Write from the END to avoid overwriting unprocessed elements.
    """
    write = m + n - 1
    i, j = m - 1, n - 1

    while j >= 0:
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[write] = nums1[i]
            i -= 1
        else:
            nums1[write] = nums2[j]
            j -= 1
        write -= 1

def opposite_pointers(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        # Process arr[left] and arr[right]
        if condition_move_left:
            left += 1
        else:
            right -= 1

def same_direction(arr):
    write = 0
    for read in range(len(arr)):
        if should_keep(arr[read]):
            arr[write] = arr[read]
            write += 1
    return write

def fast_slow(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True  # Cycle
    return False

def dutch_flag(arr):
    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:
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1
        else:
            mid += 1

def merge(arr1, arr2):
    i, j, result = 0, 0, []
    while i < len(arr1) and j < len(arr2):
        if arr1[i] <= arr2[j]:
            result.append(arr1[i])
            i += 1
        else:
            result.append(arr2[j])
            j += 1
    return result + arr1[i:] + arr2[j:]