DSA

Part 17 — Greedy Algorithms

A practical, Staff-level interview guide to Greedy Algorithms in Python: local choices, global optimality, exchange arguments, invariants, counterexamples, complexity, and when greedy should—and should not—be used.

Deepak Mishra10 min read

Greedy algorithms are one of the most important algorithmic patterns to recognize in senior and Staff-level coding interviews.

The source defines the greedy approach as making locally optimal choices at each step and never undoing those choices. The key Staff-level question is: Why is the greedy choice globally safe?

1. What Is a Greedy Algorithm?

A greedy algorithm builds a solution incrementally:

Current state
     ↓
Best local choice
     ↓
Updated state
     ↓
Best local choice
     ↓
...
     ↓
Final solution

The important point is that a locally attractive choice is not automatically globally optimal.

2. The Central Greedy Question

Never say:

“Greedy works here.”

Instead ask:

If I make this local choice,
can I prove that an optimal solution
still exists after making it?

The source recommends expressing the proof as an exchange-style argument: replace a different choice in an optimal solution with the greedy choice without making the objective worse.

3. Greedy vs Dynamic Programming

Dynamic Programming
→ systematically compare relevant alternatives

Greedy
→ prove one local choice is safe, then commit

The source places Dynamic Programming and Greedy Algorithms among the advanced algorithmic techniques in the Part/Chapter 15–18 sequence.

4. Why Greedy Algorithms Are Attractive

Greedy solutions are often simple and efficient:

Simple implementation
        +
Low memory usage
        +
Fast execution
        =
Highly practical algorithm

But simplicity does not replace correctness. At Staff level, communicate both the algorithm and why it is valid.

5. Greedy Choice Property

A useful question is:

Can I make the locally best choice without eliminating all optimal solutions?

If yes, greedy may be appropriate. If not, reconsider the approach.

6. Exchange Argument

A standard proof structure is:

Take an arbitrary optimal solution
        ↓
Look at its relevant choice
        ↓
Replace it with the greedy choice
        ↓
Show the solution remains feasible
        ↓
Show the objective does not become worse
        ↓
An optimal solution exists containing the greedy choice

This proves that the greedy choice is safe.

7. Invariants in Greedy Algorithms

The source emphasizes invariants as a valuable interview concept: maintain a property that remains true as the algorithm progresses.

A typical structure is:

After processing the first i elements,
the maintained state represents the best
result achievable under the processed prefix.

State the invariant explicitly instead of merely describing variables.

8. Example — Maximum Stock Profit

The source uses maximum stock profit to illustrate invariant-based reasoning:

min_seen = float("inf")
max_profit = 0

for price in prices:
    max_profit = max(max_profit, price - min_seen)
    min_seen = min(min_seen, price)

The invariant is that after processing index i, min_seen is the minimum price seen through that point. Therefore the best profit ending today is the current price minus the minimum previous price.

The naive pairwise approach is O(n²). Tracking the minimum price produces an O(n) time, O(1) auxiliary-space solution. The source uses this brute-force → bottleneck → observation → optimized progression as a model for interview reasoning.

9. Local vs Global Optimality

Local optimality
→ best-looking decision right now

Global optimality
→ best possible final solution

The first does not imply the second. A proof is required.

10. Counterexamples Are a Greedy Skill

If you propose a greedy rule, try to break it:

Propose rule
   ↓
Try to prove it
   ↓
Try to construct a counterexample
   ↓
If broken → abandon greedy

One valid counterexample is enough to disprove a greedy strategy.

11. Sorting + Greedy

Many greedy algorithms first sort the input:

Unstructured input
       ↓
Sort by the relevant property
       ↓
Greedy scan
       ↓
Commit to safe choices

The source identifies sorting as a fundamental algorithmic pattern and notes that sorting can expose structure in problems such as interval-related problems.

The Staff-level question is:

Why does this ordering make the greedy choice safe?

12. Greedy Complexity

A common structure is:

items.sort(key=...)

for item in items:
    if safe(item):
        choose(item)

Usually:

Sort = O(n log n)
Scan = O(n)
Total = O(n log n)

If the data is already appropriately ordered and only one pass is needed, the algorithm may be O(n).

13. Greedy vs Backtracking

Backtracking
→ explore alternatives
→ undo
→ explore another choice

Greedy
→ prove a choice is safe
→ commit
→ never reconsider

The conceptual difference is whether alternatives are explicitly explored or eliminated through proof.

14. Greedy vs Dynamic Programming — Interview Decision

Ask:

Can I prove one local choice is always safe?
        |
       YES
        ↓
     Greedy

If not, ask whether the problem has overlapping subproblems and needs multiple states:

Overlapping subproblems
        ↓
Dynamic Programming

The source’s pattern map associates repeated subproblems with Dynamic Programming and locally optimal decisions with Greedy.

15. Greedy and Constraints

The source emphasizes:

Pattern
+
Constraints
+
Requirements
=
Algorithm choice

For a greedy solution, ask:

Is sorting affordable?
Must original order be preserved?
Is input streaming?
Do I need the complete solution or only its value?
What are the memory limits?
How large is n?

16. Greedy Correctness Template

During an interview:

  1. Define the greedy choice.
  2. State why it appears attractive.
  3. Claim that it is safe.
  4. Prove safety using an exchange argument or invariant.
  5. Reduce the remaining problem.
  6. Repeat until the solution is complete.

A strong proof sounds like:

“Consider an optimal solution. If it already makes my greedy choice, we are done. Otherwise, I replace its corresponding choice with the greedy choice. The replacement remains feasible and does not worsen the objective. Therefore an optimal solution exists containing my greedy choice.”

17. Testing a Greedy Algorithm

The source recommends concrete examples, including small and extreme inputs.

Test:

empty input
single element
already favorable ordering
reverse ordering
duplicate values
equal choices
minimum values
maximum values
cases where choices are close
cases designed to break the greedy rule

The last category is particularly important.

18. Common Greedy Mistakes

Mistake 1 — “Take the largest”

There is no universal rule that the largest value is the correct greedy choice.

Mistake 2 — Confusing local and global optimum

A local choice requires a correctness argument.

Mistake 3 — No proof

If you cannot explain why the choice is safe, the algorithm is not yet justified.

Mistake 4 — Ignoring counterexamples

Try to break your own greedy rule.

Mistake 5 — Forcing greedy because it is simpler

Simple code is not evidence of correctness.

Mistake 6 — Ignoring constraints

Memory, ordering, streaming, and scale can change the right algorithm.

19. Python Implementation Style

The source recommends using standard Python libraries where they improve clarity, including dict, set, list, deque, heapq, Counter, defaultdict, bisect, and itertools.

For greedy algorithms, this often means:

items = sorted(items, key=...)

followed by a clean scan.

20. Communicating the Algorithm at Staff Level

The source recommends thinking aloud, but communicating decisions rather than narrating every keystroke.

A strong explanation exposes:

Observation
   ↓
Choice
   ↓
Proof
   ↓
Implementation
   ↓
Complexity

Not:

“I create a variable.”
“I type a loop.”
“I add an if statement.”

21. Pattern + Constraints

The source’s Staff-level mental model is:

Pattern
+
Constraints
+
Requirements
=
Algorithm choice

For greedy problems, this means the pattern is only the starting point. The proof and constraints determine whether it is actually the right solution.

22. Brute Force → Greedy

A strong interview progression is:

Brute force
   ↓
Correctness baseline
   ↓
Complexity
   ↓
Identify bottleneck
   ↓
Structural observation
   ↓
Candidate greedy rule
   ↓
Safety proof
   ↓
Greedy solution

This matches the source’s iterative-refinement model.

23. Greedy Decision Checklist

□ What is my local choice?
□ What property makes it attractive?
□ Does the choice preserve feasibility?
□ Can I prove the choice is safe?
□ Can I exchange it into an optimal solution?
□ What invariant does the algorithm maintain?
□ Can I construct a counterexample?
□ What is the remaining subproblem?
□ Is sorting required?
□ What are time and auxiliary-space costs?

If the proof is missing, stop and reconsider.

24. Greedy Complexity Checklist

For a typical sorted greedy algorithm:

Sort:  O(n log n)
Scan:  O(n)
Total: O(n log n)

For a one-pass greedy algorithm:

Time:  O(n)
Space: O(1)

Always verify these against the actual implementation and requirements.

25. Part 16 → Part 17

The transition from Dynamic Programming to Greedy Algorithms is:

Part 16 — Dynamic Programming
        ↓
Multiple relevant states
        ↓
Remember and compare alternatives
        ↓
Part 17 — Greedy Algorithms
        ↓
Can one choice be proven safe?
        ↓
Commit without reconsidering

The conceptual shift is:

DP
→ “I need to remember alternatives.”

Greedy
→ “I can prove alternatives are unnecessary.”

26. Part 17 → Part 18

The source’s advanced sequence continues from Greedy Algorithms into graph-oriented material. It groups Parts/Chapters 15–18 as advanced algorithms.

Part 15 — Recursion
        ↓
Decompose problems

Part 16 — Dynamic Programming
        ↓
Reuse overlapping subproblems

Part 17 — Greedy Algorithms
        ↓
Prove safe local choices

Part 18 — Graphs
        ↓
Model relationships and connectivity

27. Final Greedy Cheat Sheet

Concept Question
Greedy choice What is the best local decision?
Safety Why can I commit to it?
Global optimum Why doesn’t the local choice hurt the final answer?
Exchange argument Can I replace an optimal solution’s choice with mine?
Invariant What remains true after every step?
Counterexample Can I break my rule?
Sorting Does ordering expose the safe choice?
Complexity How much work per candidate?
Space What must be stored?
Constraints Does the strategy fit the input scale?
Alternative Should this actually be DP/search/etc.?

28. The One Question to Remember

When you think a problem is greedy, ask:

Why is this choice globally safe?

Not:

“Why does this choice look good?”

That distinction captures the essence of Staff-level greedy reasoning.

29. Final Takeaway

Greedy algorithms are powerful because they allow us to make decisions without remembering every alternative.

But that power comes from proof, not intuition.

Remember:

Candidate choices
      ↓
Local rule
      ↓
Safety proof
      ↓
Commit
      ↓
Invariant
      ↓
Repeat
      ↓
Optimal solution

The central lesson from the source is simple:

Don’t just say greedy works. Explain why the greedy choice is globally safe.

Source Note

This article is based on the available uploaded interview-preparation material derived from Elements of Programming Interviews in Python. The available source explicitly provides the Greedy Algorithms definition, the globally-safe-choice requirement, invariant-based reasoning, pattern recognition, complexity expectations, and the Part/Chapter 15–18 advanced-algorithm progression.

The available extracted source does not expose a complete numbered problem-by-problem listing for the original book’s Chapter 17. Therefore, this article preserves the supported Greedy Algorithms framework rather than inventing missing source-specific problem content.