👆 Two Pointers Fundamentals

🎯 What is the Two Pointers Technique?

The two pointers technique is a powerful algorithmic pattern that uses two pointers to traverse data structures (usually arrays or strings) in a single pass, often achieving O(n) time complexity.

Approach: Use two pointers to track positions in the data
Patterns: Opposite direction, same direction, fast & slow
Benefits: Reduces time complexity from O(n²) to O(n)
Space: Usually O(1) extra space

📌 O(n) Time📌 O(1) Space📌 Single Pass

The Core Insight

Key Insight: Instead of using nested loops to solve problems, two pointers allow us to process data linearly by maintaining two positions and moving them strategically based on the problem constraints.

Three Main Patterns:

Opposite Direction Pointers move towards each other
Same Direction Pointers move together (sliding window)
Fast & Slow Different speeds for cycle detection

# Two Pointers - The Three Patterns

# 1. Opposite Direction (Two Sum in Sorted Array)
def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        curr_sum = arr[left] + arr[right]
        if curr_sum == target:
            return [left, right]
        elif curr_sum < target:
            left += 1
        else:
            right -= 1
    return []

# 2. Same Direction (Sliding Window)
def max_sum_subarray(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    return max_sum

# 3. Fast & Slow (Cycle Detection)
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

🔀 Opposite Direction Pointers

🎯 Meeting in the Middle

One pointer starts at the beginning, the other at the end. They move towards each other until they meet or cross.

Best for: Sorted arrays, palindrome checking, two sum
Movement: Based on comparison with target
Time: O(n) typically
Use Case: Finding pairs, reversing arrays

# Opposite Direction Pattern Examples

# 1. Two Sum in Sorted Array
def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        curr_sum = arr[left] + arr[right]
        if curr_sum == target:
            return [left, right]
        elif curr_sum < target:
            left += 1
        else:
            right -= 1
    return []

# 2. Check if array is palindrome
def is_palindrome(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        if arr[left] != arr[right]:
            return False
        left += 1
        right -= 1
    return True

# 3. Reverse array in-place
def reverse_array(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    return arr

# 4. Find pair with difference target
def pair_with_diff(arr, target):
    left, right = 0, 1
    while right < len(arr):
        diff = arr[right] - arr[left]
        if diff == target:
            return [left, right]
        elif diff < target:
            right += 1
        else:
            left += 1
            if left == right:
                right += 1
    return []

➡️ Same Direction Pointers (Sliding Window)

🎯 Moving Together in the Same Direction

Both pointers move in the same direction, maintaining a window between them. This is also known as the sliding window technique.

Best for: Subarray problems, substring problems
Window: Defined by the two pointers
Time: O(n) typically
Use Case: Maximum/minimum subarray, longest substring

# Same Direction Pattern (Sliding Window)

# 1. Maximum sum subarray of size k
def max_sum_subarray(arr, k):
    if len(arr) < k:
        return -1
    
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    
    return max_sum

# 2. Longest substring without repeating characters
def longest_unique_substring(s):
    char_index = {}
    left = 0
    max_len = 0
    
    for right, char in enumerate(s):
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1
        char_index[char] = right
        max_len = max(max_len, right - left + 1)
    
    return max_len

# 3. Minimum window substring
def min_window(s, t):
    from collections import Counter
    need = Counter(t)
    have = {}
    left = 0
    min_len = float('inf')
    result = ""
    required = len(need)
    formed = 0
    
    for right, char in enumerate(s):
        have[char] = have.get(char, 0) + 1
        if char in need and have[char] == need[char]:
            formed += 1
        
        while formed == required and left <= right:
            if right - left + 1 < min_len:
                min_len = right - left + 1
                result = s[left:right + 1]
            
            # Shrink window
            left_char = s[left]
            have[left_char] -= 1
            if left_char in need and have[left_char] < need[left_char]:
                formed -= 1
            left += 1
    
    return result

🏃 Fast & Slow Pointers

🎯 Different Speeds for Cycle Detection

One pointer moves faster than the other. This is used for cycle detection in linked lists and finding the middle element.

Best for: Linked lists, cycle detection
Speeds: Slow moves 1 step, fast moves 2 steps
Time: O(n)
Use Case: Cycle detection, finding middle

# Fast & Slow Pointers Examples

# 1. Linked List Cycle Detection (Floyd's Algorithm)
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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

# 2. Find Middle of Linked List
def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

# 3. Find Cycle Start (Floyd's Algorithm)
def detect_cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # Find cycle start
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

# 4. Happy Number Detection
def is_happy_number(n):
    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

📝 Two Sum & Variants

🎯 Classic Two Pointers Problem

Two Sum is the classic two pointers problem. Given a sorted array, find two numbers that sum to a target.

Sorted Array: Use opposite direction pointers
Unsorted Array: Use hash map (O(n) time, O(n) space)
Variants: Two Sum II, Two Sum III, Two Sum IV

# Two Sum Variants

# 1. Two Sum (Sorted)
def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        curr = nums[left] + nums[right]
        if curr == target:
            return [left + 1, right + 1]
        elif curr < target:
            left += 1
        else:
            right -= 1
    return []

# 2. Two Sum (Unsorted) - Hash Map
def two_sum_unsorted(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

# 3. Two Sum (Multiple Solutions)
def two_sum_all(nums, target):
    nums.sort()
    result = []
    left, right = 0, len(nums) - 1
    while left < right:
        curr = nums[left] + nums[right]
        if curr == target:
            result.append([nums[left], nums[right]])
            left += 1
            right -= 1
            while left < right and nums[left] == nums[left - 1]:
                left += 1
            while left < right and nums[right] == nums[right + 1]:
                right -= 1
        elif curr < target:
            left += 1
        else:
            right -= 1
    return result

# 4. Two Sum (BST) - Two Sum IV
def find_target(root, k):
    # Use DFS + set to find if two nodes sum to k
    seen = set()
    def dfs(node):
        if not node:
            return False
        if k - node.val in seen:
            return True
        seen.add(node.val)
        return dfs(node.left) or dfs(node.right)
    return dfs(root)

🔢 Three Sum

🎯 Finding Triplets

Given an array, find all unique triplets that sum to zero (or a target). This extends the two sum approach.

Approach: Fix one element, use two pointers for the rest
Time: O(n²)
Key: Skip duplicates for uniqueness

# Three Sum (Find all triplets sum to 0)
def three_sum(nums):
    nums.sort()
    result = []
    n = len(nums)
    
    for i in range(n - 2):
        # Skip duplicates for first element
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        left, right = i + 1, n - 1
        target = -nums[i]
        
        while left < right:
            curr_sum = nums[left] + nums[right]
            if curr_sum == target:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                # Skip duplicates
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
            elif curr_sum < target:
                left += 1
            else:
                right -= 1
    
    return result

# Three Sum Closest
def three_sum_closest(nums, target):
    nums.sort()
    closest = float('inf')
    n = len(nums)
    
    for i in range(n - 2):
        left, right = i + 1, n - 1
        while left < right:
            curr_sum = nums[i] + nums[left] + nums[right]
            if abs(curr_sum - target) < abs(closest - target):
                closest = curr_sum
            if curr_sum < target:
                left += 1
            elif curr_sum > target:
                right -= 1
            else:
                return target
    
    return closest

# Four Sum
def four_sum(nums, target):
    nums.sort()
    result = []
    n = len(nums)
    
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue
            left, right = j + 1, n - 1
            while left < right:
                curr_sum = nums[i] + nums[j] + nums[left] + nums[right]
                if curr_sum == target:
                    result.append([nums[i], nums[j], nums[left], nums[right]])
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1
                elif curr_sum < target:
                    left += 1
                else:
                    right -= 1
    
    return result

📊 Container With Most Water

🎯 Maximizing Area

Given an array of heights, find the maximum area of water that can be contained between two lines. This is a classic two pointers problem.

Approach: Two pointers from both ends
Area: width × min(height[left], height[right])
Movement: Move the pointer with smaller height
Time: O(n)

# Container With Most Water
def max_area(heights):
    left, right = 0, len(heights) - 1
    max_area = 0
    
    while left < right:
        # Calculate area
        width = right - left
        height = min(heights[left], heights[right])
        area = width * height
        max_area = max(max_area, area)
        
        # Move the pointer with smaller height
        if heights[left] < heights[right]:
            left += 1
        else:
            right -= 1
    
    return max_area

# Example:
# heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
# Max area = 49 (between indices 1 and 8)

# Step-by-step:
# left=0, right=8: area=1*8=8, move left (1<7)
# left=1, right=8: area=7*7=49, move right (8>7)
# left=1, right=7: area=6*3=18, move right (8>3)
# left=1, right=6: area=5*8=40, move right (8>8? move right)
# left=1, right=5: area=4*4=16, move right (8>4)
# left=1, right=4: area=3*5=15, move right (8>5)
# left=1, right=3: area=2*2=4, move right (8>2)
# left=1, right=2: area=1*6=6, move right
# End → max_area = 49

🌊 Trapping Rain Water

🎯 Calculating Trapped Water

Given an array of heights, calculate how much water can be trapped between the bars after rain.

Approach: Two pointers with left/right max
Water: min(left_max, right_max) - height[i]
Time: O(n)
Space: O(1)

# Trapping Rain Water (Two Pointers)
def trap_rain_water(heights):
    if not heights:
        return 0
    
    left, right = 0, len(heights) - 1
    left_max = heights[left]
    right_max = heights[right]
    water = 0
    
    while left < right:
        if left_max < right_max:
            left += 1
            left_max = max(left_max, heights[left])
            water += left_max - heights[left]
        else:
            right -= 1
            right_max = max(right_max, heights[right])
            water += right_max - heights[right]
    
    return water

# Example:
# heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
# Total water = 6

# Alternative: Using precomputed left/right max arrays
def trap_rain_water_arrays(heights):
    n = len(heights)
    if n <= 2:
        return 0
    
    left_max = [0] * n
    right_max = [0] * n
    
    left_max[0] = heights[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i-1], heights[i])
    
    right_max[n-1] = heights[n-1]
    for i in range(n-2, -1, -1):
        right_max[i] = max(right_max[i+1], heights[i])
    
    water = 0
    for i in range(n):
        water += min(left_max[i], right_max[i]) - heights[i]
    
    return water

# Visualization:
# heights: [0,1,0,2,1,0,1,3,2,1,2,1]
# water:   [0,0,1,0,1,2,1,0,0,1,0,0] = 6

🔄 Palindrome Checking

🎯 Using Two Pointers for Palindromes

Two pointers are ideal for checking if a string or array is a palindrome, by comparing characters from both ends.

Approach: Compare from both ends
Time: O(n)
Space: O(1)
Variants: Valid palindrome, palindrome substrings

# Palindrome Checking with Two Pointers

# 1. Valid Palindrome (alphanumeric only)
def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        # Skip non-alphanumeric characters
        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

# 2. Find all palindromic substrings
def count_palindromic_substrings(s):
    def expand_around_center(left, right):
        count = 0
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
        return count
    
    total = 0
    for i in range(len(s)):
        total += expand_around_center(i, i)  # Odd length
        total += expand_around_center(i, i + 1)  # Even length
    
    return total

# 3. Longest Palindromic Substring
def longest_palindrome(s):
    if not s:
        return ""
    
    start = 0
    max_len = 1
    
    def expand_around_center(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - left - 1
    
    for i in range(len(s)):
        # Odd length
        l1, len1 = expand_around_center(i, i)
        # Even length
        l2, len2 = expand_around_center(i, i + 1)
        
        if len1 > max_len:
            max_len = len1
            start = l1
        if len2 > max_len:
            max_len = len2
            start = l2
    
    return s[start:start + max_len]

# 4. Valid Palindrome II (allow one deletion)
def valid_palindrome_ii(s):
    def is_palindrome_range(left, right):
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True
    
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return is_palindrome_range(left + 1, right) or is_palindrome_range(left, right - 1)
        left += 1
        right -= 1
    return True

🔗 Merging Two Arrays

🎯 Merging Sorted Arrays

Two pointers are perfect for merging two sorted arrays into one sorted array.

Approach: Compare elements from both arrays
Time: O(m + n)
Space: O(m + n) or O(1) for in-place

# Merge Two Sorted Arrays
def merge_sorted(arr1, arr2):
    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
    
    # Add remaining elements
    while i < len(arr1):
        result.append(arr1[i])
        i += 1
    while j < len(arr2):
        result.append(arr2[j])
        j += 1
    
    return result

# Merge in-place (arr1 has extra space)
def merge_in_place(arr1, m, arr2, n):
    # arr1 has length m + n, first m elements are valid
    i = m - 1
    j = n - 1
    k = m + n - 1
    
    while i >= 0 and j >= 0:
        if arr1[i] > arr2[j]:
            arr1[k] = arr1[i]
            i -= 1
        else:
            arr1[k] = arr2[j]
            j -= 1
        k -= 1
    
    while j >= 0:
        arr1[k] = arr2[j]
        j -= 1
        k -= 1
    
    return arr1

# Merge Two Sorted Linked Lists
def merge_lists(l1, l2):
    dummy = ListNode(0)
    current = dummy
    
    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    
    current.next = l1 or l2
    
    return dummy.next

🗑️ Remove Duplicates

🎯 Removing Duplicates in Sorted Arrays

Use two pointers to remove duplicates from a sorted array in-place.

Approach: Slow pointer for unique elements, fast for scanning
Time: O(n)
Space: O(1)

# Remove Duplicates from Sorted Array
def remove_duplicates(nums):
    if not nums:
        return 0
    
    write = 1
    for read in range(1, len(nums)):
        if nums[read] != nums[read - 1]:
            nums[write] = nums[read]
            write += 1
    
    return write  # Number of unique elements

# Remove Duplicates (allow at most k duplicates)
def remove_duplicates_k(nums, k):
    if len(nums) <= k:
        return len(nums)
    
    write = k
    for read in range(k, len(nums)):
        if nums[read] != nums[write - k]:
            nums[write] = nums[read]
            write += 1
    
    return write

# Remove Element (remove all occurrences of val)
def remove_element(nums, val):
    write = 0
    for read in range(len(nums)):
        if nums[read] != val:
            nums[write] = nums[read]
            write += 1
    
    return write

# Example:
# nums = [1, 1, 2, 2, 3, 3, 4]
# remove_duplicates(nums) → [1, 2, 3, 4, _, _, _], returns 4

⏱️ Time & Space Complexities

Pattern	Time Complexity	Space Complexity	Examples
Opposite Direction	O(n)	O(1)	Two Sum, Palindrome
Same Direction (Sliding)	O(n)	O(1) or O(k)	Max Subarray, Min Window
Fast & Slow	O(n)	O(1)	Cycle Detection, Middle
Two Sum (Unsorted)	O(n)	O(n)	Hash Map Approach
Three Sum	O(n²)	O(1) or O(n)	Triplets
Container Water	O(n)	O(1)	Max Area
Trapping Rain	O(n)	O(1)	Two Pointers
Merge Arrays	O(m + n)	O(m + n) or O(1)	Merge Sorted

🌍 Real-World Applications

Text Processing: Finding palindromes, anagrams
Database Queries: Joining sorted datasets
Data Compression: Run-length encoding
Network Protocols: Packet ordering
Image Processing: Boundary detection
Cryptography: String matching
Genomics: DNA sequence alignment
Web Search: Keyword matching

📝 Interview Patterns & Problems

🎯 Key Interview Questions

Two Sum: "Find two numbers that sum to target"
Three Sum: "Find all triplets that sum to zero"
Container: "Find max water container"
Trapping Rain: "Calculate trapped rain water"
Palindrome: "Check if string is palindrome"
Remove Duplicates: "Remove duplicates in-place"
Merge Arrays: "Merge two sorted arrays"
Cycle Detection: "Detect cycle in linked list"
Longest Substring: "Longest substring without repeating characters"

# Interview Problem: Move Zeroes
def move_zeroes(nums):
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1
    return nums

# Interview Problem: Sort Colors (Dutch National Flag)
def sort_colors(nums):
    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], nums[high] = nums[high], nums[mid]
            high -= 1
    return nums

# Interview Problem: Subarray Product Less Than K
def num_subarray_product_less_than_k(nums, k):
    if k <= 1:
        return 0
    
    left = 0
    product = 1
    count = 0
    
    for right, num in enumerate(nums):
        product *= num
        while product >= k and left <= right:
            product //= nums[left]
            left += 1
        count += right - left + 1
    
    return count