Greedy Pattern

Why this pattern matters for LeetCode

Greedy problems look like they need dynamic programming or backtracking, until you find the local insight that makes them O(n). The challenge is proving that the greedy choice is safe: making the best immediate decision must not ruin better future decisions. Jump Game is the canonical example: instead of trying every path, you track how far you can currently reach. If the current position is within reach, extend the reach. If it's ever out of reach, you're stuck. One variable, one pass, done.

What the Greedy pattern is

A greedy algorithm builds a solution by making the locally optimal choice at each step, without ever going back. It works when the greedy property holds: making the best immediate decision doesn't block a better global outcome. Unlike dynamic programming, which stores and reuses solutions to subproblems, greedy commits to each choice and never reconsiders. The challenge isn't implementation; it's recognizing that the greedy property holds for a specific problem.

Reach for Greedy when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Greedy

• ✓Jump Game, track the max reachable index; return false if any position is out of reach
• ✓Gas Station, greedily reset the start when the running tank goes negative
• ✓Non-overlapping Intervals, sort by end time; keep each interval that starts after the last kept end
• ✓Meeting Rooms, sort by start time; check if any two intervals overlap
• ✓Assign Cookies, sort both arrays; greedily match the smallest sufficient cookie to the smallest child

When NOT to use Greedy

• ✕The optimal choice now creates a worse outcome later, use Dynamic Programming instead
• ✕The problem requires all valid solutions, use Backtracking
• ✕You can construct a counter-example where the greedy choice is suboptimal
• ✕Previous decisions constrain future ones in a non-trivial way. DP handles overlapping subproblems

Better alternative: In those cases, Dynamic Programming handles overlapping-subproblem structure, or Backtracking explores the full solution space.

JavaScript code template

Jump Game. O(n) time, O(1) space

function canJump(nums) {
  let maxReach = 0;

  for (let i = 0; i < nums.length; i++) {
    if (i > maxReach) return false; // can't reach this position

    maxReach = Math.max(maxReach, i + nums[i]); // extend reach from here
  }

  return true;
}

maxReach tracks the farthest index reachable given all positions visited so far. At each index i, if i > maxReach, you're stranded, no combination of jumps from earlier positions can reach here. Otherwise, update maxReach to include jumps available from the current position. If you make it through the loop, every position was reachable.

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Ask: is there a clear 'best choice' at each step that doesn't hurt future steps?
2. 2Sort the input if greedy order isn't already obvious (interval problems almost always need sorting).
3. 3Define what you track: maxReach for Jump Game, running sum for Gas Station, end times for intervals.
4. 4Loop through and apply the greedy decision, no backtracking.
5. 5If a constraint is violated mid-loop, return false early.
6. 6Return the accumulated result after the loop.

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

• Non-Overlapping Intervals

  Sort by end time. Walk through, tracking the end of the last kept interval. When a new interval's start is before that end, remove it (increment count). Otherwise keep it and update the tracked end.

  Premium→
• Jump Game

  Walk left to right tracking farthest reachable index. At each i: if i > farthest, return false. Update farthest = max(farthest, i + nums[i]). Return true if loop completes.

  Premium→
• Jump Game II

  Walk the array tracking farthest reachable position and the end of the current jump's range (curEnd). Each time i reaches curEnd, increment jumps and extend curEnd to farthest.

  Premium→
• Task Scheduler

  Count task frequencies. Find max_freq and how many tasks share it. Formula: max(len(tasks), (max_freq - 1) * (n + 1) + count_of_max_freq).

  Premium→
• Gas Station

  Track total surplus and running tank. If tank goes negative, reset start to next station. If total >= 0, the last reset start is valid.

  Premium→
• Meeting Rooms

  Sort by start. Check each adjacent pair. If next.start < prev.end, return false.

  Premium→
• Meeting Rooms II

  Sort by start. Min-heap of end times. Reuse room if heap[0] <= start; else open new room. Heap size = answer.

  Premium→
• Best Time to Buy and Sell Stock II

  Sum all consecutive positive differences in one pass.

  Premium→

Common mistakes beginners make

• ✕Reaching for dynamic programming when greedy works, if the greedy property holds, DP's extra complexity buys you nothing.
• ✕Not sorting when greedy order matters, interval problems almost always need to be sorted by start or end time before the greedy logic applies.
• ✕Assuming greedy always works, test with a small counter-example. If you find one case where the greedy choice is suboptimal, DP or backtracking is needed.
• ✕Confusing greedy with brute force, brute force tries all options; greedy commits to one option at each step and moves on.

Greedy vs Dynamic Programming vs Backtracking

Choose the right tool for the job.

Time and space complexity

Most greedy algorithms make one pass through the input. O(n). When sorting is required first (interval problems), that adds O(n log n). The greedy decision at each step uses only the current element and a small amount of tracked state, so space is usually O(1). This is the main advantage over DP, which typically needs O(n) or O(n²) space for the memoization table.

Frequently asked questions

How do I know if greedy will work on a problem?

Ask: 'can I construct a counter-example where the greedy choice leads to a worse outcome?' If you can't find one, greedy likely works. The formal proof is an exchange argument, show that swapping any greedy choice for a different one doesn't improve the result. If you can find a counter-example, use dynamic programming.

What's the difference between greedy and dynamic programming?

Greedy makes one decision per step and commits. DP explores all possible decisions and stores the results to avoid recomputation. Greedy is faster (usually O(n)) but only works when the greedy property holds. DP works when previous decisions constrain future ones and you need to compare multiple options at each step.

Why does sorting often come before a greedy algorithm?

Greedy decisions need to be made in the right order. Interval problems sorted by end time let you always pick the interval that ends earliest, which leaves the most room for future intervals. Without sorting, the greedy order isn't well-defined and the algorithm may make wrong choices.

Is Jump Game a greedy or dynamic programming problem?

It can be solved both ways. The greedy solution (track maxReach in one pass) is O(n) time, O(1) space. The DP solution (dp[i] = can you reach index i?) is also O(n) time but O(n) space. Greedy is strictly better here because extending maxReach at each step never hurts future positions, the greedy property holds.