Why Greedy Works and When It Fails in DSA Go - Why This Pattern

Mental Model

Greedy means choosing the best option right now without looking ahead. It works when these choices lead to the best overall answer.

Analogy: Imagine picking coins from a table one by one, always taking the biggest coin you see first. If the coins are simple, this works well. But if some small coins add up better later, greedy can fail.

Coins on table: 5 1 1 10 1 5
Greedy picks biggest coin each time -> 10 -> 5 -> 5 -> 1 -> 1 -> 1

Dry Run Walkthrough

Input: Coins: [5, 1, 1, 10, 1, 5], pick coins to maximize sum by choosing biggest coin available each step

Goal: Show when greedy picking biggest coin works and when it fails

Step 1: Pick biggest coin 10

Picked: 10
Remaining: 5 -> 1 -> 1 -> 1 -> 5

Why: Choosing biggest coin first seems best to get max sum

Step 2: Pick biggest coin 5

Picked: 10 -> 5
Remaining: 1 -> 1 -> 1 -> 5

Why: Next biggest coin chosen greedily

Step 3: Pick biggest coin 5

Picked: 10 -> 5 -> 5
Remaining: 1 -> 1 -> 1

Why: Still picking biggest coin available

Step 4: Pick coin 1

Picked: 10 -> 5 -> 5 -> 1
Remaining: 1 -> 1

Why: Only small coins left, pick any

Step 5: Pick coin 1

Picked: 10 -> 5 -> 5 -> 1 -> 1
Remaining: 1

Why: Continue picking remaining coins

Step 6: Pick coin 1

Picked: 10 -> 5 -> 5 -> 1 -> 1 -> 1
Remaining: null

Why: All coins picked

Step 7: Calculate total sum

Sum = 10 + 5 + 5 + 1 + 1 + 1 = 23

Why: Sum of greedy picks

Step 8: Compare with non-greedy pick: e.g. 1 + 1 + 1 + 5 + 5 + 10 = 23 (same as greedy)

Greedy sum 23 is optimal here

Why: Greedy works well in this example

Result:

Picked coins: 10 -> 5 -> 5 -> 1 -> 1 -> 1 -> null
Total sum: 23

Annotated Code

DSA Go

package main

import (
	"fmt"
	"sort"
)

// pickCoinsGreedy picks coins by always choosing the biggest coin available
func pickCoinsGreedy(coins []int) []int {
	sorted := make([]int, len(coins))
	copy(sorted, coins)
	sort.Sort(sort.Reverse(sort.IntSlice(sorted))) // sort descending

	picked := []int{}
	for _, coin := range sorted {
		picked = append(picked, coin) // pick biggest coin
	}
	return picked
}

func main() {
	coins := []int{5, 1, 1, 10, 1, 5}
	picked := pickCoinsGreedy(coins)
	sum := 0
	for _, c := range picked {
		sum += c
	}
	for i, c := range picked {
		if i < len(picked)-1 {
			fmt.Printf("%d -> ", c)
		} else {
			fmt.Printf("%d -> null\n", c)
		}
	}
	fmt.Printf("Total sum: %d\n", sum)
}

sort.Sort(sort.Reverse(sort.IntSlice(sorted))) // sort descending

sort coins descending to pick biggest first

for _, coin := range sorted { picked = append(picked, coin) // pick biggest coin }

pick coins one by one from biggest to smallest

Output

10 -> 5 -> 5 -> 1 -> 1 -> 1 -> null

Total sum: 23

Complexity Analysis

Time: O(n log n) because sorting the coins takes that time

Space: O(n) because we create a copy of the coins array

vs Alternative: Compared to checking all combinations (exponential), greedy is much faster but may fail if local best choices don't lead to global best

Edge Cases

Empty coin list

Returns empty picked list with sum 0

DSA Go

copy(sorted, coins) handles empty slice safely

All coins same value

Greedy picks all coins, sum is total of all coins

DSA Go

sort.Sort still works correctly with equal elements

Coins with many small and one large (e.g. 1,1,1,10)

Greedy picks 10 first, which is best here; but in other problems greedy may fail

DSA Go

No special guard; shows greedy may fail in other contexts

When to Use This Pattern

When a problem asks for a maximum or minimum by making choices step-by-step, check if picking the best option now leads to the best overall result; if yes, greedy works.

Common Mistakes

Mistake: Assuming greedy always gives the best answer without proof
Fix: Check problem properties like greedy choice and optimal substructure before using greedy

Summary

Greedy picks the best choice at each step hoping for the best overall result.

Use greedy when local best choices lead to global best solution.

The key is that greedy works only if the problem has the greedy choice property.

Practice

1. What is the main reason a greedy algorithm works correctly for some problems?

easy

A. Because it sorts the input data before processing

B. Because it tries all possible solutions and picks the best one

C. Because it makes the best choice at each step hoping for a global optimum

D. Because it uses recursion to explore all paths

Solution

1. Step 1: Understand greedy choice property

   A greedy algorithm makes the best local choice at each step, aiming for a global best solution.

2. Step 2: Differentiate from exhaustive search

   Unlike trying all solutions or recursion, greedy does not explore all paths but relies on local optimality.

3. Final Answer:

   Because it makes the best choice at each step hoping for a global optimum -> Option C

4. Quick Check:

   Greedy choice property = Because it makes the best choice at each step hoping for a global optimum [OK]

Hint: Greedy picks best local choice, not all possibilities [OK]

Common Mistakes:

• Confusing greedy with exhaustive search
• Thinking greedy always tries all solutions
• Assuming sorting alone makes greedy correct

2. Which of the following Go code snippets correctly implements a greedy step to pick the largest number from a slice?

easy

A. max := nums[0]
for _, v := range nums {
if v > max {
max = v
}
}

B. max := 0
for i := 1; i < len(nums); i++ {
if nums[i] < max {
max = nums[i]
}
}

C. max := nums[0]
for i := 0; i < len(nums); i++ {
if nums[i] < max {
max = nums[i]
}
}

D. max := nums[0]
for _, v := range nums {
if v < max {
max = v
}
}

Solution

1. Step 1: Identify correct max initialization and comparison

   Initialize max with first element and update if current value is greater.

2. Step 2: Check loop and condition correctness

   max := nums[0] for _, v := range nums { if v > max { max = v } } uses correct range loop and updates max when v > max.

3. Final Answer:

   Option A correctly finds the largest number -> Option A

4. Quick Check:

   Correct max update condition = max := nums[0] for _, v := range nums { if v > max { max = v } } [OK]

Hint: Update max only if current value is greater [OK]

Common Mistakes:

• Using '<' instead of '>' to find max
• Initializing max to zero instead of first element
• Comparing incorrectly inside loop

3. What will be the output of the following Go code that tries to select intervals greedily by earliest finish time?

package main
import "fmt"
func main() {
  intervals := [][]int{{1,4},{3,5},{0,6},{5,7},{8,9},{5,9}}
  selected := [][]int{}
  lastEnd := 0
  for _, interval := range intervals {
    if interval[0] >= lastEnd {
      selected = append(selected, interval)
      lastEnd = interval[1]
    }
  }
  fmt.Println(selected)
}

medium

A. [[1 4] [5 7] [8 9]]

B. [[1 4] [3 5] [5 7] [8 9]]

C. [[0 6] [8 9]]

D. [[1 4] [5 9]]

Solution

1. Step 1: Understand greedy selection by earliest finish time

   Intervals are checked in given order; select if start >= last selected end.

2. Step 2: Trace selection step-by-step

   Selected intervals: [1,4] (lastEnd=4), skip [3,5], skip [0,6], select [5,7] (lastEnd=7), select [8,9].

3. Final Answer:

   [[1 4] [5 7] [8 9]] -> Option A

4. Quick Check:

   Greedy interval selection = [[1 4] [5 7] [8 9]] [OK]

Hint: Pick intervals starting after last end time [OK]

Common Mistakes:

• Not updating lastEnd correctly
• Selecting overlapping intervals
• Assuming input is sorted by finish time

4. The following Go code tries to solve the coin change problem greedily but sometimes fails. What is the bug?

package main
import "fmt"
func main() {
  coins := []int{25, 10, 5, 1}
  amount := 30
  count := 0
  for _, coin := range coins {
    count += amount / coin
    amount = amount % coin
  }
  fmt.Println(count)
}

medium

A. The coins slice is not sorted in ascending order

B. The greedy approach fails for some coin sets, but code logic is correct

C. The code does not update amount correctly inside the loop

D. The count variable should be reset inside the loop

Solution

1. Step 1: Analyze greedy coin change logic

   The code picks largest coins first, counting how many fit, updating amount correctly.

2. Step 2: Understand greedy failure cases

   Greedy works for US coins but fails for some coin sets; code logic is correct but approach can fail.

3. Final Answer:

   The greedy approach fails for some coin sets, but code logic is correct -> Option B

4. Quick Check:

   Greedy correctness depends on coin set = The greedy approach fails for some coin sets, but code logic is correct [OK]

Hint: Greedy coin change fails on non-canonical coin sets [OK]

Common Mistakes:

• Thinking code has syntax or logic error
• Assuming coin order must be ascending
• Resetting count inside loop incorrectly

5. You want to schedule the maximum number of non-overlapping meetings from a list of start and end times. Which greedy strategy guarantees the optimal solution?

hard

A. Always pick the meeting with the latest start time

B. Always pick the meeting with the shortest duration

C. Always pick the meeting with the earliest start time

D. Always pick the meeting with the earliest finish time

Solution

1. Step 1: Recall interval scheduling greedy strategy

   The proven greedy method is to pick meetings finishing earliest to maximize remaining time.

2. Step 2: Compare other strategies

   Picking earliest start or shortest duration can cause overlaps and miss optimal count.

3. Final Answer:

   Always pick the meeting with the earliest finish time -> Option D

4. Quick Check:

   Earliest finish time strategy = Always pick the meeting with the earliest finish time [OK]

Hint: Pick meetings finishing earliest to maximize schedule [OK]

Common Mistakes:

• Choosing earliest start time instead of finish time
• Picking shortest duration meetings incorrectly
• Assuming latest start time works best