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

No→Return Final Solution

Yes↓

Repeat Choosing Best Local Option

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

Execution Sample

DSA Java

int[] weights = {2, 3, 4, 5};
int capacity = 7;
int total = 0;
for (int w : weights) {
  if (total + w <= capacity) total += w;
}
System.out.println(total);

This code picks weights greedily until the capacity is reached or exceeded.

Execution Table

Step	Operation	Current Weight	Total Weight Before	Feasible?	Total Weight After	Visual State
1	Check weight 2	2	0	Yes	2	[2]
2	Check weight 3	3	2	Yes	5	[2 -> 3]
3	Check weight 4	4	5	No	5	[2 -> 3] (skip 4)
4	Check weight 5	5	5	No	5	[2 -> 3] (skip 5)
5	End loop	-	5	-	5	[2 -> 3] Final solution

💡 No more weights or capacity exceeded, loop ends.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
total	0	2	5	5	5	5

Key Moments - 3 Insights

Why do we skip weight 4 even though it is less than capacity?

At step 3 in the execution_table, adding 4 to total 5 would exceed capacity 7, so it's skipped to keep solution feasible.

Why does greedy fail if weights were {5, 4, 3} instead?

Greedy picks 5 first, then can't add 4 or 3 without exceeding capacity, missing better total 7 (4+3). This shows greedy can fail if local best isn't globally best.

When does greedy guarantee the best solution?

Greedy works when problem has 'greedy choice property' and 'optimal substructure', meaning local best choices lead to global best, as shown by the feasible checks in the table.

Visual Quiz - 3 Questions

Look at the execution_table, what is the total weight after step 2?

A 2

B 5

C 7

D 0

💡 Hint

Check the 'Total Weight After' column at step 2 in execution_table.

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

A Step 3

B Step 1

C Step 2

D Step 4

💡 Hint

Look for 'Feasible?' column with 'No' and 'Visual State' showing skip in execution_table.

If the weights array was sorted descending as {5,4,3,2}, how would the total weight after step 1 change?

A It would be 0

B It would be 2

C It would be 5

D It would be 7

💡 Hint

Check how the first weight affects total in variable_tracker and execution_table.

Concept Snapshot

Greedy Algorithm:
- Pick best local option each step
- Check if adding it keeps solution feasible
- Add if yes, skip if no
- Repeat until no options left
- Works if local choices lead to global best
- Can fail 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 previous choices. It checks if adding the current choice keeps the solution feasible, adds it if yes, or skips if no. This repeats until no more choices remain. The example code adds weights to a total until capacity is reached. The execution table shows each step's decision and total weight. Greedy works well when local best choices lead to a global best solution, but it can fail if early choices block better overall solutions. Understanding when greedy works or fails helps choose 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 uses recursion to explore all paths

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

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

D. Because it sorts the input data before processing

Solution

1. Step 1: Understand greedy choice property

   A greedy algorithm chooses the best option available at each step without reconsidering previous choices.

2. Step 2: Connect greedy choice to global optimum

   This local best choice leads to a global optimum only if the problem has the greedy choice property.

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 now, not all possibilities [OK]

Common Mistakes:

• Thinking greedy tries all solutions
• Confusing greedy with recursion
• Assuming sorting alone makes greedy correct

2. Which of the following is the correct syntax to start a greedy algorithm loop in Java to process an array arr of length n?

easy

A. foreach (int i : arr)

B. for i in range(0, n):

C. while (i <= n) { i++; }

D. for (int i = 0; i < n; i++)

Solution

1. Step 1: Identify Java loop syntax

   Java uses for loops with initialization, condition, and increment: for (int i = 0; i < n; i++)

2. Step 2: Check options for Java correctness

   for (int i = 0; i < n; i++) matches Java syntax; B is Python, C is incomplete and incorrect, D is incorrect syntax for array iteration.

3. Final Answer:

   for (int i = 0; i < n; i++) -> Option D

4. Quick Check:

   Java for loop syntax = for (int i = 0; i < n; i++) [OK]

Hint: Java for loops use int i=0; i

Common Mistakes:

• Using Python syntax in Java
• Incorrect loop conditions
• Misusing foreach syntax

3. Consider the following Java code snippet for selecting intervals greedily by earliest finish time:

int[][] intervals = {{1,3},{2,5},{4,7}};
Arrays.sort(intervals, (a,b) -> a[1] - b[1]);
int count = 0, end = 0;
for (int[] interval : intervals) {
  if (interval[0] >= end) {
    count++;
    end = interval[1];
  }
}
System.out.println(count);

What is the output?

medium

A. 3

B. 2

C. 1

D. 0

Solution

1. Step 1: Sort intervals by finish time

   Sorted intervals by end time: {1,3}, {2,5}, {4,7}

2. Step 2: Select intervals greedily

   Select {1,3} first (count=1, end=3). Next {2,5} starts at 2 < 3, skip. Next {4,7} starts at 4 >= 3, select (count=2).

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Greedy interval selection = 2 [OK]

Hint: Pick intervals by earliest finish time [OK]

Common Mistakes:

• Not sorting intervals
• Selecting overlapping intervals
• Counting all intervals without check

4. The following Java code attempts to solve the coin change problem using a greedy approach:

int[] coins = {1, 3, 4};
int amount = 6;
int count = 0;
for (int i = coins.length - 1; i >= 0; i--) {
  while (amount >= coins[i]) {
    amount -= coins[i];
    count++;
  }
}
System.out.println(count);

What is the output and what is the problem with this approach?

medium

A. 3; Greedy fails because it doesn't find minimum coins

B. 3; Greedy always finds minimum coins

C. 6; Code has syntax error

D. 0; Code does not run

Solution

1. Step 1: Trace greedy coin selection

   Start with coin 4: amount=6>=4, subtract 4 (amount=2), count=1. Next coin 3: amount=2<3 skip. Next coin 1: amount=2>=1 subtract twice, count=3 total coins.

2. Step 2: Check minimum coins possible

   Minimum coins for 6 are 2 (3+3), but greedy picks 3 coins (4+1+1). Greedy fails here.

3. Final Answer:

   3; Greedy fails because it doesn't find minimum coins -> Option A

4. Quick Check:

   Greedy coin change fails = 3; Greedy fails because it doesn't find minimum coins [OK]

Hint: Greedy may fail if coin set is non-canonical [OK]

Common Mistakes:

• Assuming greedy always finds minimum coins
• Ignoring coin order importance
• Confusing output count with amount

5. You want to schedule the maximum number of non-overlapping meetings in one room. Meetings are given as int[][] meetings = {{0, 30}, {5, 10}, {15, 20}, {25, 35}}. Which greedy strategy will always give the optimal solution and why?

hard

A. Select meetings by earliest finish time because it leaves room for more meetings

B. Select meetings by shortest duration because shorter meetings fit more

C. Select meetings by latest start time because it prioritizes recent meetings

D. Select meetings by earliest start time because it schedules more meetings

Solution

1. Step 1: Understand meeting scheduling problem

   Goal is to maximize non-overlapping meetings in one room.

2. Step 2: Analyze greedy strategies

   Choosing earliest finish time frees room earliest, allowing more meetings after.

3. Step 3: Check other strategies

   Earliest start or shortest duration can cause overlaps or miss optimal sets.

4. Final Answer:

   Select meetings by earliest finish time because it leaves room for more meetings -> Option A

5. Quick Check:

   Earliest finish time = optimal scheduling [OK]

Hint: Pick meetings finishing earliest to fit more [OK]

Common Mistakes:

• Choosing earliest start time
• Picking shortest duration meetings
• Ignoring finish times