Greedy Algorithm-(Theory)

What is Greedy Algorithm?

A Greedy Algorithm is a problem-solving paradigm where we build up a solution piece by piece, always choosing the option that offers the most immediate benefit (greedy choice). The hope is that this local optimum leads to a global optimum.

Core Properties of a Greedy Algorithm

For a problem to be solved using a greedy approach, it must have:

1. Greedy Choice Property
   A global optimal solution can be arrived at by choosing a local optimum at each step.

2. Optimal Substructure
   A problem has an optimal substructure if an optimal solution to the problem contains optimal solutions to its subproblems.

Process to Solve a Problem Using Greedy

To apply greedy strategy correctly:

Step 1: Identify the Greedy Choice Criteria

• What is the most optimal local choice? (e.g., lowest cost, highest value, earliest deadline)

Step 2: Sort/Arrange the Data

• Usually, sorting helps to expose the greedy choice. (e.g., sort by ratio, start time, end time, weight, etc.)

Step 3: Traverse and Make Optimal Local Decisions

• Iterate through the sorted array or structure.

• At each step, pick the choice that seems best at that moment.

Step 4: Ensure Constraints are Satisfied

• While making greedy choices, verify that global constraints are not violated.

Common Patterns in Greedy Algorithms

1. Activity Selection Pattern

• Idea: Pick activities with earliest finish time first to maximize the number of non-overlapping intervals.

• Sorting: By end time.

Problem: Leetcode: 435. Non-overlapping Intervals

2. Interval Scheduling / Meeting Rooms Pattern

• Idea: Schedule intervals based on start and end times.

• Variation:

  • Minimum number of rooms required → Use Min Heap on end times.

Problem: Leetcode: 253. Meeting Rooms II

3. Fractional Knapsack Pattern

• Idea: Choose items with the best value/weight ratio first.

• Sorting: By value/weight in decreasing order.

Problem: GFG: Fractional Knapsack

4. Job Sequencing Pattern

• Idea: Schedule jobs to maximize profit within deadlines.

• Sorting: By profit in descending order.

• Placement: Find the latest available slot before the deadline.

Problem: GFG: Job Sequencing Problem

5. Huffman Encoding / Compression

• Idea: Merge the two least frequent characters repeatedly.

• Tool: Use a Min Heap (priority queue).

• Sorting: Based on frequency (implicitly by min-heap).

📌 Problem: GFG: Huffman Encoding

6. Greedy Coin Change (NOT for all cases)

• Idea: Always pick the largest denomination ≤ remaining amount.

• Sorting: Descending order of coin values.

Only works when denominations are canonical (like INR, USD). For arbitrary denominations, use DP.

Problem: GFG: Coin Change using Greedy

7. Gas Station / Circular Tour

• Idea: Start from a station where total gas is enough to cover the circular trip.

• Observation: If total gas < total cost, not possible.

📌 Problem: Leetcode: 134. Gas Station

8. Jump Game

• Idea: Maximize the farthest reach at each step.

• Condition: If current index > maxReach → return false.

📌 Problem: Leetcode: 55. Jump Game

9. Greedy for Sorting / Swaps

• Idea: Swap elements to achieve smallest/largest form with limited swaps.

• Tool: Greedy digit swapping.

Problem: Leetcode: 670. Maximum Swap

General Template for Greedy Problems

// 1. Define the structure (if needed)
class Pair {
    int value, weight; // or other attributes
    double ratio;
}

// 2. Sort based on greedy criteria
Arrays.sort(arr, (a, b) -> Double.compare(b.ratio, a.ratio)); // descending

// 3. Traverse and apply local optimum
for (Pair item : arr) {
    if (condition) {
        // choose item
    }
}

Greedy vs Dynamic Programming (DP)

Pitfalls

• Greedy doesn’t always give the correct result. Counterexamples can often be constructed.

• Always check if:

  • The problem has optimal substructure.

  • Greedy choice leads to globally optimal results.

Practice Problems

🔚 Conclusion

• Greedy algorithms are fast and intuitive.

• Most effective when a problem has greedy-choice property and optimal substructure.

• Always start by sorting or arranging the data, then greedily select at each point.

• When greedy doesn’t work, fall back to Dynamic Programming.