Greedy

A greedy algorithm builds a solution piece by piece, always choosing the option that looks best at the moment. Unlike dynamic programming, it never reconsiders its choices - once a decision is made, it's final.

Think of it like eating at a buffet: at each station, you pick whatever looks most appealing right now, without planning your entire meal in advance. Sometimes this strategy works perfectly (you end up with a great meal), and sometimes it backfires (you fill up on appetizers and miss the steak).

The key question with any greedy approach is: does making the locally optimal choice at each step lead to a globally optimal solution? When the answer is yes, greedy algorithms are powerful because they're simple and fast.

Greedy algorithms work when a problem has two special properties:

1. •

   Greedy-Choice Property: You can build an optimal solution by making locally optimal choices. The best choice right now won't prevent you from finding the best overall solution.

2. •

   Optimal Substructure: After making a greedy choice, the remaining problem is a smaller version of the original. The optimal solution to the whole problem contains optimal solutions to subproblems.

A classic example where greedy works is making change with US coins (25, 10, 5, 1 cents). To make 67 cents with the fewest coins, you always pick the largest coin that fits: 25 + 25 + 10 + 5 + 1 + 1 = 6 coins. This greedy approach happens to give the optimal answer.

But change the coins to [1, 3, 4] and try to make 6 cents. Greedy picks 4 + 1 + 1 = 3 coins, but optimal is 3 + 3 = 2 coins. Here, greedy fails because the problem lacks the greedy-choice property.

The activity selection problem is the textbook example of greedy algorithms. You have a list of activities, each with a start and end time, and you want to attend as many non-overlapping activities as possible.

The greedy insight is: always pick the activity that ends earliest. Why? Because finishing early leaves the maximum time for remaining activities. Any other choice would occupy time that could fit more activities.

Here's how it works: sort all activities by their end time, then iterate through them. If an activity starts after the previous one ended, take it.

The Jump Game problem asks: given an array where each element tells you the maximum jump length from that position, can you reach the last index?

The greedy approach is elegant: as you walk through the array, track the furthest position you could possibly reach. If at any point your current position exceeds this maximum reach, you're stuck and can't proceed.

This works because we don't care about the exact path - we only care whether reaching the end is possible. By always updating our maximum reach, we're implicitly considering all possible jump sequences.

Now the question changes: what's the minimum number of jumps to reach the end? This requires a slightly different greedy strategy.

Think of it like BFS levels. Each "level" contains all positions reachable with the same number of jumps. We track the boundary of the current level (currentEnd) and the farthest position reachable in the next level (farthest).

When we reach the current level's boundary, we must jump. The new boundary becomes wherever we could reach, and we increment our jump count. This greedy approach works because we're always extending our reach as far as possible before committing to a jump.

The key difference: greedy makes one choice and moves on, while DP explores all choices and picks the best.

Use greedy when:

• •There's a clear "best" choice at each step that doesn't hurt future options
• •The problem has the greedy-choice property (you can prove local optimal leads to global optimal)
• •Sorting creates an obvious order to process items

Use DP when:

• •Choices have cascading effects on future options
• •You need to try combinations to find the best
• •The problem asks for "number of ways" or optimal value where greedy would miss some options

A good test: try a few examples with your greedy approach. If you can find a counterexample where greedy gives the wrong answer, you likely need DP.

Example: Fractional Knapsack (can take fractions of items) -> Greedy works (sort by value/weight ratio) 0/1 Knapsack (must take whole items) -> Need DP (taking a heavy valuable item might block better combinations)

1. •

   Interval Scheduling: Sort by end time to maximize non-overlapping intervals. Problems like activity selection, minimum meeting rooms, and non-overlapping intervals all use this pattern.

2. •

   Merge Intervals: Sort by start time when you need to combine overlapping intervals. Different from scheduling because you're merging, not selecting.

3. •

   Two-Pointer Greedy: Use two pointers from both ends, greedily moving the "worse" pointer. Container With Most Water and Boats to Save People use this.

4. •

   Running Maximum/Minimum: Track the best value seen so far as you iterate. Jump Game tracks maximum reach; Best Time to Buy and Sell Stock tracks minimum price seen.

5. •

   Task Scheduling: Often involves heaps to always pick the "best" available task. Task Scheduler and Reorganize String use this pattern.

The classic running minimum problem. Find maximum profit from one buy-sell transaction.

The Greedy Insight: To maximize profit, we want to buy at the LOWEST price so far. As we scan through prices, we:

1. •Track the minimum price seen
2. •At each day, calculate profit if we sell today
3. •Update maximum profit if current profit is better

Visual Trace: [7, 1, 5, 3, 6, 4]

Why Greedy Works: We're guaranteed to find the optimal because:

• •We always know the best buy price seen so far
• •At each potential sell day, we compute the best possible profit

Can you complete a circular route starting from some gas station? If yes, which one?

Problem Setup:

• •N gas stations in a circle
• •gas[i] = gas available at station i
• •cost[i] = gas needed to travel from station i to i+1

Key Insight 1: If total gas >= total cost, a solution EXISTS.

Key Insight 2: If we fail at station j starting from i, then stations i+1 to j also cannot be starting points. So we try starting from j+1.

Visual Trace:

Each boat holds at most 2 people with weight limit. Minimize boats needed.

The Greedy Strategy: Pair the lightest person with the heaviest person if possible. This maximizes boat utilization.

Algorithm:

1. •Sort people by weight
2. •Two pointers: lightest (left) and heaviest (right)
3. •If they fit together, move both pointers
4. •If not, only the heaviest goes (they need a boat alone)

Visual Trace: people = [3, 2, 2, 1], limit = 3

Why This Works:

• •Heavy people might need solo boats
• •Light people should pair with someone
• •Pairing lightest with heaviest maximizes the chance the heaviest can share

Partition a string into max parts so each letter appears in at most one part.

The Greedy Insight: For each character, find its LAST occurrence. A partition must extend at least until the last occurrence of every character it contains.

Algorithm:

1. •Pre-compute last index of each character
2. •Scan string, tracking the farthest we must extend
3. •When current index equals farthest, we can end a partition

Visual Trace: "ababcbacadefegdehijhklij"

Reconstruct a queue from (height, k) pairs where k = number of taller people in front.

The Greedy Insight: Process people from tallest to shortest. When inserting a person, their k value tells us exactly where to insert (since all already-placed people are taller or equal).

Algorithm:

1. •Sort by height DESC, then by k ASC
2. •Insert each person at index = k

Visual Trace: [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

Why This Works: Taller people don't "see" shorter people. So when we insert a shorter person, their k value stays valid regardless of shorter people inserted later.

Find the minimum number of intervals to remove to make the rest non-overlapping.

Key Insight: This is equivalent to finding the MAXIMUM number of non-overlapping intervals (activity selection), then subtracting from total.

Algorithm:

1. •Sort by END time
2. •Greedily select intervals that don't overlap
3. •Answer = total - selected

Visual Trace: [[1,2],[2,3],[3,4],[1,3]]

In interviews, you may need to explain WHY greedy works. Two common proof techniques:

1. Greedy Stays Ahead Show that at every step, greedy's solution is at least as good as any other approach.

Example - Activity Selection:

2. Exchange Argument Show that any optimal solution can be transformed into greedy's solution without losing optimality.

Example - Fractional Knapsack:

When to Suspect Greedy Fails:

• •Choices affect future options in complex ways
• •Problem asks for count of ways (usually DP)
• •Small examples show counterexamples
• •Problem has "0/1" constraint (take all or nothing)

Quick reference for identifying greedy problems:

Decision Tree:

Mistake 1: Wrong Sort Key

Mistake 2: Not Proving Greedy Works

Mistake 3: Off-by-One in Interval Comparisons

Mistake 4: Forgetting to Track State

Pro Tips:

1. •Always verify greedy with 3-4 examples before coding
2. •Think about why greedy choice doesn't hurt future
3. •Many greedy problems combine with sorting
4. •If stuck, consider if problem has optimal substructure for DP

Time Complexity Patterns:

Space Complexity:

• •Most greedy: O(1) extra space (or O(n) for result)
• •Sorting in-place: O(1) or O(log n) for recursion
• •Pre-computing (like last indices): O(alphabet size)

Why Greedy is Often Fast:

• •Single or few passes through data
• •No recursion with branching
• •No memoization table needed
• •Sorting is often the slowest step

Comparison with DP:

When greedy works, it's almost always faster and simpler than DP!

Template 1: Running Maximum/Minimum

Template 2: Interval Selection (Max Non-Overlap)

Template 3: Two-Pointer Greedy

Template 4: Greedy with Pre-computation

Template 5: Circular Array Greedy