DSA Sheet - Day 14 Stacks and Queues
🚀 DSA Sheet – Day 14: Stacks & Queues (Part 2)
This section focuses on advanced stack and queue problems like LRU Cache, Min Stack, and monotonic stack patterns used in many interview questions.
📊 Progress Tracker
Progress: 0 / 5 Completed
| Done | Problem | Practice | Level | Companies |
|---|---|---|---|---|
| Time Needed to Buy Tickets | Solve | Easy | Amazon, Microsoft | |
| LRU Cache | Solve | Medium | Amazon, Microsoft, Uber | |
| Get Min from Stack | Solve | Medium | Adobe, Salesforce | |
| Next Smaller Element | Solve | Medium | Amazon, Uber | |
| Celebrity Problem | Solve | Medium | Amazon |
🧠 Key Approaches
- Time Needed: Queue simulation
- LRU Cache: HashMap + Doubly Linked List
- Min Stack: Store minimum at each step
- Next Smaller Element: Monotonic stack
- Celebrity Problem: Elimination using two pointers
⚡ Quick Cheatsheet
LRU Cache (Core Idea)
// Use HashMap + Doubly Linked List
// Maintain recent elements at front
// O(1) get & put operations
Min Stack
stack> st;
// store (value, current_min)
Next Smaller Element
stack st;
for(int i = n - 1; i >= 0; i--){
while(!st.empty() && st.top() >= arr[i])
st.pop();
ans[i] = st.empty() ? -1 : st.top();
st.push(arr[i]);
}
Celebrity Problem
int a = 0, b = n - 1;
while(a < b){
if(knows(a, b))
a++;
else
b--;
}
// verify candidate a
🔥 Pro Tip
Advanced stack problems rely on patterns:
- Monotonic Stack (Next Greater/Smaller)
- Design Problems (LRU Cache, Min Stack)
- Elimination Techniques (Celebrity Problem)