Skip to main content

Pattern · 15 problems

Greedy Algorithm Interview Problems

Greedy takes the best choice now and never looks back. It works only when I can say why the choice never hurts.

Get the link for your laptop

Free: write the code and run it, no sign-up.

When I reach for it

  • A locally best choice looks safe.
  • You sort first, then sweep once.
  • You are scheduling, covering or merging.

Problems, easiest first

2 easy · 13 medium · 0 hard. Open one to read it, then write it in the free editor.

  1. Meeting RoomseasyIntervalsHeaps
  2. Longest Palindrome LengtheasyStringsArrays & Hashing
  3. Jump GamemediumDynamic ProgrammingArrays & Hashing
  4. Meeting Rooms IImediumIntervalsHeaps
  5. Non-overlapping IntervalsmediumIntervalsDynamic Programming
  6. Container With Most WatermediumTwo PointersArrays & Hashing
  7. Gas StationmediumArrays & Hashing
  8. Hand of StraightsmediumArrays & Hashing
  9. Jump Game IImediumDynamic ProgrammingArrays & Hashing
  10. Merge Triplets to Form Target TripletmediumArrays & Hashing
  11. Min Cost to Connect All PointsmediumHeapsGraphs
  12. Partition LabelsmediumTwo PointersStrings
  13. Task SchedulermediumHeapsArrays & Hashing
  14. Valid Parenthesis StringmediumStackDynamic Programming
  15. Minimum Number of People to TeachmediumArrays & Hashing

The idea

Make the best choice now and never revisit it. That only works if you can explain why no later choice makes you regret it.

Sort by the right key first. Many greedy solutions are a sort plus a single pass. The key is the whole idea.

farthest = 0
for i, jump in enumerate(nums):
    if i > farthest:
        return False                      # stuck: index i is out of reach
    farthest = max(farthest, i + jump)    # best reach so far
return True
Can you reach the last index? Track the farthest spot you can reach, and fail the moment you fall behind it. Python shown; the idea carries to every language in the editor.

Where it goes wrong

  • Trusting a greedy rule with no argument for why it holds.
  • Sorting by the wrong key.
  • Skipping the counterexample. Try a tiny input that could break the rule.

Say this before you type. Say the greedy choice, then say why swapping it for another choice cannot do better.

Where Coco comes in

Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.

Questions people ask

How do I show a greedy choice is safe?
Show that any better answer can swap in your choice without getting worse. Say that swap out loud.
When does greedy fail?
Coins of 1, 3 and 4 make 6 with three coins greedily: 4, 1, 1. Two coins of 3 do better. That is a dynamic programming problem.

Meet these next

Fin and Coco are characters, not people. strongyes.io is independent. Leo builds it with AI agents.