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.

Practice

1. Which of the following best describes when to use a greedy algorithm instead of dynamic programming?

easy

A. When the problem has the greedy choice property and optimal substructure

B. When the problem requires checking all possible combinations

C. When the problem has overlapping subproblems but no optimal substructure

D. When the problem needs to store all intermediate results

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.

2. Step 2: Check optimal substructure

   Optimal substructure means the optimal solution can be built from optimal solutions of subproblems.

3. Final Answer:

   When the problem has the greedy choice property and optimal substructure -> Option A

4. Quick Check:

   Greedy = greedy choice + optimal substructure [OK]

Hint: Use greedy if local best leads to global best [OK]

Common Mistakes:

• Confusing overlapping subproblems with greedy applicability
• Using greedy when problem needs full exploration
• Ignoring optimal substructure requirement

2. Which syntax correctly declares a memoization object in TypeScript for dynamic programming?

easy

A. var memo: number[] = [];

B. let memo = new Map();

C. const memo: Record = {};

D. const memo = {} as number[];

Solution

1. Step 1: Understand memo type for DP

   Memoization stores results with keys, so Record is suitable.

2. Step 2: Check syntax correctness

   const memo: Record = {}; correctly declares an empty object with number keys and values.

3. Final Answer:

   const memo: Record = {}; -> Option C

4. Quick Check:

   Memo object uses Record type [OK]

Hint: Use Record for memo objects [OK]

Common Mistakes:

• Using var instead of const or let
• Incorrect type assertion for memo
• Using Map without type parameters

3. Consider this TypeScript code snippet for a problem that can be solved by greedy or DP:

function maxSum(arr: number[]): number {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > 0) sum += arr[i];
  }
  return sum;
}
console.log(maxSum([-1, 2, 3, -5, 4]));

What is the output?

medium

A. 9

B. 4

C. 0

D. Error

Solution

1. Step 1: Trace the loop and sum positive numbers

   Positive numbers are 2, 3, and 4. Sum = 2 + 3 + 4 = 9.

2. Step 2: Confirm return value

   The function returns sum = 9, so console.log prints 9.

3. Final Answer:

   9 -> Option A

4. Quick Check:

   Sum positives = 9 [OK]

Hint: Sum only positive numbers for max sum greedy [OK]

Common Mistakes:

• Adding negative numbers mistakenly
• Returning zero instead of sum
• Confusing output with array length

4. The following TypeScript function is intended to solve the Fibonacci sequence using DP with memoization. What is the bug?

function fib(n: number, memo: Record = {}): number {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}
console.log(fib(5));

medium

A. The recursive calls should be fib(n + 1) and fib(n + 2)

B. The base case should be 'if (n < 0) return 0;'

C. The function should not use default parameter for memo

D. The memo check should be 'if (memo[n] !== undefined)' to handle zero

Solution

1. Step 1: Analyze memo check condition

   Checking 'if (memo[n])' fails when memo[n] is 0, which is falsy.

2. Step 2: Correct memo check

   Use 'if (memo[n] !== undefined)' to correctly detect stored values including zero.

3. Final Answer:

   The memo check should be 'if (memo[n] !== undefined)' to handle zero -> Option D

4. Quick Check:

   Memo check must handle zero values [OK]

Hint: Check memo with !== undefined, not truthy check [OK]

Common Mistakes:

• Using truthy check for memo causing wrong cache hits
• Wrong base case for Fibonacci
• Incorrect recursive call directions

5. You have a set of tasks with durations and deadlines. You want to maximize the number of tasks completed before their deadlines. Which approach is best and why?

interface Task {
  duration: number;
  deadline: number;
}
function scheduleTasks(tasks: Task[]): number {
  // Implementation needed
}

hard

A. Use dynamic programming to try all subsets and pick max count

B. Use a greedy algorithm sorting tasks by earliest deadline to maximize count

C. Use greedy sorting by longest duration first to minimize total time

D. Use dynamic programming to minimize total duration ignoring deadlines

Solution

1. Step 1: Understand problem goal

   Maximize number of tasks completed before deadlines means scheduling tasks efficiently.

2. Step 2: Identify best approach

   Greedy algorithm sorting by earliest deadline ensures maximum tasks fit before deadlines.

3. Final Answer:

   Use a greedy algorithm sorting tasks by earliest deadline to maximize count -> Option B

4. Quick Check:

   Earliest deadline first greedy maximizes tasks [OK]

Hint: Sort tasks by earliest deadline for max count [OK]

Common Mistakes:

• Trying all subsets with DP causing inefficiency
• Sorting by longest duration wastes time
• Ignoring deadlines in scheduling