> For the complete documentation index, see [llms.txt](https://docs-57.gitbook.io/data-structure-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs-57.gitbook.io/data-structure-and-algorithms/problems/greedy.md).

# Greedy

**It's a problem-solving strategy that involves making the locally optimal choice at each step, hoping that this will lead to the overall optimal solution.**

**Imagine it like this:** You're navigating a maze, and at each junction, you choose the path that seems most promising right now, without considering the entire maze layout.

**Key characteristics:**

* **Local optimization:** Focuses on making the best decision at each individual step, rather than considering the entire problem space at once.
* **Iterative approach:** Builds a solution incrementally, one step at a time.
* **Not always optimal:** While sometimes leading to the best solution, it doesn't guarantee it in every case.

**Common examples:**

* **Activity selection problem:** Choosing the maximum number of non-overlapping activities that can be completed within a given time frame.
* **Dijkstra's shortest path algorithm:** Finding the shortest path between nodes in a graph.
* **Kruskal's minimum spanning tree algorithm:** Constructing a minimum spanning tree for a weighted graph.
* **Huffman coding:** Efficient compression of data using variable-length codes.

**When to consider greedy approach:**

* Problems where optimal substructure property holds (optimal solution can be constructed from optimal solutions to subproblems).
* Problems where a greedy choice can be made at each step without affecting future choices.
* Problems where finding a global optimal solution is too complex or time-consuming.