DSA Sheet - Day 15 Stacks and Queues
🚀 DSA Sheet – Day 15: Stacks & Queues (Part 3)
This section introduces BFS-based problems, greedy strategies, and advanced stack patterns. These are frequently asked in product-based companies.
📊 Progress Tracker
Progress: 0 / 5 Completed
| Done | Problem | Practice | Level | Companies |
|---|---|---|---|---|
| Rotten Oranges | Solve | Medium | Meta, Flipkart | |
| Sort a Stack | Solve | Medium | Amazon, Microsoft | |
| Stock Span | Solve | Medium | Amazon, Adobe | |
| Gas Station (Circular Tour) | Solve | Medium | Cisco, Infosys | |
| Largest Rectangle in Histogram | Solve | Hard | Amazon, Microsoft |
🧠 Key Approaches
- Rotten Oranges: Multi-source BFS
- Sort Stack: Recursion + insert in sorted order
- Stock Span: Monotonic stack
- Gas Station: Greedy + prefix sum logic
- Largest Rectangle: Monotonic stack (area calculation)
⚡ Quick Cheatsheet
Rotten Oranges (BFS)
queue> q;
// push all rotten oranges first
while(!q.empty()){
// BFS level traversal
// spread infection
}
Stock Span
stack> st;
// store {price, span}
Gas Station
int total = 0, curr = 0, start = 0;
for(int i = 0; i < n; i++){
total += gas[i] - cost[i];
curr += gas[i] - cost[i];
if(curr < 0){
start = i + 1;
curr = 0;
}
}
// if total >= 0 → answer exists
Largest Rectangle in Histogram
// use monotonic stack
// calculate width using previous smaller elements
🔥 Pro Tip
These problems combine multiple concepts:
- BFS (graph-like thinking)
- Greedy decisions (Gas Station)
- Stack patterns (Stock Span, Histogram)