Greedy vs DP How to Know Which to Apply in DSA Typescript - Trade-offs & Analysis

Mental Model

Greedy picks the best choice now, hoping it leads to the best overall. DP tries all choices carefully and remembers results to find the best overall.

Analogy: Imagine choosing snacks from a buffet: greedy is like grabbing the tastiest snack you see first, while DP is like trying small bites of all snacks and remembering which combination tastes best together.

Choices: [1] -> [2] -> [3] -> [4] -> null
Greedy: picks one at a time -> best now
DP: explores all paths -> remembers best

Dry Run Walkthrough

Input: Problem: Choose coins to make 6 cents from coins [1, 3, 4] with minimum coins

Goal: Decide if greedy or DP works better to find minimum coins needed

Step 1: Greedy picks largest coin ≤ 6, picks 4

Chosen: 4 -> Remaining: 2

Why: Greedy tries best immediate choice to reduce amount quickly

Step 2: Greedy picks largest coin ≤ 2, picks 1

Chosen: 4 -> 1 -> Remaining: 1

Why: Greedy continues picking largest coin possible

Step 3: Greedy picks largest coin ≤ 1, picks 1

Chosen: 4 -> 1 -> 1 -> Remaining: 0

Why: Greedy finishes when amount is zero

Step 4: DP tries all combinations and finds 3 + 3 = 6 with 2 coins

Best: 3 -> 3 -> null (2 coins)

Why: DP explores all options and remembers best results

Result:

Greedy picks coins: 4 -> 1 -> 1 -> null (3 coins)
DP picks coins: 3 -> 3 -> null (2 coins)
DP gives better answer here

Annotated Code

DSA Typescript

class CoinChange {
  coins: number[];
  constructor(coins: number[]) {
    this.coins = coins;
  }

  greedyChange(amount: number): number[] {
    const result: number[] = [];
    let remaining = amount;
    this.coins.sort((a, b) => b - a); // largest first
    while (remaining > 0) {
      let coin = this.coins.find(c => c <= remaining);
      if (coin === undefined) break;
      result.push(coin);
      remaining -= coin;
    }
    return result;
  }

  dpChange(amount: number): number[] {
    const dp: number[] = Array(amount + 1).fill(Infinity);
    const backtrack: number[] = Array(amount + 1).fill(-1);
    dp[0] = 0;
    for (let i = 1; i <= amount; i++) {
      for (const coin of this.coins) {
        if (coin <= i && dp[i - coin] + 1 < dp[i]) {
          dp[i] = dp[i - coin] + 1;
          backtrack[i] = coin;
        }
      }
    }
    if (dp[amount] === Infinity) return [];
    const result: number[] = [];
    let curr = amount;
    while (curr > 0) {
      result.push(backtrack[curr]);
      curr -= backtrack[curr];
    }
    return result;
  }
}

const coins = [1, 3, 4];
const amount = 6;
const cc = new CoinChange(coins);
const greedyResult = cc.greedyChange(amount);
const dpResult = cc.dpChange(amount);
console.log('Greedy picks coins:', greedyResult.join(' -> ') + ' -> null');
console.log('DP picks coins:', dpResult.join(' -> ') + ' -> null');

this.coins.sort((a, b) => b - a); // largest first

sort coins descending to pick largest first in greedy

let coin = this.coins.find(c => c <= remaining);

pick largest coin not exceeding remaining amount

dp[0] = 0;

base case: zero coins needed for amount zero

if (coin <= i && dp[i - coin] + 1 < dp[i]) {

update dp if using coin reduces coin count for amount i

result.push(backtrack[curr]); curr -= backtrack[curr];

reconstruct chosen coins from backtrack array

Output

Greedy picks coins: 4 -> 1 -> 1 -> null

DP picks coins: 3 -> 3 -> null

Complexity Analysis

Time: Greedy: O(n log n) due to sorting coins; DP: O(n * amount) because it tries all coins for each amount up to target

Space: Greedy: O(n) for result; DP: O(amount) for dp and backtrack arrays

vs Alternative: Greedy is faster but can fail to find optimal; DP is slower but always finds optimal solution

Edge Cases

Amount zero

Both greedy and DP return empty list (no coins needed)

DSA Typescript

dp[0] = 0;

No coins smaller than amount

Greedy returns partial or empty; DP returns empty indicating no solution

DSA Typescript

if (coin === undefined) break;

Coins with duplicates

Both methods handle duplicates correctly as they consider all coins

DSA Typescript

for (const coin of this.coins) {

When to Use This Pattern

When a problem asks for an optimal choice step-by-step and local best choices always lead to global best, use greedy; if overlapping subproblems and optimal substructure exist but greedy fails, use DP.

Common Mistakes

Mistake: Assuming greedy always gives optimal solution
Fix: Check problem properties; if greedy fails, implement DP to guarantee optimal

Mistake: Not sorting coins descending for greedy approach
Fix: Sort coins descending to pick largest coin first in greedy

Summary

Greedy picks best immediate choice; DP tries all choices and remembers results.

Use greedy when local best choices lead to global best; use DP when problem has overlapping subproblems and greedy fails.

The key is to test if greedy choice property holds; if not, DP is safer.

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