Why Greedy Works and When It Fails in DSA C - 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

↓

Is Problem Fully Solved?

No→Repeat Choose Best Local Option

Yes↓

Return Solution

The greedy method picks the best local choice at each step, checks if it's allowed, adds it, and repeats until the problem is solved or fails.

Execution Sample

DSA C

int greedy_example(int arr[], int n) {
  int sum = 0;
  for (int i = 0; i < n; i++) {
    if (arr[i] > 0) sum += arr[i];
  }
  return sum;
}

This code sums all positive numbers in an array by greedily adding only positive values.

Execution Table

Step	Operation	Current Element	Decision	Sum So Far	Reasoning
1	Check arr[0]	3	Add 3	3	3 > 0, add to sum
2	Check arr[1]	-1	Skip	3	-1 <= 0, skip
3	Check arr[2]	4	Add 4	7	4 > 0, add to sum
4	Check arr[3]	0	Skip	7	0 <= 0, skip
5	Check arr[4]	2	Add 2	9	2 > 0, add to sum
6	End	-	-	9	All elements processed

💡 All elements checked, sum of positive numbers is 9

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
sum	0	3	3	7	7	9	9
i	0	1	2	3	4	5	5

Key Moments - 3 Insights

Why does greedy sometimes fail to find the best solution?

Because greedy only looks at the best immediate choice without considering future consequences, it can miss better overall solutions. See execution_table step 2 where skipping negative is good here, but in other problems, a local best choice might block better future options.

When is greedy guaranteed to work?

Greedy works when the problem has the 'greedy choice property' and 'optimal substructure', meaning local best choices lead to global best. The execution_table shows a simple sum where adding positive numbers always helps.

What happens if the greedy choice is not feasible?

The flow in concept_flow shows that if a choice is not feasible, the algorithm must backtrack or fail. Greedy algorithms usually do not backtrack, so they fail or give suboptimal results if feasibility is violated.

Visual Quiz - 3 Questions

Look at the execution_table, what is the sum after checking the third element?

A 3

B 7

C 9

D 4

💡 Hint

Check the 'Sum So Far' column at Step 3 in the execution_table.

At which step does the algorithm skip adding the element because it is not positive?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Decision' column in execution_table for when 'Skip' happens.

If the array had a negative number that must be included for a better total, what would happen to the greedy approach?

A It would still find the best solution

B It would fail or give a suboptimal solution

C It would backtrack to include the negative number

D It would ignore all positive numbers

💡 Hint

Refer to key_moments about greedy failing when local best choices block better future solutions.

Concept Snapshot

Greedy Algorithm:
- Pick best local choice each step
- Check if choice is feasible
- Add choice to solution
- Repeat until done
- Works if problem has greedy choice property
- May fail if future consequences ignored

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 is allowed, adds it to the solution, and repeats until the problem is solved or no choices remain. This works well when the problem has special properties ensuring local best choices lead to a global best solution. However, greedy can fail if it ignores future consequences, leading to suboptimal results. The example code sums positive numbers by greedily adding only positive values. The execution table shows step-by-step how the sum changes. Key moments explain why greedy sometimes fails and when it works. The quiz tests understanding of the execution steps and greedy limitations.