Greedy vs DP How to Know Which to Apply in DSA Javascript - Visual Comparison

Concept Flow - Greedy vs DP How to Know Which to Apply

Start Problem

↓

Check if problem has optimal substructure?

Yes↓

Check if problem has overlapping subproblems?

Yes No↓

Use DP

↓

Solve

↓

End

Start by checking if the problem can be broken into smaller parts with optimal solutions. If yes, check if these parts overlap. Use DP if overlapping, else Greedy.

Execution Sample

DSA Javascript

function chooseApproach(problem) {
  if (!problem.hasOptimalSubstructure) return 'Neither';
  if (problem.hasOverlappingSubproblems) return 'DP';
  return 'Greedy';
}

This code decides which approach to use based on problem properties.

Execution Table

Step	Check	Condition	Result	Decision
1	Check optimal substructure	problem.hasOptimalSubstructure == true	Yes	Continue
2	Check overlapping subproblems	problem.hasOverlappingSubproblems == true	Yes	Choose DP
3	End	-	-	DP chosen

💡 Decision made based on problem properties: DP chosen because overlapping subproblems exist.

Variable Tracker

Variable	Start	After Step 1	After Step 2	Final
problem.hasOptimalSubstructure	unknown	true	true	true
problem.hasOverlappingSubproblems	unknown	unknown	true	true
decision	none	none	DP	DP

Key Moments - 3 Insights

Why do we check for optimal substructure first?

Because if the problem does not have optimal substructure, neither greedy nor DP will work well. This is shown in Step 1 of the execution_table.

What does overlapping subproblems mean and why does it matter?

Overlapping subproblems mean the problem solves the same smaller problems multiple times. DP stores these results to avoid repetition. This is why in Step 2, if overlapping exists, DP is chosen.

When do we choose greedy over DP?

If the problem has optimal substructure but no overlapping subproblems, greedy is chosen. This is the 'No' branch from Step 2 in the concept_flow.

Visual Quiz - 3 Questions

Look at the execution_table at Step 2, what condition is checked?

A If problem is solvable by brute force

B If problem has overlapping subproblems

C If problem has optimal substructure

D If problem is NP-hard

💡 Hint

Check the 'Check' and 'Condition' columns at Step 2 in execution_table.

According to variable_tracker, what is the final decision after Step 2?

A Greedy

B Neither

C DP

D Unknown

💡 Hint

Look at the 'decision' variable in the 'Final' column of variable_tracker.

If a problem has optimal substructure but no overlapping subproblems, which approach is chosen?

A Greedy

B DP

C Neither

D Brute Force

💡 Hint

Refer to the concept_flow diagram's branch after checking overlapping subproblems.

Concept Snapshot

Greedy vs DP Decision:
1. Check if problem has optimal substructure.
2. If no, neither applies.
3. If yes, check overlapping subproblems.
4. Overlapping? Use DP.
5. No overlapping? Use Greedy.
This helps pick the right approach quickly.

Full Transcript

To decide between Greedy and Dynamic Programming (DP), first check if the problem has optimal substructure, meaning the best solution can be built from best solutions of smaller parts. If it does not, neither approach fits well. If it does, check if the problem has overlapping subproblems, meaning the same smaller problems repeat. If yes, DP is best because it stores results to avoid repeated work. If no, Greedy works by making the best local choice at each step. This decision flow helps choose the right method efficiently.

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