# Greedy — Part 1: The Pattern

A greedy algorithm builds a solution by making the **locally best choice at each step** and never reconsidering it. When it works, it's the simplest and fastest solution: usually one pass, or a sort plus one pass. The hard part is knowing **when** it works. Greedy is correct only if a locally optimal choice can always be extended to a globally optimal solution, and in interviews you're expected to justify that with a short argument, or to recognize that the problem needs dynamic programming instead.

![Greedy keeps the farthest reachable index while scanning](diagrams/01-jump-reach.svg)

## 1. Typical Greedy Shapes

| Shape | Example | Greedy rule |
|---|---|---|
| running value, reset when it stops helping | Maximum Subarray (Kadane), stock profit | extend or restart |
| farthest reach | Jump Game I/II | keep the max index reachable so far |
| sort, then sweep | intervals, meeting rooms, assign cookies | earliest end first / smallest that fits |
| balance / deficit | Gas Station, Lemonade Change | if the running balance goes negative, restart after it |
| last occurrence | Partition Labels | extend the current part to the last occurrence of every letter in it |
| smallest available | Hand of Straights, task scheduling | always start from the smallest remaining item |

## 2. Templates

```typescript
function maxSubarrayTemplate(nums: number[]): number {
  let best = nums[0], cur = nums[0];
  for (let i = 1; i < nums.length; i++) {
    cur = Math.max(nums[i], cur + nums[i]);
    best = Math.max(best, cur);
  }
  return best;
}

function canReachEnd(nums: number[]): boolean {
  let reach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > reach) return false;
    reach = Math.max(reach, i + nums[i]);
  }
  return true;
}
```

```python
def max_subarray_template(nums):          # Kadane: extend or restart, keep the best
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)             # a negative running sum only hurts → restart
        best = max(best, cur)
    return best

def can_reach_end(nums):                  # track the farthest reachable index
    reach = 0
    for i, step in enumerate(nums):
        if i > reach:
            return False
        reach = max(reach, i + step)
    return True
```

## 3. Proving a Greedy Choice (Briefly)

Interviewers accept a compact argument. Two standard ones:

- **Exchange argument:** take any optimal solution that differs from the greedy one at the first choice; swap in the greedy choice and show the solution is no worse. (Used for "earliest end first" in interval scheduling.)
- **Stays ahead:** show that after every step, the greedy solution is at least as good as any other on some measure (e.g. Jump Game: greedy reach is never smaller than any strategy's reach).

## 4. When Greedy Fails

Coin change with coins `[1, 3, 4]` and amount 6: greedy takes 4 + 1 + 1 = 3 coins, but 3 + 3 = 2 coins is optimal. Whenever an early choice can **block** a better combination later, you need **dynamic programming** (`02-dynamic_programming_fundamentals`). A useful habit: before committing to greedy, try to construct a small counterexample.

## Common Pitfalls

1. **Assuming greedy works without a counterexample check** (coin change, 0/1 knapsack).
2. **Sorting by the wrong key** (start vs end, value vs value/weight ratio).
3. **Initializing Kadane with 0** when all numbers can be negative (start from `nums[0]`).
4. **Off-by-one in reach checks:** you're stuck when the current index is greater than the reach.
5. **Not stating the justification** ("why is this choice safe?").

## Quick Reference

```text
Kadane: cur = max(x, cur + x); best = max(best, cur)
Jump Game: if i > reach: fail; reach = max(reach, i + a[i])
Gas Station: if total < 0 → -1; reset start when the tank goes negative
Justify: exchange argument or "stays ahead"; else → DP
```