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

Challenge - 5 Problems

🧠 Conceptual

intermediate

When to Choose Greedy Over Dynamic Programming?

Which of the following problem characteristics best suggests using a greedy algorithm instead of dynamic programming?

A The problem has a greedy-choice property where local optimal choices lead to a global optimum.

B The problem requires exploring all possible combinations to find the best solution.

C The problem has overlapping subproblems and optimal substructure.

D The problem's solution depends on previous computations stored in a table.

💡 Hint

Think about when making the best choice at each step guarantees the best overall solution.

Greedy algorithms work well when the problem has the greedy-choice property, meaning local optimal choices lead to a global optimum. Dynamic programming is needed when overlapping subproblems require storing previous results.

❓ Predict Output

intermediate

Output of Greedy Coin Change Algorithm

What is the output of the following TypeScript code that uses a greedy approach to make change?

DSA Typescript

function greedyCoinChange(coins: number[], amount: number): number[] {
  coins.sort((a, b) => b - a);
  const result: number[] = [];
  for (const coin of coins) {
    while (amount >= coin) {
      amount -= coin;
      result.push(coin);
    }
  }
  return result;
}

console.log(greedyCoinChange([25, 10, 5, 1], 37));

A [25, 10, 1, 1, 1]

B [25, 10, 5, 1, 1]

C [25, 10, 1, 1]

D [25, 10, 5, 1]

💡 Hint

Trace how the amount decreases with each coin chosen.

The greedy algorithm picks the largest coin first. 25 fits once (37-25=12), then 10 fits once (12-10=2), then 1 fits twice (2-1-1=0). So the coins are [25, 10, 1, 1].

❓ Predict Output

advanced

Dynamic Programming for Fibonacci Sequence

What is the output of this TypeScript code that uses dynamic programming to compute Fibonacci numbers?

DSA Typescript

function fibDP(n: number): number {
  const dp: number[] = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

console.log(fibDP(7));

A 21

B 13

C 8

D 34

💡 Hint

Recall the Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21...

dp[0]=0, dp[1]=1, dp[2]=1, dp[3]=2, dp[4]=3, dp[5]=5, dp[6]=8, dp[7]=13. The 7th Fibonacci number (0-indexed) is 13.

🔧 Debug

advanced

Identify the Error in Greedy Interval Scheduling

What error will this TypeScript code produce when trying to find the maximum number of non-overlapping intervals using a greedy approach?

DSA Typescript

function maxIntervals(intervals: [number, number][]): number {
  intervals.sort((a, b) => a[0] - b[0]);
  let count = 0;
  let end = -Infinity;
  for (const [start, finish] of intervals) {
    if (start >= end) {
      count++;
      end = finish;
    }
  }
  return count;
}

console.log(maxIntervals([[1,4], [2,3], [3,5]]));

A Returns 2 (correct maximum intervals)

B Returns 3 (incorrect, counts overlapping intervals)

C Returns 1 (incorrect, undercounts intervals)

D Throws a runtime error due to sorting

💡 Hint

Check how intervals are sorted and how the greedy choice is made.

The code sorts intervals by start time, but the greedy algorithm for interval scheduling requires sorting by finish time. Sorting by start time causes undercounting, so it returns 1 instead of 2.

🚀 Application

expert

Choosing Between Greedy and DP for Weighted Interval Scheduling

You have a list of intervals each with a start time, end time, and weight. You want to select non-overlapping intervals to maximize total weight. Which approach is best and why?

A Use a greedy algorithm by sorting intervals by start time and picking the earliest starting intervals.

B Use a greedy algorithm by always picking the interval with the highest weight first.

C Use a brute force approach to check all combinations because greedy and DP do not apply.

D Use dynamic programming because the problem has overlapping subproblems and requires considering previous optimal solutions.

💡 Hint

Think about whether local choices guarantee a global optimum in weighted interval scheduling.

Weighted interval scheduling requires dynamic programming because the greedy-choice property does not hold. You must consider previous optimal solutions to maximize total weight.