Greedy vs DP How to Know Which to Apply in DSA Javascript - Key Differences

Recall & Review

beginner

What is the main idea behind the greedy algorithm?

A greedy algorithm makes the best choice at each step, hoping to find the overall best solution without reconsidering previous choices.

beginner

What does Dynamic Programming (DP) do differently from greedy algorithms?

DP solves problems by breaking them into smaller overlapping subproblems, solving each once, and storing results to avoid repeated work.

intermediate

When should you choose a greedy algorithm over DP?

Choose greedy when the problem has the 'greedy choice property' and 'optimal substructure', meaning local best choices lead to a global best solution.

intermediate

What is 'optimal substructure' in the context of DP and greedy algorithms?

Optimal substructure means the best solution to a problem can be built from the best solutions of its smaller parts.

advanced

How can you test if a greedy algorithm will work for a problem?

Try to prove or check if making the best local choice at each step always leads to the global best solution. If not, DP might be needed.

Which property must a problem have for a greedy algorithm to work correctly?

A Greedy choice property

B Overlapping subproblems

C Memoization

D Backtracking

The greedy choice property means local optimal choices lead to a global optimum, which is essential for greedy algorithms.

What does Dynamic Programming use to avoid repeated work?

A Greedy choices

B Random guessing

C Memoization or tabulation

D Divide and conquer without storing results

DP stores results of subproblems using memoization or tabulation to avoid solving the same problem multiple times.

If a problem has overlapping subproblems but no greedy choice property, which approach is better?

A Greedy algorithm

B Divide and conquer without memoization

C Brute force

D Dynamic Programming

DP is suitable when subproblems overlap and greedy choices do not guarantee an optimal solution.

Which of these is an example of a problem typically solved by a greedy algorithm?

A Coin change with unlimited coins

B Activity selection problem

C Shortest path in a graph with negative edges

D Fibonacci sequence

The activity selection problem can be solved optimally by choosing the earliest finishing activity greedily.

What is a sign that a problem might require Dynamic Programming?

A Subproblems overlap and optimal substructure exists

B Greedy choice property holds

C No overlapping subproblems

D Problem size is very small

DP is useful when subproblems overlap and the problem has optimal substructure.

Explain how to decide between using a greedy algorithm or dynamic programming for a problem.

Think about problem properties and how solutions build from smaller parts.

Describe the difference between greedy algorithms and dynamic programming in simple terms.

Focus on how each method approaches problem solving.

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