Greedy and Monotonic Stack — Master Recap and Cheatsheet

Problem Statement#

Consolidate every Greedy and Monotonic Stack pattern into a single revision sheet you can scan in 10 minutes before an interview.

Constraints:

• Cover all common patterns from LeetCode top 150 in this category
• Provide ready-to-paste templates in Python and JavaScript
• Map each pattern to a real LeetCode problem and complexity

Input:  Greedy / Monotonic problem
Output: Pattern, template, time complexity

Why This Problem Matters#

Greedy and Monotonic Stack are two of the most under-prepared topics in coding interviews. Greedy reasoning trips candidates because the optimal local move is rarely obvious. Monotonic Stack tricks candidates because they reach for two nested loops and time out. Mastering both unlocks 30 to 40 LeetCode hards across FAANG interview banks (Google, Meta, Amazon, Microsoft, Apple).

The Core Insight#

Greedy works when a problem has the greedy choice property (a local optimum extends to a global optimum) and optimal substructure. Monotonic Stack works when each element triggers a one-time decision about earlier elements (next greater, next smaller, span, area). The unifying idea: each element enters and leaves the stack at most once, giving amortized O(n).

Visual Dry Run#

Solution (Optimal)#

Greedy Patterns#

Monotonic Stack Patterns#

Monotonic Stack Template#

class Solution:
    def next_greater(self, arr):
        n = len(arr)
        result = [-1] * n
        stack = []
        for i, val in enumerate(arr):
            while stack and arr[stack[-1]] < val:
                idx = stack.pop()
                result[idx] = val
            stack.append(i)
        return result

var nextGreater = function(arr) {
    const n = arr.length;
    const result = new Array(n).fill(-1);
    const stack = [];
    for (let i = 0; i < n; i++) {
        while (stack.length && arr[stack[stack.length - 1]] < arr[i]) {
            const idx = stack.pop();
            result[idx] = arr[i];
        }
        stack.push(i);
    }
    return result;
};

Histogram Template#

class Solution:
    def largest_rect(self, heights):
        heights.append(0)
        stack = [-1]
        max_area = 0
        for i, h in enumerate(heights):
            while stack[-1] != -1 and heights[stack[-1]] >= h:
                height = heights[stack.pop()]
                width = i - stack[-1] - 1
                max_area = max(max_area, height * width)
            stack.append(i)
        return max_area

var largestRect = function(heights) {
    heights.push(0);
    const stack = [-1];
    let maxArea = 0;
    for (let i = 0; i < heights.length; i++) {
        while (stack[stack.length - 1] !== -1 && heights[stack[stack.length - 1]] >= heights[i]) {
            const height = heights[stack.pop()];
            const width = i - stack[stack.length - 1] - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
    return maxArea;
};

Time: O(n) for monotonic stack, O(n log n) for sort-based greedy Space: O(n) stack worst case

Common Mistakes#

• Forgetting to push the sentinel/index, leading to off-by-one width errors.
• Sorting greedy intervals by start instead of end (breaks scheduling).
• Using a max-heap when a monotonic deque is the right structure for sliding window max.
• Picking the wrong stack monotonicity (increasing vs decreasing).
• Believing a greedy is correct without proving it via an exchange argument.

Interview Tips#

• State your greedy choice in plain English before coding, then justify with a 2-line exchange argument.
• For monotonic stack, draw the array on a whiteboard and trace the stack column-by-column.
• Always sanity-check with the smallest input (size 1 or 2) and an already-sorted input.
• Mention amortized O(n): each index pushed and popped at most once.

Follow-up Questions#

• When does a greedy approach fail and force you to switch to DP?
• Can you adapt the monotonic stack to handle duplicates or strict vs non-strict inequalities?
• How do you turn a monotonic stack solution into an online streaming algorithm?

Problem Index#

Greedy: Assign Cookies (01), Non-overlap Intervals (02), Arrows (03), Gas Station (04), Candy (05), Partition Labels (18), Queue Reconstruction (19), Min Cost Sticks (17), Max Chunks (21)

Monotonic Stack: NGE I (06), Daily Temps (07), Largest Rect Histogram (08), Trapping Rain (09), Remove Duplicates (10), Remove K Digits (11), Sum Subarray Min (12), Max Width Ramp (13), 132 Pattern (14), Maximal Rectangle (15), NGE II Circular (16)

Monotonic Deque: Jump Game VI (20)

Key Takeaways#

• Greedy works only when the greedy choice property and optimal substructure both hold; prove it with an exchange argument.
• Sort interval problems by end time, not start time, for scheduling and piercing variants.
• Monotonic stacks turn O(n^2) neighbor-search problems into O(n) by amortizing pushes and pops.
• Choose stack monotonicity by what you want to find: decreasing for next greater, increasing for next smaller and histograms.
• Use a monotonic deque, not a stack, when the question involves sliding-window extrema.
• Always include sentinels (index -1 or value 0) to flush the stack cleanly at the end.
• Memorize the two templates above; 90 percent of interview questions in this family are direct adaptations.