Two Pointers

def opposite_direction(arr, target):
    """Generic opposite-direction two pointer on sorted array."""
    left, right = 0, len(arr) - 1

    while left < right:
        current = arr[left] + arr[right]  # or whatever comparison

        if current == target:
            return [left, right]          # found answer
        elif current < target:
            left += 1                     # need larger sum -> move left up
        else:
            right -= 1                    # need smaller sum -> move right down

    return []  # no solution

def same_direction(arr):
    """Generic same-direction two pointer for in-place filtering."""
    write = 0                              # write pointer (slow)

    for read in range(len(arr)):           # read pointer (fast)
        if should_keep(arr[read]):         # your condition here
            arr[write] = arr[read]
            write += 1

    return write  # new length of valid portion

def two_sum_sorted(numbers, target):
    """Find pair in sorted array that sums to target. O(n) time, O(1) space."""
    left, right = 0, len(numbers) - 1

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

        if total == target:
            return [left + 1, right + 1]  # 1-indexed
        elif total < target:
            left += 1       # sum too small, increase left
        else:
            right -= 1      # sum too large, decrease right

def three_sum(nums):
    """Find all unique triplets that sum to zero."""
    nums.sort()                            # MUST sort first
    result = []

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

        # Two pointer search for remaining pair
        left, right = i + 1, len(nums) - 1
        target = -nums[i]                  # a + b + c = 0 means b + c = -a

        while left < right:
            total = nums[left] + nums[right]

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

    return result

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

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

        # KEY INSIGHT: move the shorter line inward
        # Moving the taller line can only decrease or maintain area
        # (width shrinks, and height is bounded by the shorter line)
        # Moving the shorter line MIGHT find a taller one -> bigger area
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return best

def trap(height):
    """Calculate trapped rainwater. O(n) time, O(1) space."""
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0

    #  left_max                    right_max
    #     |                            |
    #     v                            v
    #   |                          |
    #   |  water   |       |  water|
    #   |__|_______|_______|_______|
    #   L ->                    <- R

    while left < right:
        if height[left] < height[right]:
            # Water at left is bounded by left_max
            # (right side is guaranteed >= height[right] > height[left])
            left_max = max(left_max, height[left])
            water += left_max - height[left]   # water above this bar
            left += 1
        else:
            # Water at right is bounded by right_max
            right_max = max(right_max, height[right])
            water += right_max - height[right]
            right -= 1

    return water

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

    write = 1  # first element is always kept

    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:   # new unique value found
            nums[write] = nums[read]         # write it to the next slot
            write += 1

    return write

    # Example walkthrough:
    # [1, 1, 2, 2, 3]
    #  W  R                 nums[1]=1 == nums[0]=1, skip
    #  W     R              nums[2]=2 != nums[0]=1, write -> [1, 2, ...]
    #     W     R           nums[3]=2 == nums[1]=2, skip
    #     W        R        nums[4]=3 != nums[1]=2, write -> [1, 2, 3, ...]
    # Result: [1, 2, 3, _, _], return 3

def has_cycle(head):
    """Detect cycle in linked list using Floyd's algorithm."""
    slow = fast = head

    while fast and fast.next:
        slow = slow.next          # 1 step
        fast = fast.next.next     # 2 steps

        if slow is fast:          # they meet -> cycle exists
            return True

    return False  # fast reached end -> no cycle

    #  S
    #  F
    #  1 -> 2 -> 3 -> 4 -> 5
    #                  ^    |
    #                  |    v
    #                  7 <- 6
    #
    #  Step 1: S=2, F=3
    #  Step 2: S=3, F=5
    #  Step 3: S=4, F=7
    #  Step 4: S=5, F=4
    #  Step 5: S=6, F=6  --> MEET! Cycle detected.