Greedy Algorithm: A Comprehensive Guide With Examples

The greedy algorithm is a fundamental problem-solving technique widely used in computer science and optimization. It follows a straightforward yet powerful principle: at each step, choose the option that appears best at the moment, without considering future consequences. Although this approach doesn’t always guarantee an optimal solution, it often yields efficient and effective results for many problems.

In this article, we will explore the Greedy Algorithm, its working mechanism, advantages, disadvantages, and various real-world applications. We will discuss how to determine whether a problem can be optimally solved using a greedy approach and provide examples with explanations.

Table of Contents

What is a Greedy Algorithm?

A Greedy Algorithm is an approach to solving optimization problems by making a sequence of choices, each of which is locally optimal. In other words, it selects the best available option at each step, hoping that this sequence of choices will lead to the global optimum.

The basic principle of the greedy algorithm is, as the name suggests, greed. In any situation, it selects the best available option without considering future consequences. While the chosen option may not be the best in the long run, the approach focuses solely on the present rather than the bigger picture. This is the essence of the greedy algorithm.

Characteristics of Greedy Algorithm

Greedy Choice Property – A global (overall) optimal solution can be reached by choosing local optimal solutions at each step.
Optimal Substructure – A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to its subproblems.
Non-reversibility – Once a choice is made, it cannot be changed in future steps.

Also check: Backtracking Algorithm Explained With Examples

How the Greedy Algorithm Works

The greedy algorithm follows a structured approach:

Initialize: Start from an initial state.
Select the best option: Pick the most beneficial choice at the current step.
Reduce the problem: Update the problem to a smaller version.
Repeat until completion: Continue selecting optimal choices until the whole problem is solved.

This process ensures that the algorithm continuously makes choices that appear best at the moment, leading to an overall efficient solution.

Example: Best Time to Buy and Sell Stock

Suppose you have an integer array, prices where prices[i] is a given stock’s price on the i^th day. You can decide to buy and/or sell the stock each day. Additionally, you can only hold at most one share of the stock at any time. Your task is to find maximum profit.

Approach for Solving the Problem (Step-by-Step Logical Explanation)

The goal is to maximize the profit by buying and selling stocks multiple times, even on the same day. The solution below follows a greedy approach to achieve this.

Step 1: Understand the Problem Statement

We have an array, prices, where prices[i] represents the price of a stock on the i-th day.
We can buy and sell stocks multiple times.
However, at any given time, we can only hold at most one share (i.e., we must sell before buying again).
We need to find the maximum profit possible by making optimal transactions.

Step 2: Identify Key Observations

When the stock price increases from one day to the next, profit is made.
The best strategy is to buy at a lower price and sell at a higher price whenever possible.
If prices[i] > prices[i-1], buying at prices[i-1] and selling at prices[i] yields profit.
Since we can buy and sell on the same day, we can accumulate these small profits without worrying about the “best single transaction.”

Step 3: Define the Strategy

Start with maxProfit = 0 (initial profit).
Traverse the price array from the second day (i = 1) to the last day.
If the stock price increases from the previous day (prices[i] > prices[i – 1]):
- Treat it as a profitable transaction.
- Add the difference prices[i] – prices[i – 1] to maxProfit.
Continue this process until the last day.
In the end, maxProfit will contain the maximum profit achievable.

Step 4: Example Walkthrough

Given prices:

[6, 1, 5, 1, 6, 4]

Iteration process:

Day	Price	Action	Profit
0	6	Start	0
1	1	No transaction (price drop)	0
2	5	Buy at 1, Sell at 5 (profit = 5 – 1)	4
3	1	No transaction (price drop)	4
4	6	Buy at 1, Sell at 6 (profit = 6 – 3)	9
5	4	No transaction (price drop)	9

Final Maximum Profit: 9

Step 5: Why Does This Work?

The greedy approach captures every possible increase in stock price to maximize profit.
It accumulates all small local profits, which together yield the maximum possible profit.
Since multiple transactions are allowed, the solution efficiently capitalizes on every price increase.

Step 6: Complexity Analysis

Time Complexity: O(n) (since we traverse the list once).
Space Complexity: O(1) (because we are using only a few variables).

Also check: Sliding Window Algorithm – Fixed and Variable-Length Solutions

Advantages of Greedy Algorithm

Efficiency
Greedy algorithms are typically faster than brute-force or dynamic programming solutions since they do not explore all possibilities. This makes them an excellent choice for problems where a quick approximation is needed.
Simplicity
The greedy approach is easy to understand and implement. Because it has fewer decision points and constraints, it allows for a more straightforward coding process.
Applicability
A greedy strategy can optimally solve many real-world problems, such as Huffman coding and Kruskal’s algorithm. Various fields, including networking, scheduling, and data compression, widely use these algorithms.

Disadvantages of Greedy Algorithm

Not Always Optimal
Greedy choices do not always lead to the best overall solution. The 0/1 Knapsack Problem, for example, cannot be solved optimally using a greedy approach.
Local Optimization
Since greedy algorithms focus on immediate benefits, they might ignore the bigger picture. Because of this, we might sometimes get suboptimal results.
Problem-Specific
Greedy algorithms work well only for problems satisfying the greedy choice property and optimal substructure. If a problem does not meet these conditions, a different approach, such as dynamic programming, is needed.

Examples of Greedy Algorithm

Activity Selection Problem
The activity selection problem involves choosing the maximum number of non-overlapping activities. Specifically, the greedy approach selects the activity that finishes first, gradually reducing the problem size at each step.
Huffman Coding (Data Compression)
Huffman coding is a greedy algorithm used for lossless data compression. Because it assigns shorter binary codes to more frequent characters, it reduces the overall data size.
Kruskal’s Algorithm (Minimum Spanning Tree)
Kruskal’s algorithm selects the smallest weight edges one by one while avoiding cycles. Thus, it ensures a minimal spanning tree.
Dijkstra’s Algorithm (Shortest Path)
Dijkstra’s algorithm finds the shortest path from a source node to all other nodes in a graph by greedily selecting the nearest unvisited node.
Fractional Knapsack Problem
Unlike the 0/1 knapsack problem, the fractional knapsack problem can be solved using a greedy approach by selecting items with the highest value-to-weight ratio.
Prim’s Algorithm (Minimum Spanning Tree)
Prim’s algorithm builds a minimum spanning tree by always selecting the nearest vertex to the growing tree.
Job Sequencing with Deadlines
This problem requires scheduling jobs to maximize profit while meeting deadlines. And a greedy approach helps in achieving an efficient schedule.
Coin Change Problem
The greedy method finds the minimum number of coins needed to make change. However, this method works optimally only when the coin denominations are in a certain order (such as the U.S. currency system).
Graph Coloring
The greedy approach is useful in coloring a graph with the minimum number of colors while ensuring no two adjacent nodes share the same color.
Interval Scheduling Maximization
The greedy algorithm maximizes the number of non-overlapping intervals in scheduling problems, such as allocating conference rooms or CPU time slots.

When to Use a Greedy Algorithm?

A greedy algorithm is an ideal choice when:

The problem exhibits optimal substructure, meaning the optimal solution to a problem includes optimal solutions to its subproblems.
The problem has the greedy choice property, meaning local optimal choices lead to a global optimum.
There is a need for a fast and efficient solution instead of brute-force methods.

If these conditions are not met, dynamic programming may offer a more effective solution.

Greedy Algorithm vs. Dynamic Programming

Feature	Greedy Algorithm	Dynamic Programming
Approach	Selects locally optimal choices	Solves subproblems and stores results
Computational Complexity	Faster, O(n log n) in many cases	Slower, often O(n²) or more
Memory Usage	Uses less memory	Uses more memory (memoization)
Examples	Kruskal’s Algorithm, Huffman Coding	Fibonacci Series, 0/1 Knapsack

In cases where dynamic programming is not necessary, greedy algorithms can provide a faster and more memory-efficient alternative.

Real-World Applications of Greedy Algorithm

Networking – Algorithms like Prim’s and Kruskal’s are used for designing efficient networks.
Scheduling – Greedy methods help optimize job scheduling, airline scheduling, and exam timetables.
Compression – Huffman encoding reduces file sizes effectively.
Pathfinding – Navigation systems like Google Maps use Dijkstra’s algorithm.
Finance – Greedy approaches assist in stock trading and investment portfolio selection.
Cryptography – Certain encryption techniques use greedy principles to optimize security protocols.
Artificial Intelligence – AI pathfinding algorithms often use greedy strategies for decision-making.
Game Theory – Used for decision-making in strategic games and AI opponent modeling.

Important Problems Based on The Greedy Algorithm

The greedy algorithm can solve many problems. Below are some important ones, along with the companies that asked these questions (in brackets).

Longest Palindrome (Accenture, JP Morgan, Visa, Nutanix)
Non-overlapping Intervals (Oracle, Amazon, Meta)
Remove Duplicate Letters (Infosys, PayPal, Wipro)
Gas Station (PhonePe, Ola, Atlassian, Zepto)
Largest Number (Intuit, Arcesium, Barclays)
Candy (TCS, LTI, Morgan Stanley, Oyo, Cognizant)

Conclusion

The Greedy Algorithm is a powerful problem-solving technique that provides efficient solutions for many optimization problems.

That’s all on the greedy algorithm.

To keep yourself up to date with our latest content, please subscribe to our newsletter by dropping your email address here: Signup for Our Newsletter.

Please follow us on Medium.