Greedy

One-liner: at every step take the choice that looks best right now, and never come back to change it — which is only allowed when you can argue that the best local choice can never hurt the final answer.

The analogy

You are packing a suitcase for a trip and you must leave in five minutes. You grab the most useful thing first, then the next most useful, until the case is full. You never unpack and rethink. That works when "most useful" really is the right order. It fails when two small items together beat one big one — and then you need to compare combinations, which is dynamic programming. Greedy is the fast path; the work is proving it is safe.

Recognition signals

Reach for a greedy approach when you see these:

1. You want a maximum, minimum or yes/no answer, not a list of all answers.
2. There is a natural order to the choices (earliest finish, smallest first, farthest reach) and a choice made early does not block a better one later.
3. A small instance can be argued by hand: "if I did anything else here, I could swap it for my greedy choice and be no worse off" (the exchange argument).
4. The obvious brute force tries many combinations, and a sort or a single running value would replace it.

Step-by-step walkthrough

Take Jump Game on nums = [2, 3, 1, 1, 4], where nums[i] is the longest jump from index i:

1. Keep one number: farthest, the furthest index we can reach so far. It starts at 0.
2. At index 0, jump length 2 reaches index 2, so farthest = 2.
3. At index 1, we are inside what we can reach, and 1 + 3 = 4, so farthest = 4.
4. Index 4 is the last index and farthest ≥ 4: we can reach the end. Return true.
5. For [3, 2, 1, 0, 4], farthest stops at 3. At index 4 we have i > farthest, a gap we cannot cross. Return false.

We never tried every path; one running value summarised everything the next step needs.

Code template

Order the choices if the problem needs it, keep one running value, and commit to each safe choice for good. The two marked spots change per problem.

// Template: make the locally best choice, never revisit it, and keep only the state the next choice needs.
func greedyTemplate(items []int) int {
	slices.Sort(items) // 1. order the choices so the "best" one is always next (not every problem needs this)
	best := 0          // 2. the one running value the next decision depends on
	for _, x := range items {
		if true /* 3. is taking x safe, given only best? */ {
			best += x // 4. commit to it; we never undo this
		}
	}
	return best
}

Why each part exists:

The real solutions

Jump Game — track the farthest reachable index. If you ever stand past it, you are stuck:

// CanJump: can you reach the last index if nums[i] is the max jump length from i?
// Greedy: track the farthest index reachable so far. If we ever stand beyond it, we are stuck.
func CanJump(nums []int) bool {
	farthest := 0
	for i, jump := range nums {
		if i > farthest { // an unreachable gap
			return false
		}
		farthest = max(farthest, i+jump)
	}
	return true
}

Jump Game II (fewest jumps) — the same reach idea, but count a jump each time you hit the edge of the current jump. end is that edge and farthest is the best edge of the next jump:

// MinJumps: fewest jumps to reach the last index (it is always reachable).
// Greedy BFS-by-ranges: end is the edge of the current jump; farthest is the best edge of the next one.
func MinJumps(nums []int) int {
	jumps, end, farthest := 0, 0, 0
	for i := 0; i < len(nums)-1; i++ {
		farthest = max(farthest, i+nums[i])
		if i == end { // we must jump now: take the best landing we saw
			jumps++
			end = farthest
		}
	}
	return jumps
}

Assign Cookies — serve the least greedy child with the smallest cookie that satisfies them. Wasting a big cookie on a small appetite can only hurt:

// FindContentChildren: each child needs a cookie of size >= their greed; one cookie per child.
// Greedy: serve the least greedy child with the smallest cookie that satisfies them.
func FindContentChildren(greed, cookies []int) int {
	g, s := slices.Clone(greed), slices.Clone(cookies)
	slices.Sort(g)
	slices.Sort(s)
	child := 0
	for _, cookie := range s {
		if child < len(g) && cookie >= g[child] {
			child++ // this cookie satisfies the next-least-greedy child
		}
	}
	return child
}

Partition Labels — a part must stretch to the last occurrence of every letter it contains; close it exactly when the scan reaches that edge:

// PartitionLabels: split s so each letter appears in at most one part; return the part sizes.
// Greedy: a part must reach at least the last occurrence of every letter inside it.
func PartitionLabels(s string) []int {
	last := map[rune]int{}
	for i, r := range s {
		last[r] = i
	}
	var sizes []int
	start, end := 0, 0
	for i, r := range s {
		end = max(end, last[r]) // extend the part to cover this letter's last occurrence
		if i == end {           // nothing inside the part appears later: close it
			sizes = append(sizes, end-start+1)
			start = i + 1
		}
	}
	return sizes
}

Gas Station — if the tank goes negative at i, no start between the old start and i can work, so restart after i. If total gas is below total cost, no start works at all:

// CanCompleteCircuit: the start index that completes the circular route, or -1.
// Greedy: if the tank goes negative at i, no start in [start, i] can work, so restart at i+1.
func CanCompleteCircuit(gas, cost []int) int {
	total, tank, start := 0, 0, 0
	for i := range gas {
		diff := gas[i] - cost[i]
		total += diff
		tank += diff
		if tank < 0 {
			start = i + 1
			tank = 0
		}
	}
	if total < 0 {
		return -1
	}
	return start
}

Looking for interval greedy (earliest end first, minimum arrows)? That is on the Intervals page, built on the same idea.

Complexity

When there is a sort it dominates; the greedy pass itself is linear.

Common mistakes

Practice ladder

Ordered Easy → Hard. For each, say aloud what the local choice is and why it can never hurt.

1. 1.
   Assign Cookies

   Who should get the smallest cookie that still works?
   Easy
2. 2.
   Best Time to Buy and Sell Stock II

   Can you collect every upward step?
   Medium
3. 3.
   Jump Game

   One number: how far can you get?
   Medium
4. 4.
   Gas Station

   If the tank dies at i, what does that say about earlier starts?
   Medium
5. 5.
   Partition Labels
   Medium
6. 6.
   Jump Game II

   Count the edges of the reachable range, not the paths.
   Medium
7. 7.
   Candy

   Two passes: satisfy the left neighbour, then the right.
   Hard

Which pattern? Drills

Unlabeled problems — pick the pattern, then read why.