Stack Patterns in LeetCode Problems (Medium)

Group 1: Basic LIFO & Simulation

This group covers the most fundamental use of a stack: direct simulation. Problems here involve using the Last-In, First-Out (LIFO) property to manage a sequence of operations or build a result based on simple, rule-based state changes. These are the building blocks for all other stack patterns.

#	Problem	Link	Concept	Description of Difficulty Increase
1	Baseball Game	Link	Basic LIFO	Base case. Introduces direct simulation using a stack to manage state according to simple rules (add, invalidate, double).
2	Build an Array with Stack Operations	Link	Basic LIFO	A pure simulation where the stack helps model the process of building the target array step-by-step.
3	Crawler Log Folder	Link	Basic LIFO	Uses a stack to simulate directory depth changes based on commands (`../`, `./`, `x/`).
4	Number of Students Unable to Eat Lunch	Link	Queue/Stack Simulation	While a queue is more direct, a stack can also be used to simulate student preferences. The core is simple state checking.
5	Make the String Great	Link	Stack as a 'Processed' buffer	Introduces using a stack to build a result string by comparing the current character to the last valid character (top of the stack).
6	Remove Outermost Parentheses	Link	Stack for State Tracking	Uses a stack (or a simple counter) to track the depth of parentheses to identify and skip the outermost ones.
7	Backspace String Compare	Link	Stack for String Building	Uses a stack to simulate the effect of backspaces on a string. An optimal solution uses two pointers, but a stack is a very intuitive first approach.
8	Remove All Adjacent Duplicates in String	Link	Stack for String Building	Boring variation of `Make the String Great`. The condition is simpler (equality) but the pattern is identical.

Group 2: Parentheses Validation

Here, we tackle the canonical use case for stacks: validating and balancing parentheses. The LIFO nature of a stack is perfect for matching opening brackets with their corresponding closing brackets. Problems range from simple validation to more complex balancing and scoring.

#	Problem	Link	Concept	Description of Difficulty Increase
9	Maximum Nesting Depth of the Parentheses	Link	Simple State Tracking	Base case. Introduces tracking parenthesis depth, which is the core idea. Can be solved with a simple counter instead of a full stack.
10	Valid Parentheses	Link	Parentheses Matching	The canonical stack problem. Introduces matching opening and closing brackets, requiring the stack's LIFO property.
11	Minimum Add to Make Parentheses Valid	Link	Parentheses Balancing	Builds on validation by requiring you to count the number of mismatches (unmatched open and closed parentheses).
12	Minimum Remove to Make Valid Parentheses	Link	Parentheses Balancing + String Building	Increases complexity by requiring you to not only identify invalid parentheses but also reconstruct the valid string.
13	Score of Parentheses	Link	Stack with State Calculation	Moves from validation to calculation. The stack now stores scores of nested sub-expressions, not just characters.
14	Valid Parenthesis String	Link	Stack with Wildcards	Adds significant complexity with the `*` wildcard, often requiring two stacks or a greedy approach to track the possible range of open parentheses.
15	Minimum Insertions to Balance a Parentheses String	Link	Complex Balancing Rules	The rules for balancing are now more complex (one `(` requires two `)`), demanding more careful state management.

Group 3: The Monotonic Stack (Next/Previous Greater/Smaller Element)

This is a powerful and essential pattern for many medium-to-hard problems. A monotonic stack maintains elements in a sorted order (either increasing or decreasing). It’s used to efficiently find the ‘next greater/smaller’ or ‘previous greater/smaller’ element for every item in an array, which is key to solving problems involving ranges and boundaries.

#	Problem	Link	Concept	Description of Difficulty Increase
16	Final Prices With a Special Discount in a Shop	Link	Monotonic Stack (Increasing)	Base case for monotonic stacks. A very simple application to find the next smaller or equal element for a discount.
17	Next Greater Element I	Link	Monotonic Stack + HashMap	The classic 'Next Greater Element' problem. Introduces using a monotonic stack to pre-calculate results and a map to store them.
18	Daily Temperatures	Link	Monotonic Stack (Decreasing)	A self-contained version of NGE. Instead of values, you store indices on the stack to calculate distances.
19	Next Greater Element II	Link	Monotonic Stack (Circular Array)	Builds on the NGE pattern by requiring a second pass over the array to handle the circular nature.
20	Next Greater Node In Linked List	Link	Monotonic Stack (Linked List)	Applies the exact same monotonic stack logic, but on a linked list instead of an array.
21	Shortest Unsorted Continuous Subarray	Link	Monotonic Stack for Boundaries	A clever application where a monotonic stack is used twice (once forward, once backward) to find the left and right boundaries of the unsorted section.
22	Car Fleet	Link	Monotonic Stack (Abstract)	A creative use of the pattern. After sorting by position, a stack tracks the arrival times of cars to determine how many fleets are formed.
23	Online Stock Span	Link	Monotonic Stack (Online)	The logic is now 'online.' The stack stores pairs of `(price, span)` to efficiently calculate the span for each new day.
24	The Number of Weak Characters in the Game	Link	Monotonic Stack (Abstract)	A tricky problem that becomes a monotonic stack problem after careful sorting. You find 'next greater' on the defense values.
25	132 Pattern	Link	Monotonic Stack (Complex Condition)	A very difficult pattern-matching problem where a monotonic stack is used to efficiently track potential candidates for the `s2` element.
26	Sum of Subarray Minimums	Link	Monotonic Stack (Contribution)	Major conceptual leap. Uses a monotonic stack to find both the previous and next smaller elements for each number, allowing you to calculate its contribution to the total sum.
27	Sum of Subarray Ranges	Link	Monotonic Stack (Contribution)	Boring variation. Reinforces the contribution concept by applying it four times (next/prev smaller, next/prev greater) and combining the results.
28	Maximum Subarray Min-Product	Link	Monotonic Stack + Prefix Sums	Builds directly on `Sum of Subarray Minimums` by combining the boundary-finding technique with prefix sums to calculate subarray sums efficiently.

Group 4: Greedy Stack (Building Optimal Sequences)

These problems use a stack to make greedy choices. By processing elements one by one and using the stack to maintain an ‘optimal-so-far’ result, we can build the best possible sequence (e.g., the lexicographically smallest string). The stack helps us decide whether to keep or discard previous choices based on the current element.

#	Problem	Link	Concept	Description of Difficulty Increase
29	Remove All Adjacent Duplicates in String II	Link	Stack with Counts	Builds on the basic duplicate removal by requiring the stack to store counts along with characters.
30	Remove K Digits	Link	Greedy Monotonic Stack	The canonical greedy stack problem. Uses a stack to build the lexicographically smallest number by greedily removing larger digits from the left.
31	Find the Most Competitive Subsequence	Link	Greedy Monotonic Stack	Boring variation of `Remove K Digits`. The logic is identical but framed as finding a subsequence of a certain length.
32	Remove Duplicate Letters	Link	Greedy Monotonic Stack + State	Adds complexity to the greedy pattern. Requires tracking seen characters and their last positions to ensure the subsequence is complete.
33	Smallest Subsequence of Distinct Characters	Link	Greedy Monotonic Stack + State	Boring variation. This is the exact same problem as `Remove Duplicate Letters`.
34	Maximum Score From Removing Substrings	Link	Greedy Stack (Two Pass)	A greedy approach where a stack-like removal process is applied twice: once for the higher-priority pair, and again on the result for the lower-priority pair.

Group 5: Expression Evaluation & Parsing

Stacks are a natural fit for parsing and evaluating expressions, especially those with nested structures or operator precedence rules. Problems in this group use stacks to manage operands, operators, or intermediate results, effectively simulating a recursive descent parser or a calculation engine.

#	Problem	Link	Concept	Description of Difficulty Increase
35	Evaluate Reverse Polish Notation	Link	Expression Evaluation	Base case. The stack is used to store operands, and operators trigger calculations on the top elements. No precedence rules needed.
36	Simplify Path	Link	Path Parsing	Uses a stack to handle file path components, naturally handling `.` (do nothing) and `..` (pop).
37	Basic Calculator II	Link	Expression Evaluation (Precedence)	Introduces operator precedence. The standard approach uses a stack to hold numbers, processing `*`/`/` immediately and delaying `+`/`-`.
38	Decode String	Link	Recursive Parsing	A classic recursive structure that is perfectly modeled with two stacks: one for numbers (repeat counts) and one for strings being built.
39	Exclusive Time of Functions	Link	Log Parsing	The stack simulates the function call stack. It stores function IDs to calculate execution times when a function ends.
40	Reverse Substrings Between Each Pair of Parentheses	Link	Recursive Parsing	A complex parsing problem. A stack is used to store strings-in-progress. When a `)` is found, the inner string is popped, reversed, and appended.

Group 6: Simulating Recursion (Iterative Tree/List Traversal)

Many recursive algorithms, like tree traversals, rely on an implicit call stack. This group explores how to convert these recursive solutions into iterative ones by using an explicit stack to manage the state. This is a fundamental technique for handling deep recursion or implementing iterators.

#	Problem	Link	Concept	Description of Difficulty Increase
41	Binary Tree Preorder Traversal	Link	Iterative Traversal	Base case. The most direct simulation of recursion. Push right child then left child to process the left first.
42	N-ary Tree Preorder Traversal	Link	Iterative Traversal	Boring variation. Generalizes the preorder traversal to N-ary trees, requiring pushing children in reverse order.
43	Binary Tree Inorder Traversal	Link	Iterative Traversal	More complex than preorder. Requires a loop to push all left children onto the stack before visiting a node.
44	Binary Tree Postorder Traversal	Link	Iterative Traversal	The trickiest of the three. A common solution is a modified preorder traversal (`root, right, left`) which is then reversed.
45	N-ary Tree Postorder Traversal	Link	Iterative Traversal	Boring variation of binary postorder. Applies the same reversed-preorder logic to N-ary children.
46	Increasing Order Search Tree	Link	Iterative Inorder + Restructuring	Uses the standard iterative inorder traversal pattern to visit nodes in order, while simultaneously re-linking them to form the skewed tree.
47	Binary Search Tree Iterator	Link	Lazy Iterative Inorder	A brilliant use of a stack to perform a 'lazy' inorder traversal. The stack holds the path to the next smallest node, and is updated on each `next()` call.
48	Flatten Binary Tree to Linked List	Link	Iterative Preorder + Restructuring	Uses the iterative preorder traversal pattern. As each node is processed, its children are managed on the stack and its pointers are rewired.
49	Flatten Nested List Iterator	Link	Lazy Iterative Traversal (Abstract)	Applies the iterator pattern to a nested list structure. The stack holds iterators, and you 'flatten' lazily by processing the stack until an integer is found.

Group 7: Designing Data Structures

This group focuses on designing new data structures or implementing existing ones using stacks. These problems test your understanding of a stack’s core properties (LIFO) and how they can be combined or manipulated to achieve different behaviors, like FIFO (queues) or tracking a minimum element.

#	Problem	Link	Concept	Description of Difficulty Increase
50	Implement Stack using Queues	Link	Data Structure Design	A classic design problem showing the relationship between LIFO and FIFO structures.
51	Implement Queue using Stacks	Link	Data Structure Design	The inverse of the previous problem. Introduces the concept of an input/output stack and amortization.
52	Min Stack	Link	Data Structure Design	The canonical stack design problem. Requires storing min-so-far state alongside the actual values.
53	Design a Stack with Increment Operation	Link	Data Structure Design	Adds a new requirement (`increment`) that can be solved with a second 'lazy update' stack or array.
54	Design Browser History	Link	Data Structure Design	A straightforward design using two stacks (`history` and `forward`) to manage navigation.

Group 8: Stacks in Complex/Hybrid Algorithms

The final group presents problems where the stack is not the sole solution but a critical component within a more complex algorithm. These hybrid problems combine stacks with other patterns like greedy approaches, dynamic programming, two-pointers, or abstract simulations, showcasing the versatility of the stack as a problem-solving tool.

#	Problem	Link	Concept	Description of Difficulty Increase
55	Palindrome Linked List	Link	Stack for Reversal	A simple, intuitive solution where a stack is used to store the first half of the list, which is then compared against the second half.
56	Add Two Numbers II	Link	Stack for Reversal	Uses stacks to reverse the two linked lists so that numbers can be added from least-significant to most-significant digit.
57	Reorder List	Link	Stack for Reversal	An alternative to the fast/slow pointer solution. A stack holds the second half of the list, allowing you to weave it into the first half.
58	Asteroid Collision	Link	Simulation	A complex simulation problem where the stack perfectly represents the current state of asteroids moving in one direction.
59	Validate Stack Sequences	Link	Simulation	A direct simulation problem. You execute the `pushed` sequence while trying to produce the `popped` sequence.
60	Maximum Binary Tree	Link	Monotonic Stack (Tree Construction)	A clever application where a monotonic stack is used to find the parent (next greater element) for each node, allowing for O(n) tree construction.
61	Construct Binary Search Tree from Preorder Traversal	Link	Stack for Tree Construction	A stack is used to keep track of the parent nodes. The next value in the preorder traversal is attached as a child based on BST properties.
62	Check if Word Is Valid After Substitutions	Link	Stack for Pattern Matching	The stack stores characters. When a `c` is encountered, we check if the stack top is `ab`, effectively reducing the pattern.
63	Verify Preorder Serialization of a Binary Tree	Link	Abstract Stack (Slots)	A clever solution where you use a stack (or a single counter) to track 'available slots' for nodes in the tree.
64	Clumsy Factorial	Link	Expression Evaluation	This is a variation of `Basic Calculator`, but with a fixed, strange pattern of operators. The stack-based evaluation approach works perfectly.
65	Decoded String at Index	Link	Stack-like Logic (Two Pass)	Solved by first finding the total length, then working backward to find the character at index `K`, which mimics a stack's 'undo' behavior.
66	Minimum Deletions to Make String Balanced	Link	Stack-like Logic (Greedy)	Can be solved greedily by processing the string. A stack helps model removing a 'b' when an 'a' appears, representing a 'ba' flip.
67	Minimum Number of Swaps to Make the String Balanced	Link	Stack-like Logic (Counting)	A stack (or a simple counter) is used to find the number of mismatched pairs, which can then be used to calculate the number of swaps.
68	Longest Absolute File Path	Link	Path Parsing with Depth	Uses a stack to store the lengths of parent directories at each depth level, allowing for efficient path length calculation.
69	Minimum Cost Tree From Leaf Values	Link	Monotonic Stack (Greedy)	A notoriously difficult problem with a simple monotonic stack solution. The stack is used to greedily form parent nodes by pairing the smallest adjacent leaves.
70	Max Chunks To Make Sorted	Link	Stack-like Logic (Monotonic)	Can be solved with a monotonic stack. The stack stores the max value of each chunk. A new element is merged until it's greater than the chunk's max.
71	Shortest Subarray to be Removed to Make Array Sorted	Link	Two Pointers (Stack-like properties)	Best solved with two pointers, but the logic has stack-like properties of finding a valid prefix and suffix.
72	Check if a Parentheses String Can Be Valid	Link	Greedy (Two Pass)	A very complex validation problem that is best solved with two greedy passes (left-to-right and right-to-left), not a traditional stack.
73	Longest Well-Performing Interval	Link	Prefix Sum + Monotonic Stack	A difficult problem. It uses a monotonic stack on the prefix sum array to find the longest subarray where `prefix_sum[j] > prefix_sum[i]`.
74	Count Submatrices With All Ones	Link	Monotonic Stack (Histogram)	Conceptual leap. Reduces the problem to `Largest Rectangle in Histogram` for each row, a classic and complex monotonic stack application.
75	Mini Parser	Link	Recursive Parsing	A complex parsing problem similar to `Decode String`, but with a more intricate nested structure that is well-suited for a stack.