38 articles
LeetCode 739 — Find the number of days until a warmer temperature for each day using a monotonic decreasing stack. The key insight: store indices, not temperatures, in the stack. When a warmer day arrives, it is the "next greater element" for every cooler day still waiting on the stack — a fundamental pattern that appears in at least six other LeetCode problems.
Most candidates brute-force this in O(n·k) and hit TLE. Learn the monotonic deque invariant that reduces it to O(n) — with a step-by-step dry run, the five common bugs that break implementations, and why this pattern unlocks Jump Game VI and Constrained Subsequence Sum.
Master LeetCode 84 the right way. Learn exactly why bars are popped from the monotonic stack, how to calculate left/right boundaries without bugs, the sentinel-values trick that eliminates edge cases, and a step-by-step dry run on [2,1,5,6,2,3] — plus how this pattern extends directly to Maximal Rectangle (LC 85).
Master Greedy and Monotonic Stack: interval scheduling, activity selection, next greater/smaller element, largest rectangle, and trapping rain water.
Maximize children satisfied. Sort both greed and cookie sizes; greedily assign the smallest sufficient cookie to each child.
Minimum removals to make intervals non-overlapping. Sort by end time; greedily keep earliest-ending intervals, count conflicts.
Find minimum arrows to burst all balloons (intervals). Sort by end; one arrow can burst all overlapping intervals. Count arrows needed.
Find starting gas station index to complete circular route. If total gas >= total cost, a solution exists. Track running balance; reset start when negative.
Distribute minimum candies with higher-rated children getting more than neighbors. Two-pass: left-to-right for ascending, right-to-left for descending.
For each element in nums1, find next greater element in nums2. Monotonic stack + hashmap: process nums2, pop when greater found, store in map.
For each day find how many days until a warmer temperature. Monotonic decreasing stack of indices; pop when warmer temperature found.
Find the area of the largest rectangle in a histogram. Monotonic increasing stack: when a shorter bar is found, pop and compute rectangle area using popped height and current width.
Calculate water trapped between bars. Two-pointer approach: maintain max_left and max_right; water at each position = min(max_left, max_right) - height.
Remove duplicates to get smallest lexicographic subsequence with all chars. Greedy: use monotonic stack, only pop if char appears later.
Remove k digits to get smallest number. Monotonic increasing stack: pop larger digits when they appear before a smaller one. Remove remaining from end.
Sum of minimums of all subarrays. For each element, count how many subarrays have it as minimum using previous/next smaller element positions.
Find max j-i where i<j and nums[i]<=nums[j]. Build decreasing monotonic stack for left candidates, then scan from right to match.
Find i<j<k where nums[i]<nums[k]<nums[j]. Scan right-to-left with decreasing stack; track max popped element as potential 'nums[k]' candidate.
Find the largest rectangle in a binary matrix. Build histogram row by row (reset to 0 on '0'), apply Largest Rectangle in Histogram each row.
Next greater element in circular array. Iterate twice (2n) but use index mod n. Same decreasing stack pattern.
Minimum cost to connect all sticks. Always connect the two cheapest (Huffman coding variant). Min-heap greedy: cost = sum of merged sticks each round.
Partition string so each letter appears in at most one part. Track last occurrence of each char; greedily extend current partition end.
Reconstruct queue where [h,k] means person of height h has k taller/equal people in front. Sort by height desc (then k asc), insert at index k.
Maximum score to reach end where each jump is 1..k steps. Monotonic deque (sliding window maximum) of DP values for O(n) solution.
Find max chunks of array that when sorted individually give fully sorted array. A chunk boundary exists when max(chunk so far) == current index.
Complete Greedy and Monotonic Stack cheatsheet: all patterns, templates, complexity table, and problem index.
Find the next greater value for each node in a linked list using a monotonic decreasing stack of indices.
Find how many days until a warmer temperature using a monotonic decreasing stack of unresolved day indices.
Find the next greater element for each query in O(n+m) using a monotonic stack on nums2 and a lookup map.
Find the next greater element in a circular array by iterating twice (0 to 2n) and using a monotonic stack.
Calculate the stock price span (consecutive days <= today) using a monotonic stack that accumulates spans.
Remove k digits to form the smallest number by maintaining a monotonic increasing stack and greedy removal.
Sum the minimums of all subarrays by computing each element's contribution as the minimum using previous and next smaller element spans.
Detect a 132 pattern (i < j < k, nums[i] < nums[k] < nums[j]) using a monotonic stack scanning right to left.
Count visible people in a queue for each person using a monotonic decreasing stack scanning right to left.
Find the largest rectangle in a histogram by computing left and right boundaries using a monotonic increasing stack.
Find the maximal rectangle in a binary matrix by building histogram heights row by row and applying largest rectangle.
Calculate trapped rainwater volume using a monotonic stack that computes water in horizontal layers as bars are processed.