Greedy vs DP How to Know Which to Apply in DSA Javascript - Compare & Choose

Challenge - 5 Problems

🧠 Conceptual

intermediate

When to Choose Greedy Over Dynamic Programming?

You have a problem where you need to find the minimum number of coins to make a certain amount. The coin denominations are unlimited and sorted. Which condition best suggests that a greedy approach will work correctly instead of dynamic programming?

A The coin denominations are multiples of each other, like 1, 5, 10, 25.

B The problem requires checking all combinations of coins to find the minimum.

C The problem has overlapping subproblems and optimal substructure.

D The coin denominations are random and not related to each other.

💡 Hint

Think about when picking the largest coin first always leads to the best solution.

Greedy works when local choices lead to a global optimum. If coin denominations are multiples, picking the largest coin first always works. Otherwise, dynamic programming is needed.

❓ Predict Output

intermediate

Output of Greedy vs DP Coin Change

What is the output of the following JavaScript code that tries to find the minimum coins for amount 11 using greedy and DP?

DSA Javascript

const coins = [1, 5, 7];
const amount = 11;

function greedyCoinChange(coins, amount) {
  let count = 0;
  let remaining = amount;
  for (let i = coins.length - 1; i >= 0; i--) {
    while (coins[i] <= remaining) {
      remaining -= coins[i];
      count++;
    }
  }
  return count;
}

function dpCoinChange(coins, amount) {
  const dp = Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  return dp[amount];
}

console.log({ greedy: greedyCoinChange(coins, amount), dp: dpCoinChange(coins, amount) });

A {"greedy": 3, "dp": 3}

B {"greedy": 5, "dp": 3}

C {"greedy": 4, "dp": 4}

D {"greedy": 6, "dp": 3}

💡 Hint

Trace the greedy approach: it picks largest coins first until it can't, then smaller coins.

The greedy picks coins: 7 + 1 + 1 + 1 + 1 = 5 coins total. DP finds the optimal 5 + 5 + 1 = 3 coins total. So greedy is not optimal here.

🧠 Conceptual

advanced

Key Property to Use Dynamic Programming

Which property is essential for a problem to be solved efficiently by dynamic programming?

A The problem has overlapping subproblems and optimal substructure.

B The problem can be solved by brute force without optimization.

C The problem can be solved by making a single greedy choice at each step.

D The problem requires sorting the input before processing.

💡 Hint

Think about reusing solutions to smaller parts of the problem.

Dynamic programming works when the problem can be broken into smaller overlapping subproblems and the optimal solution can be built from optimal solutions of subproblems.

❓ Predict Output

advanced

Output of Interval Scheduling Problem

Given intervals, what is the output of the greedy algorithm that selects intervals with earliest finish time?

DSA Javascript

const intervals = [
  { start: 1, end: 4 },
  { start: 3, end: 5 },
  { start: 0, end: 6 },
  { start: 5, end: 7 },
  { start: 8, end: 9 },
  { start: 5, end: 9 }
];

function intervalScheduling(intervals) {
  intervals.sort((a, b) => a.end - b.end);
  const result = [];
  let lastEnd = -Infinity;
  for (const interval of intervals) {
    if (interval.start >= lastEnd) {
      result.push(interval);
      lastEnd = interval.end;
    }
  }
  return result;
}

const selected = intervalScheduling(intervals);
console.log(selected.map(i => `[${i.start},${i.end}]`).join(' -> '));

A [0,6] -> [8,9]

B [1,4] -> [3,5] -> [5,7] -> [8,9]

C [1,4] -> [5,7] -> [8,9]

D [3,5] -> [5,9]

💡 Hint

Sort intervals by end time and pick non-overlapping ones.

The greedy picks intervals ending earliest without overlap: [1,4], then [5,7], then [8,9].

🧠 Conceptual

expert

Why Greedy Fails and DP Succeeds in Some Problems

Why does a greedy algorithm fail to find the optimal solution in some problems where dynamic programming succeeds?

A Dynamic programming ignores overlapping subproblems, making it faster than greedy.

B Greedy algorithms always try all possible solutions, causing inefficiency.

C Dynamic programming uses random choices to find better solutions than greedy.

D Greedy algorithms do not consider future consequences of current choices, missing global optimum.

💡 Hint

Think about how greedy picks locally best choices without looking ahead.

Greedy algorithms make the best local choice at each step but may miss better overall solutions that require considering future steps. Dynamic programming considers all subproblems and builds the global optimum.

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