Two Pointers (Opposite Ends)

"""
Two Pointers (Opposite Ends)

OVERVIEW

This pattern uses two pointers that start from opposite ends of a data structure
(array or string) and move toward each other.

It is mainly used when:

• Order matters from both ends
• The data is sorted or symmetric
• You are checking pairs or mirrored positions
• You want to reduce time complexity from O(N^2) to O(N)

POINTER SETUP

left -> starts at index 0
right -> starts at index n - 1

LOOP CONDITION

Continue while left < right

POINTER MOVEMENT LOGIC

• If current condition is satisfied: update answer and move pointers
• If value is too small: move left forward
• If value is too large: move right backward

TIME & SPACE

Time Complexity : O(N)
Space Complexity : O(1)
"""

"""
EXAMPLE 1: Two Sum (Sorted Array)

Problem:
Given a sorted array, determine if there exists a pair whose sum equals target.

Logic:

• If sum is smaller than target, increase left to get a bigger sum
• If sum is larger than target, decrease right to get a smaller sum """

def two_sum_sorted(nums, target):
left = 0
right = len(nums) - 1

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

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

return False

"""
EXAMPLE 2: Palindrome Check

Problem:
Check whether a string is a palindrome.

Logic:

• Characters at symmetric positions must match
• Any mismatch immediately returns false """

def is_palindrome(s):
left = 0
right = len(s) - 1

while left < right:
    if s[left] != s[right]:
        return False

    left += 1
    right -= 1

return True

"""
EXAMPLE 3: Container With Most Water

Problem:
Find two vertical lines that together with the x-axis form a container holding
the maximum amount of water.

Logic:

• Area depends on width and the smaller height
• Move the pointer with the smaller height to try increasing area """

def max_area(height):
left = 0
right = len(height) - 1
max_water = 0

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

    if height[left] < height[right]:
        left += 1
    else:
        right -= 1

return max_water

"""
EXAMPLE 4: Reverse Array In-Place

Problem:
Reverse an array without using extra space.

Logic:

• Swap elements at symmetric positions
• Move inward until pointers meet """

def reverse_array(arr):
left = 0
right = len(arr) - 1

while left < right:
    arr[left], arr[right] = arr[right], arr[left]
    left += 1
    right -= 1

return arr

"""

IDENTIFICATION CHECKLIST

Ask these questions:

• Are two elements compared together?
• Do we care about values from both ends?
• Can one side be discarded every step?
• Is the data sorted or symmetric?

If yes, this pattern fits.

SUMMARY

• Two pointers start from opposite ends
• Both move inward
• Each iteration removes impossible cases
• Clean, optimal, and easy to reason about """