Greedy Algorithm Explained: When It Works, When It Fails, and Why

Imagine standing in a candy shop with only a few coins in your pocket. You want to grab the tastiest treats while spending the least. So, you pick the biggest candies with the lowest prices, one at a time, until your money runs out. That, in essence, is how a Greedy Algorithm thinks.

It makes decisions based on what's best at the moment. It doesn’t care about what came before or what may come next. This method can work wonders, but not always! In the article, we will break down how it works, where it shines, and when it fails.

Interested in making a career in the Data Science field? If so, pursue Online Data Science Courses offered by top Indian and global universities.

What is a Greedy Algorithm?

A Greedy Algorithm is an optimization technique that builds a solution step by step by making the most favorable choice at each stage—based only on the current situation—without revisiting or revising past decisions.

It never looks back or plans ahead. Instead, it assumes that picking a local optimum—the best immediate option—will eventually lead to a global optimum, the best overall outcome.

This approach only works when the problem satisfies two key conditions: the greedy-choice property and optimal substructure.

Must Explore: What is an Algorithm?

What is the Intuition Behind Greedy Algorithms?

Greedy algorithms believe in the local optimum at every step.

Think of it like hiking: at every fork, you pick the path that goes most uphill. You hope this leads to the mountain peak. Sometimes it works. Sometimes you get stuck on a tall hill that isn’t the highest.

So, it’s fast, simple, and memory-efficient. But risky if the problem structure doesn't support it.

Also Read: What is BFS Algorithm? Breath First Search Algorithm Explained

What Are the Characteristics of Greedy Algorithms?

Here are some of the characteristics of greedy algorithms:

• Greedy algorithms follow straightforward logic and are generally easy to implement.
• They often run quickly and perform well in time-sensitive scenarios.
• When both greedy and dynamic programming approaches apply, greedy is often chosen for its lower complexity, as in Dijkstra's Algorithm vs Bellman-Ford (when no negative weights exist).
• Once a choice is made, it’s final—greedy algorithms do not backtrack or revise earlier decisions.

Check out the Tower of Hanoi Algorithm article!

How Greedy Algorithms Work?

Let's go through an example to understand how greedy algorithms work.

Suppose your backpack can hold up to 10 kg, and you're presented with three valuable items. You can only carry a total of 10 kg, so you'll need to choose wisely:

A greedy algorithm might pick the item with the highest value first—the Marble Sculpture worth INR 650. But it weighs 7 kg, leaving only 3 kg of space, which isn't enough to take either of the remaining items.

So, the total value ends up being 650.

However, a better choice would be to take the Lantern and the Book Set. Together, they weigh exactly 10 kg and give you a total value of 900.

Greedy Algorithm fails here because:

• Greedy picks the highest immediate value (local optimum)
• But misses the best combination for maximum value (global optimum)

Greedy Algorithm Example

Problem: You are given a list of activities with start and end times. Select the maximum number of non-overlapping activities.

Greedy Strategy: Always select the next activity that finishes earliest and doesn’t overlap.

Selected Activities (Output): A1: (1, 4), A4: (5, 7), A5: (8, 9)

Greedy Algorithm Implementation in Code

Python

activities = [
    ("A1", 1, 4), ("A2", 3, 5), ("A3", 0, 6),
    ("A4", 5, 7), ("A5", 8, 9), ("A6", 5, 9)
]

def activity_selection(activities):
    activities.sort(key=lambda x: x[2])  # Sort by end time
    selected = [activities[0]]
    last_end = activities[0][2]

    for activity in activities[1:]:
        if activity[1] >= last_end:
            selected.append(activity)
            last_end = activity[2]
    return selected

for act in activity_selection(activities):
    print(f"{act[0]}: ({act[1]}, {act[2]})")

Output: A1: (1, 4), A4: (5, 7), A5: (8, 9)

C++

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;

bool compare(tuple<string, int, int> a, tuple<string, int, int> b) {
    return get<2>(a) < get<2>(b);
}

vector<tuple<string, int, int>> activitySelection(vector<tuple<string, int, int>> &activities) {
    sort(activities.begin(), activities.end(), compare);
    vector<tuple<string, int, int>> result;
    result.push_back(activities[0]);
    int last_end = get<2>(activities[0]);

    for (int i = 1; i < activities.size(); ++i) {
        if (get<1>(activities[i]) >= last_end) {
            result.push_back(activities[i]);
            last_end = get<2>(activities[i]);
        }
    }
    return result;
}

int main() {
    vector<tuple<string, int, int>> activities = {
        {"A1", 1, 4}, {"A2", 3, 5}, {"A3", 0, 6},
        {"A4", 5, 7}, {"A5", 8, 9}, {"A6", 5, 9}
    };
    vector<tuple<string, int, int>> result = activitySelection(activities);
    for (auto &act : result)
        cout << get<0>(act) << ": (" << get<1>(act) << ", " << get<2>(act) << ") ";
    return 0;
}

Output: A1: (1, 4), A4: (5, 7), A5: (8, 9)

Java

import java.util.*;

public class ActivitySelection {
    public static List<String> selectActivities(String[][] activities) {
        Arrays.sort(activities, Comparator.comparingInt(a -> Integer.parseInt(a[2])));
        List<String> result = new ArrayList<>();

        result.add(activities[0][0] + ": (" + activities[0][1] + ", " + activities[0][2] + ")");
        int lastEnd = Integer.parseInt(activities[0][2]);

        for (int i = 1; i < activities.length; i++) {
            int start = Integer.parseInt(activities[i][1]);
            int end = Integer.parseInt(activities[i][2]);
            if (start >= lastEnd) {
                result.add(activities[i][0] + ": (" + activities[i][1] + ", " + activities[i][2] + ")");
                lastEnd = end;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        String[][] activities = {
            {"A1", "1", "4"}, {"A2", "3", "5"}, {"A3", "0", "6"},
            {"A4", "5", "7"}, {"A5", "8", "9"}, {"A6", "5", "9"}
        };
        List<String> result = selectActivities(activities);
        for (String act : result) System.out.println(act);
    }
}

Output: A1: (1, 4), A4: (5, 7), A5: (8, 9)

What Are the Most Common Greedy Algorithm Examples?

Greedy algorithms are commonly used in problems where making a series of locally optimal decisions leads to a globally optimal solution. Let’s look at the most popular ones, along with short and accurate examples for each.

Fractional Knapsack

This problem asks you to maximize the value you can carry in a bag with a limited weight capacity. The greedy strategy is to select items based on their value-to-weight ratio. Start with the highest ratio and take as much of that item as possible before moving to the next. Since you can take fractional amounts, this approach guarantees the optimal result.

Example:

Items = [A1 (value=60, weight=10), A2 (value=100, weight=20), A3 (value=120, weight=30)]Knapsack capacity = 50

• Take A1 completely: 10 kg; 60 value
• Take A2 completely: 20 kg; 100 value
• Take 2/3 of A3: 20 kg; 80 value
  Total value = 240

Must Explore: Binary Search Algorithm & Time Complexity article!

Dijkstra’s Algorithm

Dijkstra’s algorithm is used to find the shortest distance from a source node to all other nodes in a weighted graph. It works greedily by always expanding the nearest unvisited node. This strategy works only when all edge weights are non-negative.

Example:

Task: Find the shortest path from node A to node D.

• A to B = 4
• A to C = 2
• C to D = 7
• B to D = 10

Path A to B to D = 14
Path A to C to D = 9

Greedy selects the shortest known node (C) first, leading to the optimal path A → C → D with total cost = 9

Kruskal’s Algorithm

Kruskal’s algorithm builds a Minimum Spanning Tree by sorting all edges in increasing order and adding them one by one, only if they don’t form a cycle. It’s greedy because it always picks the lowest-weight edge available.

Example: Graph edges: A–B (1), B–C (2), A–C (3) → Pick A–B and B–C to connect all nodes without a cycle. Total MST weight = 3

Huffman Coding

This algorithm compresses data by assigning shorter binary codes to more frequent characters. It works by repeatedly combining the two nodes with the smallest frequencies, creating a tree where the most common characters are closer to the root.

Example: Frequencies = A(5), B(9), C(12), D(13)Combine A and B → Merge with C → Merge with D → Huffman Tree created

Codes: A = 00, B = 01, C = 10, D = 11 (shorter codes for higher frequencies

Prim’s Algorithm

Like Kruskal’s, Prim’s builds a Minimum Spanning Tree. But instead of starting with edges, it starts with a single node and grows the tree by always picking the smallest edge connecting to an unvisited node. It expands greedily at each step.

Example: Start at node A → connect to B (1) → connect to C (2) → total MST weight = 3

Do you know about quicksort algorithms? If not, read the What is Quicksort Algorithm article.

What Are the Advantages and Disadvantages of Greedy Algorithms?

Here are some of the advantages and disadvantages of greedy algorithms:

How Does the Greedy Approach Differ from Other Algorithms?

Greedy algorithms focus on making the best decision at each step, based solely on current conditions. They assume that a sequence of locally optimal choices will result in a globally optimal solution.

Other strategies like Dynamic Programming (DP) and Brute Force take a more exhaustive or cautious route.

Conclusion

Greedy algorithms shine when the local best decisions lead to a global optimum. They're fast, efficient, and easy to implement. But use them with caution—without the right structure, greedy can cost you the optimal solution. Always test, prove, and understand the problem before going greedy.

FAQ’s

1. What are the common traits of greedy-suitable problems?

Greedy-suitable problems usually exhibit optimal substructure and the greedy-choice property. This means you can build an optimal solution step by step by making locally optimal choices, and those choices won't need to be changed later.

2. How to prove that a greedy approach is correct?

You can prove correctness through mathematical induction, proof by contradiction, or by comparing the greedy solution with a known optimal result. Testing against edge cases where greedy fails can also validate your logic.

3. Is the greedy method always the best choice?

No. Greedy is only best when the problem structure guarantees that locally optimal choices lead to a globally optimal solution. Otherwise, dynamic programming or backtracking may be better.

4. Can greedy algorithms solve all optimization problems?

No. Greedy algorithms are limited to problems where making a local optimum choice always leads to the global optimum. Problems like the 0/1 Knapsack or Longest Common Subsequence cannot be solved optimally using greedy methods.

5. Why does greedy fail in some problems?

Greedy fails when the problem lacks optimal substructure or the greedy-choice property. In such cases, local decisions can prevent reaching the global best outcome.

6. Can greedy be combined with other techniques?

Yes. Some hybrid approaches use greedy along with backtracking, dynamic programming, or divide-and-conquer to optimize performance or correctness.

7. What’s the difference between greedy and divide-and-conquer?

Greedy builds solutions incrementally, making decisions without recursion or combining sub-solutions. Divide-and-conquer splits the problem into parts, solves each recursively, and merges the results.

8. Are greedy algorithms memory efficient?

Yes. Greedy algorithms typically require very little memory since they don’t store state history or explore alternative paths.

9. How do you identify the greedy metric in a problem?

Look for what needs to be maximized or minimized: value-to-weight ratio, earliest finish time, shortest edge, etc. This metric becomes your decision-making criteria.

10. Are greedy algorithms suitable for real-time systems?

Absolutely. Because of their speed and low memory usage, greedy algorithms are great for real-time scheduling, load balancing, and routing systems.

11. Do greedy algorithms always require sorting?

Not always, but most greedy solutions begin with sorting based on the metric that guides the greedy choice (e.g., weight, cost, finish time).