DSA sheet · Stack Pattern wise
Stack DSA Notebook
My study notes from the Stack Pattern wise playlist. Each page is written so that a beginner (or me, after forgetting everything) can read it once and understand why a stack fits, what gets pushed and popped and why, the Python code line by line, and a full dry run with the stack contents drawn after every step.
The one idea behind every page
A stack keeps the most recent unfinished thing on top (last in, first out). Use one whenever the newest item decides what happens to older ones: it cancels them (undo, parentheses), answers them (next greater element), or waits for them (expressions, nesting).
In Python a plain list is the stack:
In Python a plain list is the stack:
append to push, pop() to pop, [-1] to peek. Always check it isn't empty first.Every page follows the same order:
① question in simple words → ② constraints → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ line by line → ⑧ dry run with the stack after every step → ⑨ complexity & remember
Start here
Monotonic stack: next greater / smaller
- 2Next Greater Elementbrute → monotonic
- 3Next Greater Element II (Circular)loop twice
- 4Daily Temperaturesstore indices
- 5Asteroid Collisionsimulate with stack
- 6Largest Rectangle in Histogramprev/next smaller
- 9Maximal Rectanglerows → histograms
Expression evaluation
- 7Basic Calculator IIlast sign
- 8Evaluate Reverse Polish Notationnumbers stack
- 22Decode Stringstack + nesting
Undo pattern: newest cancels the top
- 10Backspace String Comparestack → two pointers
- 11Remove All Adjacent Duplicatesbrute → stack
- 12Make The String Greatbrute → stack
- 13Min Length After Removing Substringsstack
Parentheses
- 14Valid Parenthesesmatch opener
- 15Minimum Add to Make Parentheses Validstack → counters
- 16Score of Parenthesesstack → depth
- 17Longest Valid Parenthesesstack → two passes
- 25Minimum Remove to Make Valid Parenthesesstack + greedy
Design a data structure
- 18Implement Queue using Stacksamortised O(1)
- 19Implement Stack using Queuespush vs pop costly
- 20Min Stackmin in O(1)
- 21Design Stack With Incrementlazy increment
Greedy + stack: smallest result
Numbers are the order in the playlist. "Next →" at the top of each page follows that order.