16 articles
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.
LC 1167 Minimum Cost to Connect Sticks applies Huffman coding greedy with a min-heap. Always merge the two cheapest sticks first — a classic greedy pattern with a provable exchange argument that Amazon uses to test priority queue fluency.
LC 763 Partition Labels partitions a string into maximum parts where each letter appears in at most one part. Track the last occurrence of each character and greedily extend the current partition boundary — an elegant O(n) greedy interval merge.
Reconstruct a queue from height-position pairs [h, k] where k is the count of taller or equal people in front. Sort tallest first, then insert each person at their specified position k.
Maximise score jumping through an array where each jump covers 1 to k steps. Combine DP with a monotonic deque to find the sliding window maximum of recent DP values in O(n) time.
Find the maximum number of chunks that can be individually sorted to produce the full sorted array. A chunk boundary exists when the running maximum equals the current index — a clean O(n) greedy.