Greedy Core Pattern¶

class Solution:
    """
    Greedy Reachability: Track farthest reachable position.

    Key Insight:
    - At each position i, we can jump anywhere in [i+1, i+nums[i]]
    - If i > farthest_reachable, position i is unreachable, so we fail
    - If farthest_reachable >= last_index at any point, we succeed

    Invariant: farthest_reachable always holds the maximum index
    reachable from any position we've seen so far.

    Time: O(n) | Space: O(1)
    """
    def canJump(self, nums: List[int]) -> bool:
        farthest_reachable = 0
        last_index = len(nums) - 1

        for current_index in range(len(nums)):
            # If current position is unreachable, fail
            if current_index > farthest_reachable:
                return False

            # Update farthest reachable from this position
            farthest_reachable = max(
                farthest_reachable,
                current_index + nums[current_index]
            )

            # Early exit: can already reach the end
            if farthest_reachable >= last_index:
                return True

        return True

class Solution:
    """
    Greedy Jump Counting: Implicit BFS with level boundaries.

    Key Insight:
    - Each "jump" explores all positions reachable from current level
    - current_end marks the boundary of current jump's reach
    - next_farthest tracks the farthest we can reach in next jump
    - When we hit current_end, we must make a jump to continue

    This is BFS without a queue: levels are defined by jump boundaries.

    Time: O(n) | Space: O(1)
    """
    def jump(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return 0

        jump_count = 0
        current_end = 0      # Boundary of current jump's reach
        next_farthest = 0    # Farthest position reachable in next jump

        for current_index in range(len(nums) - 1):  # Don't need to jump from last
            # Extend next jump's reach
            next_farthest = max(
                next_farthest,
                current_index + nums[current_index]
            )

            # Reached current jump's boundary - must make a jump
            if current_index == current_end:
                jump_count += 1
                current_end = next_farthest

                # Early exit: can reach the end
                if current_end >= len(nums) - 1:
                    break

        return jump_count

class Solution:
    """
    Greedy Reset: Track local surplus, reset start on deficit.

    Key Insights:
    1. If total_gas >= total_cost, a valid start exists (pigeonhole principle)
    2. If we can't reach station j from station i, we also can't reach j
       from any station between i and j (they have less accumulated gas)
    3. When surplus goes negative, the next station is a candidate start

    Invariant: current_surplus tracks gas balance since last reset point.

    Time: O(n) | Space: O(1)
    """
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        total_surplus = 0      # Total gas - total cost (feasibility check)
        current_surplus = 0    # Surplus since candidate start
        candidate_start = 0    # Current best starting station

        for station in range(len(gas)):
            net_gain = gas[station] - cost[station]
            total_surplus += net_gain
            current_surplus += net_gain

            # Can't reach next station from candidate_start
            # Reset: next station becomes new candidate
            if current_surplus < 0:
                candidate_start = station + 1
                current_surplus = 0

        # If total is non-negative, candidate_start is valid
        return candidate_start if total_surplus >= 0 else -1

class Solution:
    """
    Two-Pass Greedy: Satisfy left constraint, then right constraint.

    Key Insight:
    - Single pass can't handle both directions simultaneously
    - Forward pass: ensure higher rating than LEFT neighbor → more candy
    - Backward pass: ensure higher rating than RIGHT neighbor → more candy
    - Take max of both constraints at each position

    Greedy Choice: Give minimum candy that satisfies constraints.

    Time: O(n) | Space: O(n)
    """
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        candies = [1] * n  # Everyone gets at least 1

        # Forward pass: satisfy left neighbor constraint
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1

        # Backward pass: satisfy right neighbor constraint
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                # Take max to preserve forward pass constraint
                candies[i] = max(candies[i], candies[i + 1] + 1)

        return sum(candies)

class Solution:
    """
    Sort + Greedy Match: Satisfy least greedy children first.

    Key Insight:
    - Sort children by greed (ascending)
    - Sort cookies by size (ascending)
    - Match smallest sufficient cookie to each child
    - Never "waste" a large cookie on a less greedy child

    Greedy Choice: Always try to satisfy the least greedy unsatisfied child
    with the smallest cookie that works.

    Time: O(n log n + m log m) | Space: O(1) excluding sort
    """
    def findContentChildren(self, greed: List[int], cookies: List[int]) -> int:
        greed.sort()
        cookies.sort()

        child_index = 0
        cookie_index = 0
        satisfied_count = 0

        while child_index < len(greed) and cookie_index < len(cookies):
            # Current cookie can satisfy current child
            if cookies[cookie_index] >= greed[child_index]:
                satisfied_count += 1
                child_index += 1      # Move to next child
                cookie_index += 1     # Use this cookie
            else:
                # Cookie too small, try next (larger) cookie
                cookie_index += 1

        return satisfied_count

class Solution:
    """
    Greedy by Cost Difference: Sort by savings from choosing A over B.

    Key Insight:
    - cost[i] = [cost_A, cost_B]
    - diff = cost_A - cost_B measures "how much cheaper A is"
    - Negative diff: A is cheaper, send to A
    - Positive diff: B is cheaper, send to B
    - Sort by diff, send first n (lowest diff) to A, rest to B

    Greedy Choice: Maximize total savings by prioritizing largest
    cost differences.

    Time: O(n log n) | Space: O(1) excluding sort
    """
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        # Sort by (cost_A - cost_B)
        # People with most "savings from A" come first
        costs.sort(key=lambda x: x[0] - x[1])

        total_cost = 0
        n = len(costs) // 2

        # First n people go to city A (they benefit most from A)
        for i in range(n):
            total_cost += costs[i][0]

        # Remaining n people go to city B
        for i in range(n, 2 * n):
            total_cost += costs[i][1]

        return total_cost

def canReach(nums: List[int]) -> bool:
    farthest = 0
    for i in range(len(nums)):
        if i > farthest:
            return False
        farthest = max(farthest, i + nums[i])
    return True

def minJumps(nums: List[int]) -> int:
    if len(nums) <= 1:
        return 0

    jumps = 0
    current_end = 0
    next_farthest = 0

    for i in range(len(nums) - 1):
        next_farthest = max(next_farthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = next_farthest
    return jumps

def findStart(gain: List[int], cost: List[int]) -> int:
    total = 0
    current = 0
    start = 0

    for i in range(len(gain)):
        net = gain[i] - cost[i]
        total += net
        current += net
        if current < 0:
            start = i + 1
            current = 0

    return start if total >= 0 else -1

def greedyMatch(needs: List[int], supplies: List[int]) -> int:
    needs.sort()
    supplies.sort()

    matched = 0
    supply_idx = 0

    for need in needs:
        while supply_idx < len(supplies) and supplies[supply_idx] < need:
            supply_idx += 1
        if supply_idx < len(supplies):
            matched += 1
            supply_idx += 1

    return matched

def twoPassGreedy(values: List[int]) -> List[int]:
    n = len(values)
    result = [1] * n

    # Forward pass: left constraint
    for i in range(1, n):
        if values[i] > values[i - 1]:
            result[i] = result[i - 1] + 1

    # Backward pass: right constraint
    for i in range(n - 2, -1, -1):
        if values[i] > values[i + 1]:
            result[i] = max(result[i], result[i + 1] + 1)

    return result

def optimalAssignment(costs: List[List[int]]) -> int:
    # costs[i] = [option_A_cost, option_B_cost]
    # Sort by advantage of A over B
    costs.sort(key=lambda x: x[0] - x[1])

    n = len(costs) // 2
    total = 0

    # First half to option A
    for i in range(n):
        total += costs[i][0]

    # Second half to option B
    for i in range(n, 2 * n):
        total += costs[i][1]

    return total