# How to Identify and Validate Greedy Algorithms: A Complete Guide

> Master identifying and validating greedy algorithms. Learn to make locally optimal choices for global solutions with this complete guide. Perfect for LeetCode challenges.

- Repository: [lucifer/leetcode](https://github.com/azl397985856/leetcode)
- Tags: tutorial
- Published: 2026-03-06

---

**A greedy algorithm solves problems by making locally optimal choices at each step without backtracking, and you can validate one by verifying the no-after-effect property, proving local optimality leads to global optimality through exchange arguments, and implementing a linear-time solution that extends coverage boundaries.**

Greedy algorithms are among the most elegant solutions in competitive programming and software engineering, yet identifying when they apply requires rigorous validation. This guide draws from the comprehensive greedy algorithm implementations in the `azl397985856/leetcode` repository to provide a systematic framework for recognizing greedy-eligible problems and proving their correctness.

## What Makes a Problem Suitable for Greedy Algorithms?

Before writing code, you must determine whether the problem structure permits a greedy approach. According to the repository’s core thinking notes in [`thinkings/greedy.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/greedy.md), two architectural properties define greedy-compatible problems.

### The No-After-Effect Property (无后效性)

A state must depend only on the current position, not on the path taken to reach it. The repository describes this as **无后效性** (no-after-effect). If a decision at step `i` requires knowledge of how you arrived at `i`, dynamic programming is required instead. In greedy algorithms, you only track the current boundary or metric, discarding historical choices.

### Problem Classification: Coverage and Extreme-Value Problems

The repository groups greedy solutions under **覆盖问题** (coverage problems). These typically involve:
- **Interval coverage**: Selecting minimum intervals to cover a line segment
- **Jump games**: Reaching the end of an array with minimum steps
- **Resource allocation**: Assigning cookies or scheduling tasks with local optimality

If your problem asks for an extreme value (minimum, maximum, or coverage) and exhibits the no-after-effect property, it is a candidate for the greedy paradigm.

## The 7-Step Validation Process for Greedy Algorithms

To prove that a greedy solution is correct, follow this validation pipeline derived from the repository’s methodology in [`thinkings/greedy.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/greedy.md).

### Step 1: Verify the Problem Class

Confirm the problem involves coverage, interval selection, or extreme-value optimization. Check if similar problems in the repository (like Jump Game II or Video Stitching) share the same structural pattern.

### Step 2: Confirm the No-After-Effect Property

Test whether the optimal choice at position `i` depends only on `i` and the current state metric (like `furthest` reachable index), not on previous decisions. If you can describe the state with a single variable or boundary, the property holds.

### Step 3: Prove Local Optimality Leads to Global Optimality

Use **exchange arguments** or mathematical induction:
- Show that any optimal solution can be transformed into the greedy solution step-by-step without worsening the result
- Prove by induction that after `k` greedy choices, there exists an optimal solution that matches those choices

The repository notes this is the most difficult step, requiring rigorous proof in the **总结** (summary) section of the greedy note.

### Step 4: Formulate the Greedy Rule

Define a metric that can be updated in **O(1)** time. Common patterns from the repository include:
- **Furthest reachable index**: For jump problems, track the maximum index reachable from the current window
- **Rightmost covered point**: For interval problems, pick the interval extending the current boundary the farthest

### Step 5: Implement the Linear Scan

Write a single pass algorithm that updates the metric while scanning the input. The repository provides three canonical implementations demonstrating this pattern.

### Step 6: Validate Complexity

Greedy solutions should achieve **O(N)** time complexity and **O(1)** or **O(N)** auxiliary space. The repository’s “复杂度分析” (complexity analysis) sections confirm these bounds for Jump Game II, Video Stitching, and Minimum Taps.

### Step 7: Analyze Edge Cases

- Verify the problem guarantees feasibility (e.g., “you can always reach the end”)
- Add explicit checks for impossible cases, returning `-1` when the greedy scan cannot extend the boundary

## Canonical Implementation Patterns from the LeetCode Repository

The `azl397985856/leetcode` repository provides three reference implementations in [`thinkings/greedy.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/greedy.md) that demonstrate the greedy skeleton for coverage problems.

### Pattern 1: Boundary Extension (Jump Game II)

The `jump()` method in **Jump Game II** maintains two pointers: `end` marks the current reachable boundary, and `furthest` tracks the maximum index reachable from the current window. When the scan reaches `end`, it extends the boundary to `furthest` and increments the jump count.

```python
class Solution:
    def jump(self, nums: List[int]) -> int:
        n, cnt, furthest, end = len(nums), 0, 0, 0
        for i in range(n - 1):               # scan all but the last index

            furthest = max(furthest, nums[i] + i)   # farthest we can reach now

            if i == end:                     # reached the current boundary

                cnt += 1                     # need one more jump

                end = furthest               # extend boundary greedily

        return cnt

```

*Source*: [`thinkings/greedy.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/greedy.md) → [Jump Game II](https://github.com/azl397985856/leetcode/blob/master/thinkings/greedy.md#45-跳跃游戏-ii)

### Pattern 2: Preprocessing Furthest Reach (Video Stitching)

**Video Stitching** preprocesses the input to create a `furthest` array where each index `i` stores the rightmost point reachable from position `i`. The greedy scan then extends the boundary using this precomputed metric, returning `-1` if the boundary cannot advance.

```python
class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        furthest = [0] * T
        for s, e in clips:
            for i in range(s, min(e, T - 1) + 1):
                furthest[i] = max(furthest[i], e)

        end = last = ans = 0
        for i in range(T):
            last = max(last, furthest[i])
            if last == i:            # cannot extend further → impossible

                return -1
            if i == end:
                ans += 1
                end = last
        return ans

```

*Source*: [`thinkings/greedy.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/greedy.md) → [Video Stitching](https://github.com/azl397985856/leetcode/blob/master/thinkings/greedy.md#1024-视频拼接)

### Pattern 3: Interval Coverage with Validation (Minimum Number of Taps)

**Minimum Number of Taps** converts tap ranges into interval coverage, building a `furthest` map from each position to the rightmost coverage point. The greedy scan validates feasibility by checking for uncovered segments (returning `-1`) while counting the minimum taps needed to cover the garden.

```python
class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        furthest = [0] * n
        for i in range(n + 1):
            left, right = max(0, i - ranges[i]), min(n, i + ranges[i])
            for pos in range(left, right):
                furthest[pos] = max(furthest[pos], right)

        end = last = ans = 0
        for i in range(n):
            if furthest[i] == 0:      # uncovered segment → impossible

                return -1
            last = max(last, furthest[i])
            if i == end:
                ans += 1
                end = last
        return ans

```

*Source*: [`thinkings/greedy.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/greedy.md) → [Minimum Taps](https://github.com/azl397985856/leetcode/blob/master/thinkings/greedy.md#1326-灌溉花园的最少水龙头数目)

## Key Source Files in the Repository

Understanding the greedy paradigm requires studying both the theoretical framework and concrete implementations. The `azl397985856/leetcode` repository organizes this knowledge across the following critical files:

| File | Significance |
|------|--------------|
| [`thinkings/greedy.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/greedy.md) | Core conceptual article defining greedy strategy, the **无后效性** (no-after-effect) property, and containing the reference implementations for Jump Game II, Video Stitching, and Minimum Taps. |
| [`thinkings/greedy.en.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/greedy.en.md) | English translation of the greedy thinking notes, providing the same architectural guidance for international contributors. |
| [`problems/45.jump-game.md`](https://github.com/azl397985856/leetcode/blob/main/problems/45.jump-game.md) | Problem-specific deep dive connecting Jump Game II to the greedy paradigm with complexity analysis. |
| [`problems/455.AssignCookies.md`](https://github.com/azl397985856/leetcode/blob/main/problems/455.AssignCookies.md) | Concrete example of a simple greedy problem (Assign Cookies) demonstrating local optimal choice validation. |
| [`README.en.md`](https://github.com/azl397985856/leetcode/blob/main/README.en.md) (section *Basic skills*) | High-level inventory categorizing Greedy algorithms alongside Dynamic Programming and Divide & Conquer. |

These files collectively provide the theoretical foundation, canonical code patterns, and problem-specific context needed to **identify** greedy-eligible problems and **validate** that your implementation follows the greedy paradigm correctly.

## Summary

To identify and validate greedy algorithms effectively, remember these core principles derived from the `azl397985856/leetcode` repository:

- **Verify the no-after-effect property** (无后效性) to ensure decisions depend only on the current state, not the path taken.
- **Classify the problem** as a coverage, interval, or extreme-value problem before applying greedy logic.
- **Prove correctness** using exchange arguments or induction to show local optimal choices lead to global optimality.
- **Implement the boundary extension pattern** using `furthest` reach metrics and linear scans, achieving O(N) time complexity.
- **Validate edge cases** explicitly, returning failure indicators (like `-1`) when the greedy scan cannot cover the required range.

## Frequently Asked Questions

### How do I distinguish between a greedy algorithm and dynamic programming?

**Greedy algorithms** require the **no-after-effect property** (无后效性), meaning the optimal choice at each step depends only on the current state metric (like the furthest reachable index), not on how you arrived there. **Dynamic programming** is necessary when future decisions depend on the specific sequence of previous choices, creating overlapping subproblems that require memoization. According to [`thinkings/greedy.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/greedy.md), if you can describe the state with a single boundary variable that updates in O(1) time, use greedy; otherwise, use dynamic programming.

### What is the "exchange argument" for proving greedy correctness?

An **exchange argument** proves that any optimal solution can be transformed into the greedy solution without worsening the objective value. You start with an arbitrary optimal solution and iteratively replace its choices with the greedy choices, showing at each step that the solution remains feasible and optimal. As noted in the **总结** section of [`thinkings/greedy.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/greedy.md), this technique is essential for validating that local optimal choices (like picking the interval that extends the rightmost boundary the farthest) necessarily lead to the global optimum.

### Why do greedy solutions for coverage problems use a "furthest" array or variable?

Coverage problems (覆盖问题) require tracking the maximum extent reachable from the current position. The **furthest** metric serves as the greedy choice criterion: at each step, you select the option (jump, clip, or tap) that extends this boundary the most. In the repository's implementations of `jump()`, `videoStitching()`, and `minTaps()`, the algorithm maintains `furthest` to track the maximum reachable index and `end` to mark the current coverage boundary. When the scan reaches `end`, the greedy choice is made by setting `end = furthest`, ensuring the minimum number of steps or intervals used.

### How do I handle impossible cases in greedy algorithms?

Always validate that the greedy scan can actually reach the target. In the repository's `videoStitching()` and `minTaps()` implementations, the code checks if `last == i` (cannot extend further) or `furthest[i] == 0` (uncovered segment) and returns `-1` to indicate impossibility. For `jump()`, the problem constraints guarantee reachability, but in general implementations, you should verify that the `furthest` boundary exceeds the current index at each step, ensuring the algorithm doesn't get stuck before reaching the goal.