Tags
- ⭐ = solved in first try
- 📍 = revisit
- 🔥 = important
- ⚠️ = solved but edge case missed
- 👀 = solved but had to see little solution first
- 🐢 = solved, but less optimized
- 💀 = out of the box
- no tag = pending/not started
5. Pattern: Monotonic Stack
5.1 Direct NGE / NSE / PGE / PSE
💡 Signal: “next greater element”, “daily temperatures”, “stock span”
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Next Greater Element I (easy) | NGE on nums2, map values. Stack stores values not indices | ||
| 2. Next Greater Element II (medium) | circular → iterate 2n times, use i % n | ||
| 3. Daily Temperatures (medium) | NGE in disguise, answer = nge[i] - i | ||
| 4. Online Stock Span (medium) | PGE — span = i - pge[i]. Store {price, idx} pairs | ||
| 5. Next Greater Node in Linked List (medium) | convert LL to array first, then standard NGE | ||
| 6. Final Prices With Special Discount (easy) | NSE — discount = price of next smaller or equal |
5.2 Histogram / Rectangle Problems
💡 Signal: “largest rectangle”, “maximal rectangle”, bar extending left/right
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Largest Rectangle in Histogram (hard) | PSE + NSE merged. width = nse[i] - pse[i] - 1 | ||
| 2. Maximal Rectangle (hard) | convert each row to histogram heights, apply LC 84 |
5.3 Trapping Rain Water
💡 Signal: “how much water trapped”, elevation map
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Trapping Rain Water (hard) | decreasing stack. On pop: h = min(left, right) - mid, w = gap | ||
| 2. Container With Most Water (medium) | two pointers approach (not mono stack, but related) |
5.4 Sum of Subarray Mins / Maxs
💡 Signal: “sum of subarray minimums”, “subarray ranges”, contribution of each element
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Sum of Subarray Minimums (medium) | PSE(>=) + NSE(>). contribution = arr[i] * left * right | ||
| 2. Sum of Subarray Ranges (medium) | = sumOfMaxs - sumOfMins. Apply pattern twice | ||
| 3. Sum of Total Strength of Wizards (hard) | mono stack + prefix sum of prefix sums. Very hard |
5.5 Stack-Based Construction / Greedy
💡 Signal: “remove k digits”, “smallest subsequence”, “remove duplicates”, build optimal sequence
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Remove K Digits (medium) | increasing stack. Pop when top > current & k > 0 | ||
| 2. Remove Duplicate Letters (medium) | increasing stack + freq count + inStack bool | ||
| 3. Create Maximum Number (hard) | decreasing stack on each array + merge | ||
| 4. Smallest Subsequence of Distinct Characters (medium) | identical to Remove Duplicate Letters | ||
| 5. Maximum Width Ramp (medium) | decreasing stack of candidates for left end |
5.6 Advanced / Tricky
💡 Signal: “132 pattern”, “visible people”, “sliding window maximum”
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. 132 Pattern (medium) | R→L, decreasing stack. Track max popped as “2” | ||
| 2. Number of Visible People in a Queue (hard) | R→L decreasing stack. Count pops + 1 if stack non-empty | ||
| 3. Buildings With an Ocean View (medium) | decreasing stack, remaining elements have view | ||
| 4. Sliding Window Maximum (hard) | monotonic deque (decreasing). pop_front for expiry | ||
| 5. Shortest Subarray with Sum at Least K (hard) | increasing deque on prefix sums | ||
| 6. Max Chunks To Make Sorted II (hard) | increasing stack, merge chunks with max | ||
| 7. Asteroid Collision (medium) | stack simulation. Pop when opposite signs collide | ||
| 8. Car Fleet (medium) | sort by position, decreasing stack on arrival times |