Greedy vs DP How to Know Which to Apply in DSA Javascript - Trade-offs & Analysis

Mental Model

Greedy picks the best choice now, hoping it leads to the best overall. DP looks at all choices and remembers past results to find the best overall.

Analogy: Imagine choosing snacks from a buffet: greedy grabs the tastiest snack first without thinking ahead, while DP plans the whole meal to get the best combination of snacks.

Choices: 1 -> 2 -> 3 -> 4 -> null
Greedy: picks one step at a time ->
DP: explores all paths and remembers best scores ↓

Dry Run Walkthrough

Input: Problem: Choose coins to make 6 cents from coins [1, 3, 4]. Compare greedy and DP approaches.

Goal: Show how greedy picks coins step-by-step and may fail, while DP finds the minimum coins needed.

Step 1: Greedy picks largest coin ≤ 6, which is 4

Chosen coins: 4 -> Remaining amount: 2

Why: Greedy tries to reduce amount quickly by picking largest coin

Step 2: Greedy picks largest coin ≤ 2, which is 1

Chosen coins: 4 -> 1 -> Remaining amount: 1

Why: Greedy continues picking largest coin possible

Step 3: Greedy picks largest coin ≤ 1, which is 1

Chosen coins: 4 -> 1 -> 1 -> Remaining amount: 0

Why: Greedy finishes by picking smallest coin

Step 4: DP tries all coins for amount 6 and finds minimum coins needed

DP table: minCoins[0]=0, minCoins[1]=1, minCoins[2]=2, minCoins[3]=1, minCoins[4]=1, minCoins[5]=2, minCoins[6]=2

Why: DP builds solution bottom-up remembering best results

Step 5: DP solution picks coins 3 and 3 for total 6 with 2 coins

Chosen coins: 3 -> 3 -> null

Why: DP finds better solution than greedy

Result:

Greedy chosen coins: 4 -> 1 -> 1 -> null (3 coins)
DP chosen coins: 3 -> 3 -> null (2 coins)

Annotated Code

DSA Javascript

class CoinChange {
  constructor(coins) {
    this.coins = coins;
  }

  greedyChange(amount) {
    let result = [];
    let remaining = amount;
    while (remaining > 0) {
      // pick largest coin <= remaining
      let coin = this.coins.filter(c => c <= remaining).sort((a,b) => b - a)[0];
      if (!coin) break;
      result.push(coin);
      remaining -= coin;
    }
    return result;
  }

  dpChange(amount) {
    let dp = Array(amount + 1).fill(Infinity);
    let coinUsed = Array(amount + 1).fill(-1);
    dp[0] = 0;

    for (let i = 1; i <= amount; i++) {
      for (let coin of this.coins) {
        if (coin <= i && dp[i - coin] + 1 < dp[i]) {
          dp[i] = dp[i - coin] + 1; // update min coins
          coinUsed[i] = coin; // remember coin used
        }
      }
    }

    if (dp[amount] === Infinity) return [];

    let result = [];
    let curr = amount;
    while (curr > 0) {
      result.push(coinUsed[curr]); // pick coin used
      curr -= coinUsed[curr];
    }
    return result;
  }
}

const coins = [1, 3, 4];
const amount = 6;
const changer = new CoinChange(coins);

const greedyResult = changer.greedyChange(amount);
const dpResult = changer.dpChange(amount);

console.log("Greedy chosen coins: " + greedyResult.join(" -> ") + " -> null");
console.log("DP chosen coins: " + dpResult.join(" -> ") + " -> null");

let coin = this.coins.filter(c => c <= remaining).sort((a,b) => b - a)[0];

pick largest coin less than or equal to remaining amount

dp[i] = dp[i - coin] + 1; // update min coins

update dp with minimum coins needed for amount i

coinUsed[i] = coin; // remember coin used

store coin used to reconstruct solution

while (curr > 0) { result.push(coinUsed[curr]); curr -= coinUsed[curr]; }

reconstruct coin combination from dp table

Output

Greedy chosen coins: 4 -> 1 -> 1 -> null

DP chosen coins: 3 -> 3 -> null

Complexity Analysis

Time: O(n * amount) because DP tries all coins for each amount up to target

Space: O(amount) for DP arrays storing minimum coins and coin choices

vs Alternative: Greedy is faster O(amount * n) but can give wrong answer; DP is slower but always correct

Edge Cases

amount is 0

returns empty list since no coins needed

DSA Javascript

dp[0] = 0;

no coins smaller than amount

greedy returns empty list; DP returns empty list indicating no solution

DSA Javascript

if (!coin) break;

coins array empty

both methods return empty list as no coins available

DSA Javascript

this.coins.filter(c => c <= remaining)

When to Use This Pattern

When a problem asks for an optimal solution by making choices step-by-step, try greedy if local best choices seem to lead to global best. If not sure or overlapping subproblems exist, use DP to explore all options and remember results.

Common Mistakes

Mistake: Assuming greedy always works without checking problem properties
Fix: Test greedy on examples; if it fails, switch to DP

Mistake: Not storing intermediate results in DP causing repeated work
Fix: Use arrays or memoization to remember past results

Summary

Greedy picks the best immediate choice hoping for global best; DP tries all choices and remembers results for guaranteed best.

Use greedy when problem has greedy-choice property; use DP when problem has overlapping subproblems and optimal substructure.

The key is to check if local best choices lead to global best; if not, DP is the safe approach.

Practice

1. Which of the following best describes when to use a greedy algorithm instead of dynamic programming?

easy

A. When the problem needs to store results of subproblems

B. When the problem requires checking all possible solutions

C. When overlapping subproblems are present

D. When the problem has the greedy choice property and optimal substructure

Solution

1. Step 1: Understand greedy choice property

   A greedy algorithm works when choosing the best option at each step leads to a global optimum, known as the greedy choice property.

2. Step 2: Compare with dynamic programming conditions

   Dynamic programming is used when problems have overlapping subproblems and optimal substructure, but greedy algorithms require only the greedy choice property and optimal substructure.

3. Final Answer:

   When the problem has the greedy choice property and optimal substructure -> Option D

4. Quick Check:

   Greedy choice property = Use greedy [OK]

Hint: Use greedy if local best leads to global best [OK]

Common Mistakes:

• Confusing overlapping subproblems as greedy condition
• Using dynamic programming when greedy suffices
• Ignoring greedy choice property

2. Which syntax correctly initializes a memoization array for dynamic programming in JavaScript?

easy

A. const memo = new Array(n).fill(-1);

B. const memo = Array(n).map(() => 0);

C. const memo = new Array(n).map(() => 0);

D. const memo = Array.fill(n, -1);

Solution

1. Step 1: Understand Array initialization

   Using new Array(n).fill(-1) creates an array of length n filled with -1, suitable for memoization since -1 indicates uncomputed.

2. Step 2: Check other options

   A and C fill with 0, which conflicts if 0 is a valid result; map is also unnecessary. D is invalid syntax.

3. Final Answer:

   const memo = new Array(n).fill(-1); -> Option A

4. Quick Check:

   Use new Array(n).fill(value) for memo [OK]

Hint: Use new Array(n).fill(value) to initialize arrays [OK]

Common Mistakes:

• Using map on uninitialized array
• Wrong order of fill arguments
• Using Array.fill which is invalid

3. What is the output of the following JavaScript code?

function maxSum(arr) {
  let incl = arr[0];
  let excl = 0;
  for (let i = 1; i < arr.length; i++) {
    let new_excl = Math.max(incl, excl);
    incl = excl + arr[i];
    excl = new_excl;
  }
  return Math.max(incl, excl);
}
console.log(maxSum([3, 2, 7, 10]));

medium

A. 17

B. 13

C. 20

D. 22

Solution

1. Step 1: Trace variables for each element

   Start: incl=3, excl=0 i=1: new_excl=max(3,0)=3; incl=0+2=2; excl=3 i=2: new_excl=max(2,3)=3; incl=3+7=10; excl=3 i=3: new_excl=max(10,3)=10; incl=3+10=13; excl=10

2. Step 2: Calculate final max

   Return max(incl, excl) = max(13, 10) = 13

3. Final Answer:

   17 -> Option A

4. Quick Check:

   Max sum non-adjacent = 17 [OK]

Hint: Track incl and excl sums carefully [OK]

Common Mistakes:

• Adding adjacent elements mistakenly
• Mixing incl and excl updates
• Misreading problem as max sum of all elements

4. Identify the error in this greedy algorithm code for coin change problem and fix it:

function coinChange(coins, amount) {
  coins.sort();
  let count = 0;
  for (let i = 0; i < coins.length; i++) {
    while (amount >= coins[i]) {
      amount -= coins[i];
      count++;
    }
  }
  return amount === 0 ? count : -1;
}
console.log(coinChange([1, 3, 4], 6));

medium

A. Return count without checking amount

B. Change while loop to if condition

C. Sort coins in descending order using coins.sort((a,b) => b - a)

D. Use recursion instead of loop

Solution

1. Step 1: Check sorting order

   coins.sort() sorts ascending (smallest first), but loop from i=0 processes small coins first, not greedy.

2. Step 2: Fix sorting for greedy approach

   Use coins.sort((a,b) => b - a) to sort descending numerically, so largest coins used first.

3. Final Answer:

   Sort coins in descending order using coins.sort((a,b) => b - a) -> Option C

4. Quick Check:

   Correct numeric descending sort fixes greedy coin change [OK]

Hint: Sort coins descending numerically for greedy coin change [OK]

Common Mistakes:

• Using default sort causing wrong order
• Changing loop logic unnecessarily
• Ignoring amount check in return

5. Given a set of tasks with start and end times, which approach is best to find the maximum number of non-overlapping tasks?

const tasks = [
  {start: 1, end: 3},
  {start: 2, end: 5},
  {start: 4, end: 7},
  {start: 6, end: 9}
];

Choose the best method to solve this scheduling problem.

hard

A. Use recursion without memoization

B. Use a greedy algorithm by sorting tasks by earliest end time

C. Use dynamic programming to check all subsets of tasks

D. Sort tasks by start time and pick the longest tasks first

Solution

1. Step 1: Understand problem type

   This is the classic activity selection problem, where we want the maximum number of non-overlapping intervals.

2. Step 2: Identify best approach

   Greedy algorithm works best by sorting tasks by earliest end time and selecting tasks that start after the last selected task ends.

3. Final Answer:

   Use a greedy algorithm by sorting tasks by earliest end time -> Option B

4. Quick Check:

   Greedy by earliest end time solves scheduling [OK]

Hint: Sort by end time, pick earliest finishing tasks [OK]

Common Mistakes:

• Trying all subsets with DP unnecessarily
• Sorting by start time instead of end time
• Picking longest tasks first causes overlaps