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

Mental Model

Greedy means picking the best choice right now without looking ahead. It works when local best choices lead to the global best result.

Analogy: Making change for 6 cents with coins [1,3,4]. Greedy picks largest <= remaining: 4 (rem 2), 1 (rem 1), 1 (total 3 coins). But 3+3=2 coins better, so fails. With [1,5,10,25] for 30, greedy 25+5=2 coins, optimal.

Coins [1,3,4], target=6
Greedy: pick 4 -> rem=2 -> pick 1 -> rem=1 -> pick 1 (3 coins)
Better: pick 3 -> rem=3 -> pick 3 (2 coins)

Dry Run Walkthrough

Input: coins: [1,5,10,25], target=30 | coins: [1,3,4], target=6

Goal: Minimum number of coins to make exact target amount

Step 1: Sort coins descending: [25,10,5,1]

coins=[25,10,5,1], rem=30

Why: Greedy always picks largest possible coin <= remaining

Step 2: Pick 25 (<=30), rem=5, count=1

rem=5, count=1

Why: Local best choice

Step 3: Pick 5 (<=5), rem=0, count=2

rem=0, count=2 (works!)

Why: Done, optimal here

Step 4: Now [1,3,4] desc [4,3,1], target=6

rem=6

Why: Test where greedy fails

Step 5: Pick 4 (<=6), rem=2, count=1

rem=2, count=1

Why: Local best

Step 6: Pick 1 (<=2), rem=1, count=2

rem=1, count=2

Why: Next largest <=rem

Step 7: Pick 1 (<=1), rem=0, count=3

count=3

Why: Greedy total 3 coins

Step 8: Optimal: 3+3=6, count=2

count=2

Why: Global better by not picking local best first

Result:

Greedy: 2 coins (works) | 3 coins (fails)
Optimal: 2 | 2
Greedy works for canonical sets, fails otherwise

Annotated Code

DSA Rust

fn greedy_change(coins: &[i32], mut target: i32) -> i32 {
    if target == 0 {
        return 0;
    }
    let mut sorted: Vec<i32> = coins.to_vec();
    sorted.sort_by(|a, b| b.cmp(a));
    let mut count = 0;
    while target > 0 {
        let mut picked = false;
        for &coin in &sorted {
            if coin <= target {
                target -= coin;
                count += 1;
                picked = true;
                break;
            }
        }
        if !picked {
            return -1; // cannot make
        }
    }
    count
}

fn optimal_change(coins: &[i32], target: i32) -> i32 {
    // Simple DP: min coins[i] = min over j<i (coins[i-j] + 1 if j in coins)
    let mut dp = vec![i32::MAX / 2; (target as usize + 1)];
    dp[0] = 0;
    for i in 1..=target as usize {
        for &c in coins {
            if c as usize <= i && dp[i - c as usize] != i32::MAX / 2 {
                dp[i] = (dp[i]).min(dp[i - c as usize] + 1);
            }
        }
    }
    if dp[target as usize] == i32::MAX / 2 { -1 } else { dp[target as usize] }
}

fn main() {
    let coins1 = vec![1,5,10,25];
    let target1 = 30;
    println!("Greedy coins1: {}", greedy_change(&coins1, target1));
    println!("Optimal coins1: {}", optimal_change(&coins1, target1));

    let coins2 = vec![1,3,4];
    let target2 = 6;
    println!("Greedy coins2: {}", greedy_change(&coins2, target2));
    println!("Optimal coins2: {}", optimal_change(&coins2, target2));
}

for &coin in &sorted { if coin <= target { target -= coin; count +=1; break; } }

Pick largest coin <= current remaining target

for i in 1..=target as usize { for &c in coins { if ... dp[i] = min(dp[i], dp[i-c]+1) } }

DP checks all ways: optimal looks ahead unlike greedy

Output

Greedy coins1: 2

Optimal coins1: 2

Greedy coins2: 3

Optimal coins2: 2

Complexity Analysis

Time: O(n log n + target * n) for sort + DP steps in worst case

Space: O(target) for DP array and O(n) for sorted vec

vs Alternative: DP is O(n * target), reliable but slower for large target; greedy faster but incorrect sometimes

Edge Cases

target = 0

returns 0 coins

DSA Rust

if target == 0 { return 0; }

cannot make target (no 1)

returns -1

DSA Rust

if !picked { return -1; }

When to Use This Pattern

When a problem asks for a quick best choice at each step, check if greedy works by verifying if local best leads to global best; if not (like non-canonical coin change), use DP.

Common Mistakes

Mistake: Assuming greedy always gives optimal for coin change
Fix: Test with non-canonical denominations like [1,3,4] for 6

Summary

Greedy picks the largest coin possible at each step hoping for fewest total.

Works for US coins [1,5,10,25] (canonical), fails for [1,3,4].

Key: prove 'greedy choice property' and 'optimal substructure' or use DP.

Practice

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

easy

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

B. Because choosing the best option at each step leads to an optimal solution

C. Because it uses recursion to explore all paths

D. Because it sorts the input data before processing

Solution

1. Step 1: Understand greedy choice property

   A greedy algorithm works when making the best local choice at each step leads to a globally optimal solution.

2. Step 2: Differentiate from other methods

   Unlike exhaustive search or recursion, greedy does not try all solutions but relies on local optimal choices.

3. Final Answer:

   Because choosing the best option at each step leads to an optimal solution -> Option B

4. Quick Check:

   Greedy choice property = A [OK]

Hint: Greedy picks best local choice aiming for global best [OK]

Common Mistakes:

• Thinking greedy tries all solutions
• Confusing greedy with recursion or backtracking
• Assuming sorting alone makes greedy work

2. Which of the following Rust code snippets correctly implements a greedy approach to select intervals with earliest finishing time?

easy

A. intervals.sort_by_key(|x| x.start); let mut count = 0; let mut last_end = 0; for i in &intervals { if i.end >= last_end { count += 1; last_end = i.start; } }

B. intervals.sort_by_key(|x| x.end); let mut count = 0; for i in &intervals { count += 1; }

C. intervals.sort_by_key(|x| x.end); let mut count = 0; let mut last_end = 0; for i in &intervals { if i.start >= last_end { count += 1; last_end = i.end; } }

D. intervals.sort_by_key(|x| x.start); let mut count = 0; for i in &intervals { if i.start > last_end { count += 1; last_end = i.end; } }

Solution

1. Step 1: Identify correct sorting key

   The greedy interval scheduling algorithm sorts intervals by their finishing time (end).

2. Step 2: Check selection condition and update

   It selects intervals starting after or at the last selected interval's end, updating last_end accordingly.

3. Final Answer:

   intervals.sort_by_key(|x| x.end); let mut count = 0; let mut last_end = 0; for i in &intervals { if i.start >= last_end { count += 1; last_end = i.end; } } -> Option C

4. Quick Check:

   Sort by end, pick if start >= last_end = B [OK]

Hint: Sort by finish time, pick intervals starting after last end [OK]

Common Mistakes:

• Sorting by start time instead of end time
• Updating last_end incorrectly
• Counting all intervals without condition

3. Consider the Rust code below that tries to find the minimum number of coins for a given amount using greedy approach with coin denominations [25, 10, 5, 1]. What is the output for amount = 30?

let coins = [25, 10, 5, 1];
let mut amount = 30;
let mut count = 0;
for &coin in &coins {
    count += amount / coin;
    amount %= coin;
}
println!("{}", count);

medium

A. 4

B. 3

C. 5

D. 2

Solution

1. Step 1: Calculate coins for 25-cent

   30 / 25 = 1 coin, remainder 30 % 25 = 5

2. Step 2: Calculate coins for 10-cent, 5-cent, 1-cent

   5 / 10 = 0 coins, remainder 5; 5 / 5 = 1 coin, remainder 0; 0 / 1 = 0 coins

3. Step 3: Sum total coins

   1 (25-cent) + 0 (10-cent) + 1 (5-cent) + 0 (1-cent) = 2 coins

4. Final Answer:

   2 -> Option D

5. Quick Check:

   30 = 25 + 5 = 2 coins [OK]

Hint: Divide amount by largest coin, reduce remainder, sum counts [OK]

Common Mistakes:

• Adding coins incorrectly
• Using wrong coin order
• Ignoring remainder after division

4. The following Rust code attempts to solve the coin change problem greedily with coins [10, 6, 1] and amount 12. It outputs the number of coins used. What is the bug?

let coins = [10, 6, 1];
let mut amount = 12;
let mut count = 0;
for &coin in &coins {
    count += amount / coin;
    amount %= coin;
}
println!("{}", count);

medium

A. The greedy approach fails to find minimum coins for these denominations

B. The code has a syntax error in the for loop

C. The amount variable is not mutable

D. The coins array is not sorted

Solution

1. Step 1: Understand greedy failure for coin set

   Greedy picks 10 once, remainder 2, then two 1 coins = 3 coins total.

2. Step 2: Check for better solution

   Using two 6 coins gives 12 with only 2 coins, better than greedy's 3.

3. Step 3: Identify bug

   The bug is greedy approach itself fails to find minimum coins for this coin set.

4. Final Answer:

   The greedy approach fails to find minimum coins for these denominations -> Option A

5. Quick Check:

   Greedy fails on non-canonical coins = D [OK]

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

Common Mistakes:

• Thinking code syntax is wrong
• Assuming sorting fixes greedy failure
• Ignoring greedy algorithm limitations

5. You want to select activities from a list with start and end times to maximize the number of activities chosen. However, some activities overlap partially. Which approach correctly applies greedy algorithm to solve this, and why might it fail if you choose activities by earliest start time instead of earliest finish time?

hard

A. Sort activities by earliest finish time and pick compatible ones; choosing by start time can miss optimal sets

B. Sort activities by earliest start time and pick all that start earliest; this always works

C. Pick activities randomly; greedy always finds optimal solution

D. Sort activities by longest duration and pick those first; this maximizes usage

Solution

1. Step 1: Identify correct greedy strategy

   Sorting by earliest finish time ensures maximum remaining time for other activities.

2. Step 2: Explain failure of sorting by start time

   Choosing by earliest start time can select long activities blocking many others, missing optimal count.

3. Step 3: Conclude correct approach and failure reason

   Greedy works with earliest finish time sorting; earliest start time sorting may fail to maximize activities.

4. Final Answer:

   Sort activities by earliest finish time and pick compatible ones; choosing by start time can miss optimal sets -> Option A

5. Quick Check:

   Earliest finish time sorting = A [OK]

Hint: Sort by finish time, not start time, to maximize activities [OK]

Common Mistakes:

• Assuming earliest start time sorting always works
• Picking longest duration first
• Ignoring overlap constraints