Greedy Two-Pointer Pattern: When Greedy Meets Two Pointers (Template and Examples)

arr1.sort()
arr2.sort()

i = j = 0
while i < len(arr1) and j < len(arr2):
    if can_match(arr1[i], arr2[j]):
        i += 1
        j += 1
    else:
        j += 1  # Or i += 1

def match_elements(arr1, arr2):
    arr1.sort()
    arr2.sort()
    
    i = j = 0
    matches = 0
    
    while i < len(arr1) and j < len(arr2):
        if arr2[j] >= arr1[i]:  # Can match
            matches += 1
            i += 1
            j += 1
        else:
            j += 1  # Try next element in arr2
    
    return matches

def pair_elements(arr, limit):
    arr.sort()
    
    left = 0
    right = len(arr) - 1
    pairs = 0
    
    while left < right:
        if arr[left] + arr[right] <= limit:
            pairs += 1
            left += 1
            right -= 1
        else:
            right -= 1  # Try smaller element
    
    return pairs

def numRescueBoats(people, limit):
    """
    Time: O(n log n), Space: O(1)
    """
    people.sort()
    
    left = 0
    right = len(people) - 1
    boats = 0
    
    while left <= right:
        # Try to pair heaviest with lightest
        if people[left] + people[right] <= limit:
            left += 1   # Lightest person gets on
            right -= 1  # Heaviest person gets on
        else:
            right -= 1  # Heaviest goes alone
        
        boats += 1
    
    return boats

people = [3, 2, 2, 1], limit = 3

After sort: [1, 2, 2, 3]

Step 1: left=0, right=3
  people[0]=1, people[3]=3
  1 + 3 = 4 > 3? YES
  Heaviest (3) goes alone
  boats=1, right=2

Step 2: left=0, right=2
  people[0]=1, people[2]=2
  1 + 2 = 3 <= 3? YES
  Pair them
  boats=2, left=1, right=1

Step 3: left=1, right=1
  Same person, goes alone
  boats=3

Result: 3 boats

def twoCitySchedCost(costs):
    """
    Time: O(n log n), Space: O(1)
    """
    # Sort by difference: how much we save by going to A
    costs.sort(key=lambda x: x[0] - x[1])
    
    total = 0
    n = len(costs) // 2
    
    # First n go to city A (biggest savings)
    for i in range(n):
        total += costs[i][0]
    
    # Last n go to city B
    for i in range(n, 2 * n):
        total += costs[i][1]
    
    return total

from collections import deque

def advantageCount(nums1, nums2):
    """
    Time: O(n log n), Space: O(n)
    """
    nums1.sort()
    
    # Create (value, index) pairs and sort by value
    sorted_nums2 = sorted((val, i) for i, val in enumerate(nums2))
    
    result = [0] * len(nums1)
    left = 0
    right = len(nums1) - 1
    
    # Process nums2 from largest to smallest
    for val, idx in reversed(sorted_nums2):
        if nums1[right] > val:
            # Can beat it, use largest available
            result[idx] = nums1[right]
            right -= 1
        else:
            # Can't beat it, use smallest (waste it)
            result[idx] = nums1[left]
            left += 1
    
    return result

def greedy_two_pointer(arr1, arr2, condition):
    """
    Universal template for greedy + two pointer.
    """
    # Step 1: Sort (greedy ordering)
    arr1.sort()
    arr2.sort()  # If needed
    
    # Step 2: Initialize pointers
    left = 0
    right = len(arr1) - 1  # Or use two arrays
    result = 0
    
    # Step 3: Two-pointer logic
    while left <= right:  # Or other condition
        if condition(arr1[left], arr1[right]):
            # Make greedy choice
            result += 1
            left += 1
            right -= 1
        else:
            # Adjust pointers
            right -= 1  # Or left += 1
    
    return result

arr.sort(reverse=True)  # Descending when need ascending

arr.sort()  # Ascending for greedy matching

left += 1
right -= 1  # Always move both

if condition:
    left += 1
    right -= 1
else:
    right -= 1  # Only move one

# Forgot to sort!
left, right = 0, len(arr) - 1

arr.sort()  # Must sort first
left, right = 0, len(arr) - 1

Need to match elements?
├─ From two arrays?
│  └─ Use same-direction (i, j)
│     Example: Assign Cookies
│
└─ From same array?
   └─ Use opposite-direction (left, right)
      Example: Boats to Save People