Greedy Algorithms and Monotonic Stack — Complete FAANG Interview Guide

Problem Statement#

This master guide covers two of the most asked FAANG interview families: greedy algorithms and monotonic stacks/deques. We will map every LeetCode pattern in this series to a single mental model so you can pick the right tool in seconds.

Constraints (typical across the series):

• Array sizes up to 10^5 to 10^6 — most solutions must be O(n) or O(n log n)
• Values can be negative, zero, or up to 10^9
• Many problems have a stricter "linear time" follow-up

Input:  intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1   // minimum number of intervals to remove

Input:  heights = [2,1,5,6,2,3]
Output: 10  // largest rectangle in histogram

Why This Problem Matters#

Greedy and monotonic stack problems dominate the FAANG interview loop. Meta, Amazon, Google, Bloomberg, and Apple use these patterns to test whether you can prove correctness, not just code a solution. The greedy interview question is usually a one-line algorithm that requires a multi-paragraph exchange argument — recruiters want to see that argument out loud.

Monotonic stack FAANG questions like Daily Temperatures, Largest Rectangle, and Trapping Rain Water are graded on whether you can collapse an O(n^2) brute force to O(n) using a stack invariant. These show up in coding rounds at Amazon (especially L5/L6), in Google onsite arrays sets, and in nearly every Bloomberg phone screen.

If you internalize the exchange argument and the monotonic invariant, you unlock roughly 80 LeetCode problems with the same shape. This guide is the index for the rest of the series.

The Core Insight#

Greedy works only when the problem has the greedy choice property plus optimal substructure. The proof technique is the exchange argument: assume an optimal solution differs from the greedy choice, then swap the differing element with the greedy one and show the solution stays valid and no worse.

Monotonic stacks work because each element is pushed and popped at most once. The invariant — strictly increasing or strictly decreasing from bottom to top — encodes the answer to "next greater" or "next smaller" in amortized O(1) per element.

Visual Dry Run#

Solution (Optimal)#

class Solution:
    # Pattern 1 — Greedy interval scheduling
    def eraseOverlapIntervals(self, intervals):
        intervals.sort(key=lambda x: x[1])
        prev_end = float('-inf')
        kept = 0
        for s, e in intervals:
            if s >= prev_end:
                kept += 1
                prev_end = e
        return len(intervals) - kept
 
    # Pattern 2 — Monotonic decreasing stack (next greater)
    def dailyTemperatures(self, T):
        n = len(T)
        ans = [0] * n
        stack = []
        for i, t in enumerate(T):
            while stack and T[stack[-1]] < t:
                j = stack.pop()
                ans[j] = i - j
            stack.append(i)
        return ans
 
    # Pattern 3 — Histogram with monotonic increasing stack
    def largestRectangleArea(self, heights):
        stack = []
        best = 0
        heights.append(0)
        for i, h in enumerate(heights):
            while stack and heights[stack[-1]] > h:
                top = stack.pop()
                left = stack[-1] if stack else -1
                best = max(best, heights[top] * (i - left - 1))
            stack.append(i)
        return best

var eraseOverlapIntervals = function(intervals) {
    intervals.sort((a, b) => a[1] - b[1]);
    let prevEnd = -Infinity, kept = 0;
    for (const [s, e] of intervals) {
        if (s >= prevEnd) { kept++; prevEnd = e; }
    }
    return intervals.length - kept;
};
 
var dailyTemperatures = function(T) {
    const n = T.length, ans = new Array(n).fill(0), stack = [];
    for (let i = 0; i < n; i++) {
        while (stack.length && T[stack[stack.length - 1]] < T[i]) {
            const j = stack.pop();
            ans[j] = i - j;
        }
        stack.push(i);
    }
    return ans;
};
 
var largestRectangleArea = function(heights) {
    const stack = [];
    let best = 0;
    heights.push(0);
    for (let i = 0; i < heights.length; i++) {
        while (stack.length && heights[stack[stack.length - 1]] > heights[i]) {
            const top = stack.pop();
            const left = stack.length ? stack[stack.length - 1] : -1;
            best = Math.max(best, heights[top] * (i - left - 1));
        }
        stack.push(i);
    }
    return best;
};

Time: O(n log n) for sort-based greedy, O(n) for monotonic stack passes Space: O(n) for the stack, O(1) extra for greedy two-pointer variants

Common Mistakes#

• Sorting by start time instead of end time in interval scheduling — breaks the exchange argument
• Forgetting to push the sentinel zero at the end of histogram problems, leaving items stuck on the stack
• Using <= vs < incorrectly in the stack while loop, producing duplicate or skipped pops
• Confusing monotonic stack (top is most recent) with monotonic deque (used for sliding window max)
• Believing greedy always works — many problems require DP because the greedy choice property fails

Interview Tips#

• State the invariant out loud before you code: "stack stays strictly decreasing in temperature"
• Prove correctness with an exchange argument when the interviewer asks "why does this work"
• Mention the O(n) amortized analysis: each element is pushed and popped at most once
• Sketch the visual: bars for histograms, intervals on a number line — interviewers love it

Follow-up Questions#

• How would you adapt monotonic stack to a circular array? Hint: iterate twice modulo n
• Can you solve Largest Rectangle in O(n) without a stack? Hint: divide and conquer with sparse table
• What if intervals are streamed and cannot be sorted? Hint: use a min-heap by end time
• How does monotonic deque differ from monotonic stack? Hint: it allows pops from both ends
• When does greedy fail and you need DP instead? Hint: when local choice depends on future state

Key Takeaways#

• Greedy requires both the greedy choice property and optimal substructure to be correct
• The exchange argument is the standard proof technique for greedy correctness
• Monotonic stacks solve next-greater and next-smaller problems in amortized O(n)
• Sort by end time for interval scheduling, by start time for merging
• Each element enters and leaves a monotonic stack at most once — that is the O(n) bound
• Histogram problems benefit from a sentinel zero appended to flush the stack
• Trapping Rain Water can be solved by two-pointer or by monotonic stack — both are FAANG-favorite