Greedy Algorithms & Monotonic Stack — Complete Guide

Greedy Algorithms

A greedy algorithm makes the locally optimal choice at each step, hoping it leads to a global optimum. Works when the problem has the greedy choice property: a global optimal solution can be built from locally optimal choices.

The 5 Core Greedy Patterns

Pattern 1 — Interval Scheduling (Sort by End Time)

Maximize number of non-overlapping intervals by greedily picking the earliest-ending activity.

intervals.sort(key=lambda x: x[1])  # sort by end
count = 0; prev_end = -inf
for start, end in intervals:
    if start >= prev_end:
        count += 1; prev_end = end

Pattern 2 — Activity Selection / Job Scheduling

Schedule jobs greedily to maximize profit. Sort by deadline or profit-per-unit.

Pattern 3 — Huffman / Greedy Coding

Minimum total cost to connect cables: always connect two cheapest. Priority queue (min-heap).

Pattern 4 — Two-Pointer Greedy

Assign people to tasks optimally. Sort both arrays, match greedily.

Pattern 5 — Candy / Fair Distribution

Local constraints from both sides. Two-pass: left-to-right then right-to-left.

Monotonic Stack

A monotonic stack maintains elements in increasing or decreasing order. Elements are popped when a better candidate arrives.

Pattern 6 — Next Greater Element

stack = []
for i in range(n):
    while stack and nums[stack[-1]] < nums[i]:
        idx = stack.pop()
        result[idx] = nums[i]  # nums[i] is NGE for idx
    stack.append(i)

Pattern 7 — Largest Rectangle in Histogram

stack = [-1]  # sentinel
for i, h in enumerate(heights):
    while stack[-1] != -1 and heights[stack[-1]] >= h:
        height = heights[stack.pop()]
        width = i - stack[-1] - 1
        area = height * width; max_area = max(max_area, area)
    stack.append(i)
# process remaining
while stack[-1] != -1:
    height = heights[stack.pop()]
    width = len(heights) - stack[-1] - 1
    max_area = max(max_area, height * width)

Complexity Reference

Problem Index