Greedy Algorithm Interview Pattern: How to Tell When Greedy Works

Greedy Algorithm Interview Pattern: How to Tell When Greedy Works

Greedy algorithms are seductive in interviews. The idea is simple: at each step, make the choice that looks best right now and never look back. When greedy works, it produces short, fast solutions. When it doesn't, it produces confident, wrong answers.

This guide covers the greedy algorithm interview pattern: how to recognize it, how to check whether your greedy choice is safe, the classic templates, and how to justify your approach so the interviewer trusts it.

What makes a problem greedy

A greedy approach is correct when two things are true:

  1. Greedy choice property: some locally optimal choice is part of at least one globally optimal solution.
  2. Optimal substructure: after making that choice, the remaining problem is a smaller version of the same problem.

You don't need to say these terms in an interview, but you should be able to explain the idea in plain words: "Choosing this option first never makes the final answer worse."

Signals in the prompt

Greedy is worth considering when you see:

Signals that greedy is risky: the prompt asks for the number of ways, the best value across many overlapping sub-choices, or anything where an early choice can block a better later one. Those usually point to dynamic programming.

Test your greedy choice before coding

The most useful habit: try to break your greedy rule with a small counterexample before you write code.

Take coin change with coins [1, 3, 4] and target 6. "Always take the largest coin" gives 4 + 1 + 1 (three coins), but 3 + 3 uses two. Greedy fails, so this is a DP problem.

Say this process out loud: "My greedy rule is to take the largest coin. Let me try a small case to see if it breaks... it does, so I'll use DP." That's a strong signal even though you discarded the idea.

If you try two or three tricky cases and the rule holds, explain why it holds, then code it.

Template 1: interval scheduling

Problem: select the maximum number of non-overlapping intervals.

Greedy rule: sort by end time, then repeatedly pick the interval that finishes earliest and doesn't overlap the last one picked.

def max_non_overlapping(intervals):
    intervals.sort(key=lambda x: x[1])
    count, last_end = 0, float("-inf")
    for start, end in intervals:
        if start >= last_end:
            count += 1
            last_end = end
    return count

Why it works: the interval that ends first leaves the most room for everything else. Any optimal solution can swap its first interval for the earliest-ending one without losing anything. That's the "exchange argument," and a one-sentence version of it is usually enough in an interview.

Sorting by start time or by length is a common trap. Try a counterexample with one long interval that starts early and covers several short ones.

Template 2: reach and jump problems

Problem: can you reach the last index if each value is the maximum jump length?

Greedy rule: track the farthest index reachable so far. If the current index ever exceeds it, you're stuck.

def can_reach_end(nums):
    farthest = 0
    for i, jump in enumerate(nums):
        if i > farthest:
            return False
        farthest = max(farthest, i + jump)
    return True

The minimum-jumps variant extends this by counting how many times you have to "commit" to a new window of reachable indices.

Template 3: sort and match

Problem: assign items to people so the most people are satisfied (for example, cookies to children by size).

Greedy rule: sort both lists, then use two pointers to match the smallest sufficient item to each person in order.

The justification: using a bigger item than necessary can only hurt later matches.

Template 4: running balance

Problem: gas stations in a circle; find a starting station that lets you complete the loop.

Greedy rule: if the total gas is less than total cost, no answer exists. Otherwise, track the running balance; whenever it drops below zero, the next station becomes the new candidate start.

This one benefits from a clear explanation: "If I can't get from A to B, then no station between A and B can be the start either, because I'd arrive there with at least as much fuel as starting fresh."

How to justify greedy in an interview

Interviewers often ask "how do you know this is correct?" Have a short structure ready:

  1. State the rule: "I always pick the interval that ends earliest."
  2. Give the intuition: "It leaves the most room for the rest."
  3. Sketch the exchange: "Any optimal answer could swap its first pick for mine without getting worse."
  4. Mention a failed alternative: "Sorting by start time breaks on this case."

That's thirty seconds, and it turns a hunch into a reasoned argument.

Complexity

Most greedy solutions are dominated by sorting: O(n log n) time. The greedy pass itself is usually O(n). Space is often O(1) beyond the sort, or O(n) if sorting creates a copy. State both.

Common mistakes

Practice the reasoning, not just the templates

Greedy problems reward the habit of proposing, testing, and justifying. Rehearse that loop out loud with a timer: state the rule, try to break it, then explain why it holds. Luna Interview gives you a structured place to practice that kind of spoken reasoning and stay calm when an interviewer challenges your approach.

Quick checklist

Greedy is less about being clever and more about being careful. Test the shortcut before you trust it.