dsa2 min read
Decode String [Medium] — Stack-Based Expansion
Decode a run-length-encoded string like "3[a2[bc]]" = "abcbcabcbcabcbc" using a stack for nested brackets.
Read →
Stack
61 articles
dsa2 min read
Daily Temperatures [Medium] — Monotonic Stack
Find how many days until a warmer temperature for each day using a monotonic decreasing stack.
Read →
dsa2 min read
Trapping Rain Water [Hard] — Two Pointers O(n)
Calculate trapped rain water using inward two pointers that track left-max and right-max, replacing the classic O(n) space approach.
Read →
dsa2 min read
Largest Rectangle in Histogram [Hard] — Monotonic Stack
Find the largest rectangle in a histogram in O(n) using a monotonic increasing stack that computes area when a shorter bar is encountered.
Read →
dsa2 min read
Maximal Rectangle [Hard] — Histogram Stack per Row
Find the largest rectangle of 1s in a binary matrix by treating each row as a histogram and applying the Largest Rectangle in Histogram algorithm.
Read →
dsa1 min read
Longest Valid Parentheses [Hard] — Stack / DP
Find the longest valid parentheses substring using a stack that tracks the last unmatched index as a base.
Read →
dsa2 min read
Maximum Frequency Stack [Hard] — Frequency + Group Stacks
Design a stack that pops the most frequent element (breaking ties by recency) using frequency and group-stacks mapping.
Read →
dsa2 min read
Add Two Numbers II — Stack to Handle Forward Order
Add two numbers given in forward order by pushing digits to stacks, then building the result list in reverse.
Read →
dsa2 min read
Flatten Multilevel Doubly Linked List — DFS Stack
Flatten a multilevel doubly linked list by inserting child sub-lists inline using DFS or an explicit stack.
Read →
dsa5 min read
Stacks & Queues — Complete Guide: All Patterns & Problem Index
Master every stack and queue pattern: monotonic stack, BFS, two-stack tricks, deque, and design — with templates and full index of 50 problems.
Read →
dsa2 min read
Valid Parentheses — Stack Bracket Matching
Check if a string of brackets is valid by pushing open brackets and matching close brackets against the stack.
Read →
dsa1 min read
Implement Stack Using Queues — Single Queue Rotation
Implement a stack using one queue by rotating all elements after each push to bring the new element to the front.
Read →
dsa1 min read
Implement Queue Using Stacks — Amortized O(1) Two-Stack
Implement a queue using two stacks with amortized O(1) operations by lazily transferring from inbox to outbox.
Read →
dsa1 min read
Min Stack — Parallel Min Tracking Stack
Design a stack with O(1) getMin by maintaining a parallel min-tracking stack alongside the main stack.
Read →
dsa1 min read
Baseball Game — Stack Simulation
Simulate a baseball scoring game using a stack to track valid scores and handle +, D, and C operations.
Read →
dsa1 min read
Backspace String Compare — Two Pointer O(1) Space
Compare two strings after applying backspace characters in O(1) space by scanning from right with skip counters.
Read →
dsa1 min read
Crawler Log Folder — Stack Depth Counter
Track the minimum number of operations to return to the main folder by simulating directory navigation with a depth counter.
Read →
dsa1 min read
Number of Recent Calls — Sliding Window Queue
Count ping requests within the last 3000ms using a queue that slides expired entries off the front.
Read →
dsa1 min read
Make the String Great — Stack Same-Letter Case Check
Remove adjacent pairs of same letters with different cases using a stack to build the result character by character.
Read →
dsa2 min read
Daily Temperatures — Monotonic Decreasing Stack
Find how many days until a warmer temperature using a monotonic decreasing stack of unresolved day indices.
Read →
dsa1 min read
Next Greater Element I — Monotonic Stack with HashMap
Find the next greater element for each query in O(n+m) using a monotonic stack on nums2 and a lookup map.
Read →
dsa1 min read
Next Greater Element II — Circular Array Monotonic Stack
Find the next greater element in a circular array by iterating twice (0 to 2n) and using a monotonic stack.
Read →
dsa1 min read
Online Stock Span — Monotonic Stack with Accumulated Span
Calculate the stock price span (consecutive days <= today) using a monotonic stack that accumulates spans.
Read →
dsa2 min read
Remove K Digits — Monotonic Increasing Stack
Remove k digits to form the smallest number by maintaining a monotonic increasing stack and greedy removal.
Read →
dsa2 min read
Decode String — Stack for Counts and Strings
Decode a string with nested encodings like 3[a2[bc]] using two stacks: one for counts and one for partial strings.
Read →
dsa1 min read
Evaluate Reverse Polish Notation — Operand Stack
Evaluate an RPN expression by pushing numbers and applying operators to the top two stack elements.
Read →
dsa2 min read
Sliding Window Maximum — Monotonic Deque
Find the maximum in each sliding window of size k using a monotonic decreasing deque storing indices.
Read →
dsa1 min read
Asteroid Collision — Stack Simulation
Simulate asteroid collisions using a stack where right-moving asteroids wait and left-moving ones destroy smaller ones.
Read →
dsa2 min read
Sum of Subarray Minimums — Monotonic Stack with Contribution
Sum the minimums of all subarrays by computing each element's contribution as the minimum using previous and next smaller element spans.
Read →
dsa1 min read
Score of Parentheses — Stack Depth Doubling
Calculate the score of balanced parentheses where () = 1 and AB = A+B and (A) = 2*A using a stack depth trick.
Read →
dsa1 min read
Task Scheduler — Greedy with Most Frequent First
Find the minimum intervals to execute all tasks with cooldown n by greedily scheduling the most frequent task first.
Read →
dsa1 min read
Rotting Oranges — Multi-Source BFS
Find minutes until all oranges rot using multi-source BFS starting from all initially rotten oranges simultaneously.
Read →
dsa1 min read
Number of Islands — BFS or DFS Flood Fill
Count islands in a 2D grid using BFS or DFS to flood-fill connected land cells, marking them visited.
Read →
dsa1 min read
Course Schedule — Topological Sort BFS (Kahns Algorithm)
Detect if all courses can be finished (no cycle) using Kahn's algorithm: BFS on in-degree zero nodes.
Read →
dsa1 min read
Course Schedule II — Topological Order via BFS
Return a valid course order using Kahn's BFS topological sort, or empty array if a cycle exists.
Read →
dsa2 min read
Word Ladder — BFS Shortest Transformation Path
Find the shortest word transformation sequence using BFS where each step changes exactly one character.
Read →
dsa1 min read
Basic Calculator II — Stack with Operator Precedence
Evaluate a string expression with +, -, *, / using a stack that handles operator precedence without parentheses.
Read →
dsa1 min read
132 Pattern — Monotonic Stack from Right
Detect a 132 pattern (i < j < k, nums[i] < nums[k] < nums[j]) using a monotonic stack scanning right to left.
Read →
dsa1 min read
Number of Visible People in Queue — Monotonic Stack
Count visible people in a queue for each person using a monotonic decreasing stack scanning right to left.
Read →
dsa1 min read
Design Circular Queue — Array with Head and Tail Pointers
Implement a circular queue using a fixed-size array with head and tail pointers and a size counter.
Read →
dsa2 min read
Pacific Atlantic Water Flow — Reverse BFS from Both Oceans
Find cells that can flow to both oceans by doing reverse BFS from each ocean's borders and finding the intersection.
Read →
dsa1 min read
Jump Game VI — DP + Monotonic Deque
Maximize score jumping through an array with window k by combining DP with a monotonic decreasing deque.
Read →
dsa1 min read
Shortest Subarray with Sum at Least K — Deque + Prefix Sum
Find the shortest subarray with sum >= k using a monotonic deque on prefix sums for O(n) time.
Read →
dsa1 min read
Walls and Gates — Multi-Source BFS from All Gates
Fill each empty room with its distance to nearest gate using simultaneous multi-source BFS from all gates.
Read →
dsa1 min read
Flatten Nested List Iterator — Stack-Based Lazy Expansion
Implement an iterator for a nested list using a stack that lazily expands nested lists as elements are consumed.
Read →
dsa1 min read
Remove All Adjacent Duplicates in String II — Stack with Counts
Remove k adjacent identical characters repeatedly using a stack that tracks (character, count) pairs.
Read →
dsa1 min read
Design Hit Counter — Queue with Timestamp Expiry
Design a hit counter that returns hits in the past 5 minutes using a queue to expire old timestamps.
Read →
dsa1 min read
Largest Rectangle in Histogram — Monotonic Increasing Stack
Find the largest rectangle in a histogram by computing left and right boundaries using a monotonic increasing stack.
Read →
dsa1 min read
Maximal Rectangle — Histogram Stack on Each Row
Find the maximal rectangle in a binary matrix by building histogram heights row by row and applying largest rectangle.
Read →
dsa2 min read
Basic Calculator I — Stack for Sign and Parentheses
Evaluate a basic expression with +, -, and parentheses using a stack to save and restore sign context.
Read →
dsa2 min read
Maximum Frequency Stack — Bucket-per-Frequency Design
Design a frequency stack with O(1) push and pop-max-frequency using a map of frequency to stack of elements.
Read →
dsa2 min read
Find Median from Data Stream — Two Heaps
Find the median dynamically as numbers are added using two heaps: a max-heap for the lower half and min-heap for upper.
Read →
dsa1 min read
Serialize and Deserialize Binary Tree — BFS Level Order
Serialize a binary tree to a string using BFS level-order and deserialize back using a queue for reconstruction.
Read →
dsa2 min read
Trapping Rain Water — Monotonic Stack Horizontal Layer
Calculate trapped rainwater volume using a monotonic stack that computes water in horizontal layers as bars are processed.
Read →
dsa5 min read
Stacks & Queues Master Recap — All Patterns & Templates
Complete cheatsheet for Stacks & Queues: all 7 patterns, template code, Big O reference, and MAANG interview priority guide.
Read →
dsa2 min read
Binary Search Tree Iterator
Implement an in-order BST iterator with O(h) space using a stack to simulate recursive in-order traversal.
Read →
dsa1 min read
Trapping Rain Water [Hard] — Two Pointer Classic
Calculate trapped rainwater using optimal two-pointer approach that tracks left and right maximums without extra space.
Read →
dsa2 min read
Tarjan's Algorithm — Strongly Connected Components
Find all strongly connected components in a directed graph using Tarjan's single-pass DFS algorithm with discovery time, low-link values, and a stack.
Read →
dsa2 min read
Meta — Flatten Nested List Iterator (Stack-Based)
Implement an iterator for a nested list that flattens it lazily. Meta favors this for testing iterator design, stack usage, and lazy evaluation.
Read →
dsa2 min read
Design Browser History — Stack-Based Navigation
Design a browser with visit, back, and forward navigation. Uses two stacks (or a doubly-ended array with pointer) for O(1) visit and O(steps) navigation.
Read →
dsa2 min read
Design Min Stack — O(1) Minimum with Auxiliary Stack
Implement a stack that supports push, pop, top, and retrieving the minimum element in O(1) time using an auxiliary min-stack that tracks minimums at each level.
Read →