27 articles
Learn how to find the next greater node in a linked list using a monotonic stack in O(n) time. A popular interview question at Amazon and Adobe that tests your stack intuition and linked list traversal skills.
LeetCode 739 — asked at Amazon, Google, and Meta. Find the number of days until a warmer temperature using a monotonic decreasing stack. Store indices not temperatures, pop when current day is warmer, and solve six related problems with the same O(n) pattern.
LeetCode 84 — asked at Amazon, Google, and Microsoft. Find the largest rectangle in a histogram using a monotonic increasing stack. For each bar, find the nearest shorter bars on both sides to compute the maximum width. O(n) time, O(n) space.
A complete FAANG-ready guide to greedy algorithms and monotonic stacks: interval scheduling, exchange arguments, next greater element, histogram problems, and trapping rain water patterns.
LC 496 Next Greater Element I is the canonical entry point for monotonic stack thinking. Master the decreasing stack pattern and hash map lookup here, and you will recognize the same structure in Daily Temperatures, Largest Rectangle in Histogram, and Trapping Rain Water.
LC 739 Daily Temperatures is the most important medium-level monotonic stack problem. Unlike Next Greater Element, the stack stores indices so you can compute waiting distances. Every FAANG company uses this to gauge stack fluency.
LC 84 Largest Rectangle in Histogram is the canonical hard monotonic stack problem. The key insight — use an increasing stack and compute maximum rectangle area when a shorter bar causes a pop — unlocks both this problem and Maximal Rectangle.
LC 42 Trapping Rain Water is one of the most famous hard problems in FAANG interviews. The optimal two-pointer approach uses O(1) space. Knowing all three approaches and their trade-offs separates senior candidates from junior ones.
LC 316 Remove Duplicate Letters combines greedy with a monotonic stack to find the lexicographically smallest subsequence containing every character exactly once. The "pop only if the character appears again later" check using last_occurrence is the key insight.
LC 402 Remove K Digits uses a monotonic increasing stack to greedily eliminate digits that make the number larger. The three-part answer construction — pop k times, trim trailing removals, strip leading zeros — is the exact pattern that trips candidates in interviews.
LC 907 Sum of Subarray Minimums introduces the contribution technique: instead of finding the minimum of each subarray, count how many subarrays each element is the minimum of. Two monotonic stacks compute left and right boundaries in O(n).
LC 962 Maximum Width Ramp finds the largest j-i with nums[i] <= nums[j]. The two-pass approach — build a decreasing stack of candidates, then scan right-to-left to match — is a pattern that appears in several max-width-satisfying-condition problems.
LC 456 132 Pattern requires finding i < j < k where nums[i] < nums[k] < nums[j]. The right-to-left decreasing stack maintains the "2" candidate — the key insight that makes an O(n) solution possible where left-to-right fails.
LC 85 Maximal Rectangle is a hard problem that reduces to running Largest Rectangle in Histogram on each row. Build cumulative height histograms row by row and apply the O(n) monotonic stack solution — the reduction is the key insight.
LC 503 Next Greater Element II extends the NGE pattern to circular arrays. Use a monotonic decreasing stack with a double-pass (iterate 2n) and modular indexing to handle wrap-around — a critical adaptation tested as a follow-up at every FAANG company.
Find the longest contiguous subarray whose sum is at most K in linear time using prefix sums plus a decreasing monotonic stack, then learn the segment tree and BIT alternatives for streaming variants.
Find how many days until a warmer temperature using a monotonic decreasing stack of unresolved day indices. The canonical monotonic stack problem asked at every FAANG company — master the pattern here and unlock 20+ harder problems.
Find the next greater element for each query using a monotonic stack on nums2 and a hash map lookup in O(n+m) time. A classic application of the monotonic stack pattern combined with hash map lookups for efficient query answering.
Find the next greater element in a circular array by processing 2n indices with modulo indexing and a monotonic stack. The circular variant of the classic monotonic stack pattern — an elegant trick that extends NGE I to handle wrap-around in O(n) time.
Calculate the stock price span using a monotonic decreasing stack that stores (price, span) pairs and accumulates spans in O(1) amortized time. A classic streaming design problem that tests span accumulation and the monotonic stack pattern.
Remove k digits from a number string to form the smallest possible number using a monotonic increasing stack with greedy removal. A key FAANG problem testing greedy thinking, stack manipulation, and edge case handling with leading zeros.
Sum the minimum of all subarrays using a monotonic stack to find each element's contribution as the minimum element across all subarrays it dominates. A critical FAANG problem teaching the contribution-counting pattern with monotonic stacks.
Solve LeetCode 456 132 Pattern in O(n) using a monotonic stack scanned from right to left while tracking the best second-largest. A FAANG interview favorite at Bloomberg, Amazon, and Google.
Solve LeetCode 1944 Number of Visible People in a Queue in O(n) using a monotonic decreasing stack. A FAANG hard interview problem at Amazon, Google, and Meta that uses LIFO stack semantics for visibility queries.
Solve LeetCode 84 Largest Rectangle in Histogram in O(n) using a monotonic increasing stack. The single most important monotonic stack interview problem at FAANG.
Solve LeetCode 85 Maximal Rectangle in O(m times n) by reducing each row to a histogram and applying the monotonic stack. A FAANG hard interview classic.
Solve LeetCode 42 Trapping Rain Water in O(n) using a monotonic decreasing stack to fill water layer by layer. The signature FAANG monotonic stack hard problem.