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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if a problem can be solved greedily by verifying if the problem has the greedy-choice property.

DSA Javascript

function canUseGreedy(problem) {
  // Greedy works if local optimum leads to global optimum
  return problem.hasGreedyChoiceProperty === [1];
}

Drag options to blanks, or click blank then click option'

Afalse

Btrue

Cnull

Dundefined

Attempts:

3 left

💡 Hint

Common Mistakes

Choosing false or undefined instead of true.

The greedy-choice property means choosing the best local option leads to the global best solution, so it must be true.

2fill in blank

medium

Complete the code to check if a problem has overlapping subproblems, a key property for dynamic programming.

DSA Javascript

function canUseDP(problem) {
  // DP works if subproblems repeat
  return problem.hasOverlappingSubproblems === [1];
}

Drag options to blanks, or click blank then click option'

Afalse

Bnull

Ctrue

Dundefined

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing overlapping subproblems with greedy-choice property.

Dynamic programming requires overlapping subproblems to reuse solutions and avoid repeated work.

3fill in blank

hard

Fix the error in the function that decides which approach to use based on problem properties.

DSA Javascript

function chooseApproach(problem) {
  if (problem.hasGreedyChoiceProperty === [1] && problem.hasOverlappingSubproblems === false) {
    return 'Greedy';
  } else if (problem.hasOverlappingSubproblems === true) {
    return 'DP';
  } else {
    return 'Brute Force';
  }
}

Drag options to blanks, or click blank then click option'

Atrue

Bfalse

Cnull

Dundefined

Attempts:

3 left

💡 Hint

Common Mistakes

Using false instead of true for greedy-choice property.

The greedy approach applies when the greedy-choice property is true and overlapping subproblems is false.

4fill in blank

hard

Fill both blanks to complete the function that explains why greedy or DP is chosen.

DSA Javascript

function explainChoice(problem) {
  if (problem.hasGreedyChoiceProperty === [1]) {
    return 'Use greedy because it has the greedy-choice property.';
  } else if (problem.hasOverlappingSubproblems === [2]) {
    return 'Use DP because it has overlapping subproblems.';
  } else {
    return 'Use brute force as no special properties found.';
  }
}

Drag options to blanks, or click blank then click option'

Atrue

Bfalse

Cnull

Dundefined

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing true and false values in conditions.

Greedy is chosen if greedy-choice property is true; DP if overlapping subproblems is true.

5fill in blank

hard

Fill all three blanks to complete the function that returns the recommended approach based on problem properties.

DSA Javascript

function recommendApproach(problem) {
  if (problem.hasGreedyChoiceProperty === [1] && problem.hasOverlappingSubproblems === [2]) {
    return [3];
  } else if (problem.hasGreedyChoiceProperty === true) {
    return 'Greedy';
  } else if (problem.hasOverlappingSubproblems === true) {
    return 'DP';
  } else {
    return 'Brute Force';
  }
}

Drag options to blanks, or click blank then click option'

Atrue

Bfalse

C'DP'

D'Brute Force'

Attempts:

3 left

💡 Hint

Common Mistakes

Returning 'DP' or 'Greedy' when both properties are false.

If neither greedy-choice property nor overlapping subproblems is true, recommend brute force.

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