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

Concept Flow - Why Greedy Works and When It Fails

Start Problem

↓

Choose Best Local Option

↓

Is This Choice Feasible?

No→Backtrack or Fail

Yes↓

Add Choice to Solution

↓

More Choices Left?

Yes→Repeat

No↓

Return Final Solution

The greedy approach picks the best option at each step, checks if it fits, adds it, and repeats until done or fails.

Execution Sample

DSA Go

choices := []int{5, 3, 4, 2}
solution := []int{}
for _, c := range choices {
  if feasible(c, solution) {
    solution = append(solution, c)
  }
}

This code tries to build a solution by adding choices if they are feasible, showing greedy selection.

Execution Table

Step	Operation	Current Choice	Feasible?	Solution State	Reasoning
1	Check first choice	5	Yes	[5]	First choice always feasible, add it
2	Check second choice	3	Yes	[5, 3]	3 fits with 5, add it
3	Check third choice	4	No	[5, 3]	4 conflicts with existing choices, skip
4	Check fourth choice	2	Yes	[5, 3, 2]	2 fits, add it
5	No more choices	-	-	[5, 3, 2]	Finished building solution

💡 All choices checked; solution built by adding feasible choices greedily.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
solution	[]	[5]	[5, 3]	[5, 3]	[5, 3, 2]	[5, 3, 2]
current_choice	N/A	5	3	4	2	N/A

Key Moments - 3 Insights

Why do we skip adding choice 4 even though it looks good?

At step 3 in the execution_table, choice 4 is not feasible because it conflicts with the current solution, so greedy skips it to keep solution valid.

Does greedy always find the best overall solution?

No, greedy picks the best local option each time but may miss better global solutions if choices conflict, shown by skipping choice 4.

What happens if no choice is feasible at some step?

Greedy stops adding choices and returns the current solution, as shown at step 5 when no more choices remain.

Visual Quiz - 3 Questions

Look at the execution_table, what is the solution state after step 2?

A [5, 4]

B [5, 3]

C [5]

D [3, 4]

💡 Hint

Check the 'Solution State' column at step 2 in the execution_table.

At which step does the greedy algorithm skip adding a choice?

A Step 1

B Step 4

C Step 3

D Step 5

💡 Hint

Look for 'Feasible?' column with 'No' in the execution_table.

If choice 4 was feasible, how would the final solution change?

A It would include choice 4

B It would exclude choice 2

C It would be empty

D It would be the same

💡 Hint

Refer to variable_tracker and execution_table to see how adding feasible choices affects solution.

Concept Snapshot

Greedy Algorithm:
- Pick best local choice each step
- Check if choice fits (feasible)
- Add choice if feasible
- Repeat until no choices left
- Works when local best leads to global best
- Fails if local best blocks better future choices

Full Transcript

The greedy algorithm solves problems by choosing the best option available at each step without reconsidering past choices. It checks if the choice fits the current solution and adds it if feasible. This process repeats until no more choices remain. Greedy works well when local best choices lead to the overall best solution. However, it can fail if a locally best choice prevents better solutions later. For example, in the execution, choice 4 was skipped because it conflicted with earlier choices, showing greedy's limitation. Understanding when greedy works or fails helps decide if it's the right approach for a problem.

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