46 articles
The definitive guide to every stack and queue pattern asked in FAANG interviews — monotonic stack, BFS, two-stack tricks, deque, and design problems with templates and a 50-problem index.
Master the Valid Parentheses problem using a stack to match nested brackets in O(n) time. The canonical LIFO warm-up problem asked at Google, Meta, Amazon, and Microsoft — learn the hash-map trick and every edge case.
Implement a LIFO stack using only queue operations. Learn both the single-queue rotation trick and the two-queue approach — a classic data-structure design problem that tests your understanding of LIFO vs FIFO at FAANG interviews.
Implement a FIFO queue using two stacks with amortized O(1) push and pop. The two-stack lazy-transfer trick is a FAANG interview staple that demonstrates deep understanding of amortized complexity and LIFO vs FIFO semantics.
Design a stack that supports push, pop, top, and getMin in O(1) time using a parallel min-tracking stack. A classic FAANG design interview problem testing stack invariants and auxiliary state maintenance.
Simulate a baseball scoring game using a stack to handle score records, doubles, sum operations, and cancellations in O(n) time. A clean stack-simulation problem that tests your ability to model stateful operations with LIFO access.
Compare two typed strings after applying backspace characters using a stack simulation or O(1) space two-pointer from the right. Covers both approaches with full complexity analysis and FAANG interview tips.
Find the minimum operations to return to the root folder by simulating file system navigation with a stack depth counter in O(n) time and O(1) space. A clean warm-up problem testing stack simulation and boundary conditions.
Count ping requests within the last 3000ms using a FIFO queue that evicts expired timestamps from the front in O(1) amortized time. A clean introduction to the sliding window queue pattern used in rate limiters and real-time counters.
Remove adjacent pairs of same letters with different cases using a stack that processes each character and cancels bad pairs immediately. A clean application of the stack-based adjacent-pair-removal pattern common in FAANG string interviews.
Find how many days until a warmer temperature using a monotonic decreasing stack of unresolved day indices. The canonical monotonic stack problem asked at every FAANG company — master the pattern here and unlock 20+ harder problems.
Find the next greater element for each query using a monotonic stack on nums2 and a hash map lookup in O(n+m) time. A classic application of the monotonic stack pattern combined with hash map lookups for efficient query answering.
Find the next greater element in a circular array by processing 2n indices with modulo indexing and a monotonic stack. The circular variant of the classic monotonic stack pattern — an elegant trick that extends NGE I to handle wrap-around in O(n) time.
Calculate the stock price span using a monotonic decreasing stack that stores (price, span) pairs and accumulates spans in O(1) amortized time. A classic streaming design problem that tests span accumulation and the monotonic stack pattern.
Remove k digits from a number string to form the smallest possible number using a monotonic increasing stack with greedy removal. A key FAANG problem testing greedy thinking, stack manipulation, and edge case handling with leading zeros.
Decode a run-length encoded string with nested brackets like 3[a2[bc]] using two stacks for counts and partial strings. A key FAANG problem testing nested structure parsing with stacks — the same pattern used in expression evaluators and compilers.
Evaluate a Reverse Polish Notation expression by pushing operands and applying operators to the top two stack elements in O(n) time. The canonical stack-based expression evaluation problem asked at Amazon, LinkedIn, and Microsoft.
Find the maximum in every sliding window of size k using a monotonic decreasing deque that maintains candidate indices in O(n) total time. The hardest and most elegant deque problem — mastering this unlocks Shortest Subarray with Sum At Least K and Jump Game VI.
Simulate asteroid collisions where right-moving asteroids accumulate on the stack and left-moving ones destroy smaller ones on collision. A clean application of the collision-simulation stack pattern asked at Amazon and Bloomberg.
Sum the minimum of all subarrays using a monotonic stack to find each element's contribution as the minimum element across all subarrays it dominates. A critical FAANG problem teaching the contribution-counting pattern with monotonic stacks.
Calculate the score of a balanced parentheses string where () = 1 and (A) = 2*A using a stack and an elegant O(1) space depth-doubling trick. A FAANG medium problem that rewards deep thinking with a beautiful bit-shift optimization.
Find the minimum CPU intervals to execute all tasks with cooldown n using a greedy formula based on maximum frequency. A key FAANG problem testing greedy reasoning, frequency counting, and optionally heap-based simulation asked at Amazon, Google, and Facebook.
Solve LeetCode 994 Rotting Oranges step by step using multi-source BFS with a queue. A FAANG interview favorite at Amazon, Google, and Microsoft that teaches level-order traversal, simultaneous infection spread, and grid traversal patterns.
Solve LeetCode 200 Number of Islands using BFS with a queue or DFS with a stack. The most asked grid interview question at Amazon, Google, Meta, and Microsoft, teaching connected components and flood fill.
Solve LeetCode 207 Course Schedule using Kahn algorithm BFS topological sort with a queue and indegree array. A FAANG interview classic at Amazon, Google, and Meta that tests cycle detection in a directed graph.
Solve LeetCode 210 Course Schedule II by returning an actual topological order using Kahn algorithm BFS or DFS with three colors. A FAANG interview classic at Amazon, Google, Meta, and Microsoft.
Solve LeetCode 127 Word Ladder using BFS with a queue and a wildcard pattern map for O(1) neighbor lookups. A FAANG hard at Amazon, Google, Meta, and Microsoft that tests BFS on implicit graphs.
Solve LeetCode 227 Basic Calculator II using a stack to handle operator precedence for plus, minus, multiplication, and division. A FAANG interview classic at Google, Amazon, Meta, and Uber.
Solve LeetCode 456 132 Pattern in O(n) using a monotonic stack scanned from right to left while tracking the best second-largest. A FAANG interview favorite at Bloomberg, Amazon, and Google.
Solve LeetCode 1944 Number of Visible People in a Queue in O(n) using a monotonic decreasing stack. A FAANG hard interview problem at Amazon, Google, and Meta that uses LIFO stack semantics for visibility queries.
Solve LeetCode 622 Design Circular Queue with a fixed-size array and two pointers to achieve O(1) enQueue, deQueue, Front, and Rear. A FAANG interview classic at Amazon, Google, and Meta.
Solve LeetCode 417 Pacific Atlantic Water Flow with reverse BFS from both ocean borders using a deque queue. A FAANG grid traversal classic asked at Amazon, Google, and Meta.
Solve LeetCode 1696 Jump Game VI with a monotonic deque to track the sliding window maximum of DP states in O(n). A high-signal FAANG interview problem.
Solve LeetCode 862 Shortest Subarray with Sum At Least K in O(n) using a monotonic increasing deque on prefix sums. A FAANG hard interview classic.
Solve LeetCode 286 Walls and Gates with multi-source BFS from every gate using a deque queue in O(m times n). A FAANG grid traversal classic.
Solve LeetCode 341 Flatten Nested List Iterator with a lazy stack-based approach in O(1) amortized hasNext and next. A FAANG design favorite at Google, Meta, and Amazon.
Solve LeetCode 1209 Remove All Adjacent Duplicates II in O(n) using a counter stack of (char, count) pairs. A FAANG-favorite stack twist asked at Google and Amazon.
Solve LeetCode 362 Design Hit Counter using a queue or fixed-size circular buffer for O(1) amortized hits and constant-time getHits. A FAANG system design favorite.
Solve LeetCode 84 Largest Rectangle in Histogram in O(n) using a monotonic increasing stack. The single most important monotonic stack interview problem at FAANG.
Solve LeetCode 85 Maximal Rectangle in O(m times n) by reducing each row to a histogram and applying the monotonic stack. A FAANG hard interview classic.
Solve LeetCode 224 Basic Calculator with a single-pass stack approach handling +, -, parentheses, and arbitrary whitespace in O(n). A FAANG hard parsing classic.
Solve LeetCode 895 Maximum Frequency Stack with a layered "stack of stacks" data structure giving O(1) push and pop. A FAANG hard design favorite.
Solve LeetCode 295 Find Median from Data Stream with two heaps (max-heap for low half, min-heap for high half) giving O(log n) addNum and O(1) findMedian. A FAANG streaming classic.
Solve LeetCode 297 Serialize and Deserialize Binary Tree with a BFS queue producing a level-order encoding parsed in O(n). A FAANG hard tree design favorite.
Solve LeetCode 42 Trapping Rain Water in O(n) using a monotonic decreasing stack to fill water layer by layer. The signature FAANG monotonic stack hard problem.
A printable cheatsheet for the entire Stacks and Queues category — seven patterns, ready-to-paste templates, Big-O reference, and a MAANG priority order.