DSA Masterclass Module 11: Greedy Algorithms

Introduction to Greedy Algorithms

Mental Model

Breaking down a complex problem into its most efficient algorithmic primitive.

A Greedy Algorithm is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most immediate benefit.

In simpler terms: "Take the best choice you have right now, and never look back."

While Greedy doesn't always lead to the optimal solution (unlike Dynamic Programming), it is blazingly fast when it works. In FAANG interviews, Greedy problems are often used to test your ability to recognize optimization shortcuts.

1. Real-World Intuition: Making Change

Imagine you are a cashier giving $36 cents in change. You have quarters ($25), dimes ($10), nickels ($5), and pennies ($1).

You take the largest possible coin first: Quarter (Remains $11).
Next largest: Dime (Remains $1).
Next largest: Penny (Remains $0).
Result: 3 coins.

Because the US coin system is designed this way, the "Greedy" choice of taking the largest coin always leads to the fewest coins (the global optimum).

2. Pattern Recognition: Is it Greedy?

A problem can be solved with Greedy if it satisfies two properties:

Greedy Choice Property: A global optimum can be reached by choosing a local optimum.
Optimal Substructure: An optimal solution to the problem contains optimal solutions to its subproblems.

Common Signs:

It's an Optimization Problem (Find the minimum/maximum).
It involves Scheduling or Intervals.
You can sort the input to make the best choice obvious.

3. Solved Examples

Example 1: Interval Scheduling (Meeting Rooms)

Given a set of meetings with start and end times, what is the maximum number of non-overlapping meetings you can attend?

The Greedy Choice: Always pick the meeting that ends earliest. This leaves the maximum amount of time for remaining meetings.

public int maxMeetings(int[][] intervals) {
    // Sort by end time
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

    int count = 0;
    int lastEndTime = -1;

    for (int[] interval : intervals) {
        if (interval[0] >= lastEndTime) {
            count++;
            lastEndTime = interval[1];
        }
    }
    return count;
}

Example 2: Jump Game

Given an array where nums[i] is your max jump length at that position, can you reach the last index?

public boolean canJump(int[] nums) {
    int furthestReach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > furthestReach) return false;
        furthestReach = Math.max(furthestReach, i + nums[i]);
    }
    return true;
}

Example 3: Huffman Coding (Intuition)

Given a set of characters and their frequencies, find the optimal prefix-free binary code. Greedy Strategy: Always merge the two nodes with the lowest frequencies. This ensures that frequent characters have shorter codes.

Example 4: Gas Station

There are n gas stations along a circular route. Given gas[i] and cost[i], return the starting gas station index if you can travel around the circuit once.

public int canCompleteCircuit(int[] gas, int[] cost) {
    int totalGas = 0, totalCost = 0, currGas = 0, start = 0;
    for (int i = 0; i < gas.length; i++) {
        totalGas += gas[i];
        totalCost += cost[i];
        currGas += gas[i] - cost[i];
        if (currGas < 0) {
            start = i + 1;
            currGas = 0;
        }
    }
    return totalGas >= totalCost ? start : -1;
}

4. Practice Problems

Interval Scheduling: (Easy)
Jump Game: (Medium)
Gas Station: (Medium)
Fractional Knapsack: (Easy)
Assign Cookies: (Easy)
Task Scheduler: (Medium)
Minimum Number of Arrows to Burst Balloons: (Medium)
Non-overlapping Intervals: (Medium)
Two City Scheduling: (Medium)
Candy: (Hard)

5. Common Mistakes

Greedy vs DP: Trying to solve a problem with Greedy when it requires Dynamic Programming (e.g., the coin change problem with non-standard coin values like {1, 3, 4} for target 6).
Sorting the wrong way: In interval problems, sorting by start time instead of end time can lead to suboptimal results.
Missing Edge Cases: Not handling negative values or empty inputs.

6. Interview Tips

Prove it by Contradiction: If you think a greedy choice works, try to imagine a scenario where it fails. If you can't find one, it's likely correct.
Sort First: 90% of Greedy problems involve sorting the input as the first step.
Ask yourself: "What is the one metric I can use to make the 'best' decision at each step?"

Final Takeaways

Greedy is about local optimization.
Always check if the "Greedy Choice Property" holds.
It usually results in $O(n \log n)$ time due to sorting and $O(1)$ space.

6. Staff-Level Verbal Masterclass (Communication)

Interviewer: "How would you defend this specific implementation in a production review?"

You: "In a mission-critical environment, I prioritize the Big-O efficiency of the primary data path, but I also focus on the Predictability of the system. In this implementation, I chose a state-based dynamic programming approach. While a recursive solution is more readable, I would strictly monitor the stack depth. If this were to handle skewed inputs, I would immediately transition to an explicit stack on the heap to avoid a StackOverflowError. From a memory perspective, I leverage primitive arrays to ensure that we minimize the garbage collection pauses (Stop-the-world) that typically plague high-throughput Java applications."

7. Global Scale & Distributed Pivot

When a problem like this is moved from a single machine to a global distributed architecture, the constraints change fundamentally.

Data Partitioning: We would shard the input space using Consistent Hashing. This ensures that even if our dataset grows to petabytes, any single query only hits a small subset of our cluster, maintaining logarithmic lookup times.
State Consistency: For problems involving state updates (like DP or Caching), we would use a Distributed Consensus protocol like Raft or Paxos to ensure that all replicas agree on the final state, even in the event of a network partition (The P in CAP theorem).

8. Performance Nuances (The Staff Perspective)

Cache Locality: Accessing a 2D matrix in row-major order (reading [i][j] then [i][j+1]) is significantly faster than column-major order in modern CPUs due to L1/L2 cache pre-fetching. I always structure my loops to align with how the memory is physically laid out.
Autoboxing and Generics: In Java, using List<Integer> instead of int[] can be 3x slower due to the overhead of object headers and constant wrapping. For the most performance-sensitive sections of this algorithm, I advocate for primitive specialized structures.

Key Takeaways

You take the largest possible coin first: Quarter (Remains $11).
Next largest: Dime (Remains $1).
Next largest: Penny (Remains $0).