stack state Pattern
81 problems
Pattern pages help build reusable solving frames. Identify signals first, then explain state, transition, and edge handling.
Recognition Signals
- Look for the candidate's ability to apply stack-based state management to a real-world path traversal problem.
- Assess how well the candidate handles edge cases like empty or root paths and redundant slashes.
- You might be prompted to explain why a naive O(n^2) approach fails for large histograms.
Solve Flow
- 1. Define the active state/window.
- 2. Update state while preserving invariants.
- 3. Validate with edge-heavy examples.
Common Misses
- Forgetting to handle consecutive slashes as a single slash, which can lead to incorrect paths.
- Forgetting to add a sentinel zero-height bar to process remaining stack elements.
- Using float division instead of truncating toward zero, causing wrong integer results.
Recommended Ladder
Simplify Path
Simplify a Unix-style path by transforming it into its canonical form using stack-based state management.
Largest Rectangle in Histogram
Find the maximal rectangular area in a histogram using stack-based state management for precise bar tracking and width c…
Evaluate Reverse Polish Notation
Compute the result of an arithmetic expression in Reverse Polish Notation using a stack to manage operands efficiently.
Min Stack
Design a stack with O(1) operations to push, pop, retrieve the top element, and get the minimum element in constant time…
Basic Calculator
Implement a basic calculator to evaluate mathematical expressions, ensuring correct evaluation with stack-based manageme…
Implement Stack using Queues
This problem tests your ability to simulate a LIFO stack using two queues while preserving all standard stack operations…
Basic Calculator II
Basic Calculator II evaluates a mathematical expression with operators and integers, handling basic arithmetic with prec…
Implement Queue using Stacks
Implement a queue using two stacks, focusing on stack-based state management to achieve FIFO behavior in a queue.
Remove Duplicate Letters
Remove duplicate letters from a string to produce the lexicographically smallest result using stack-based state manageme…
Mini Parser
Deserialize a nested list string using stack-based state management, handling integers and nested lists with depth-first…
Longest Absolute File Path
Find the length of the longest absolute file path in a filesystem string using stack-based depth tracking efficiently.
Decode String
Decode a nested encoded string using stack-based state management, handling repeated patterns efficiently with recursion…
Remove K Digits
Remove K Digits requires selecting which digits to drop using a monotonic stack for the smallest possible integer result…
Next Greater Element II
Solve the Next Greater Element II problem by using a stack-based state management approach for circular arrays.
Tag Validator
The Tag Validator problem involves validating a code snippet by parsing through tags using a stack-based state managemen…
Exclusive Time of Functions
Solve the 'Exclusive Time of Functions' problem using stack-based state management for accurate function execution time …
Baseball Game
Simulate baseball score operations using a stack-based approach to compute the final score after all operations.
Number of Atoms
Compute the exact count of each atom in a chemical formula using stack-based state management and hashing techniques eff…
Asteroid Collision
Determine the final positions of moving asteroids using a stack-based simulation for efficient collision resolution in l…
Parse Lisp Expression
Parse Lisp expressions using stack-based state management to evaluate variables and operations.
Daily Temperatures
In the Daily Temperatures problem, you need to find out how many days to wait for a warmer temperature based on given da…
Max Chunks To Make Sorted II
Determine the maximum number of chunks you can split an array into so that sorting each chunk results in a fully sorted …
Max Chunks To Make Sorted
The Max Chunks To Make Sorted problem requires you to split an array into the maximum number of chunks that can be sorte…
Basic Calculator IV
Simplify mathematical expressions using stack-based state management, handling variables, operators, and polynomial term…
Car Fleet
The Car Fleet problem asks how many car fleets will reach a target given their starting positions and speeds, considerin…
Score of Parentheses
Calculate the score of a balanced parentheses string using stack-based state management for an optimal solution.
Decoded String at Index
Decode the string and find the k-th letter efficiently using stack-based state management in this problem.
Maximum Frequency Stack
Design a stack-like data structure to manage elements and handle frequent stack operations, including popping the most f…
Online Stock Span
Design an efficient algorithm using stacks to calculate the stock span for daily price quotes.
Minimum Add to Make Parentheses Valid
Compute the minimum insertions needed to make a parentheses string valid using efficient stack-based state tracking tech…
Stamping The Sequence
Solve Stamping The Sequence with stack-based state management to convert string s to target using stamp efficiently.
Validate Stack Sequences
Determine if a sequence of push and pop operations can produce the given popped array using a stack-based state approach…
Check If Word Is Valid After Substitutions
Determine if a string can be built from repeated 'abc' insertions using stack-based state management, verifying sequence…
Clumsy Factorial
Compute the clumsy factorial of a number using a fixed rotation of multiply, divide, add, and subtract operations effici…
Remove Outermost Parentheses
Remove Outermost Parentheses simplifies a valid parentheses string by removing the outermost layers of parentheses in ea…
Remove All Adjacent Duplicates In String
Solve Remove All Adjacent Duplicates In String by simulating deletions with a stack that collapses matching neighbors im…
Smallest Subsequence of Distinct Characters
The Smallest Subsequence of Distinct Characters problem asks you to find the lexicographically smallest subsequence of a…
Brace Expansion II
Solve Brace Expansion II efficiently by using stack-based state management to generate all unique combinations of nested…
Parsing A Boolean Expression
Solve the "Parsing A Boolean Expression" problem by evaluating boolean expressions using stack-based state management, r…
Maximum Nesting Depth of Two Valid Parentheses Strings
This problem challenges you to compute the maximum nesting depth of two valid parentheses strings using stack-based stat…
Dinner Plate Stacks
Design a system that manages dinner plate stacks using stack-based state management, handling dynamic plate placement an…
Reverse Substrings Between Each Pair of Parentheses
Reverse all substrings within matched parentheses using a stack-based approach for efficient state tracking and reversal…
Remove All Adjacent Duplicates in String II
Remove all adjacent duplicates in the string using stack-based state management with a given threshold k.
Minimum Remove to Make Valid Parentheses
Given a string with parentheses and letters, remove the fewest parentheses to produce any valid balanced string efficien…
Design a Stack With Increment Operation
Implement a stack that supports push, pop, and targeted increment operations efficiently using array-based state managem…
Build an Array With Stack Operations
Simulate stack operations to match a target array while processing numbers from 1 to n.
Final Prices With a Special Discount in a Shop
Calculate final prices with discounts applied in a shop using a stack-based state management approach to find the correc…
Minimum Insertions to Balance a Parentheses String
Compute the minimum insertions to transform a parentheses string into a balanced string using efficient stack tracking.
Make The String Great
This problem requires removing adjacent characters that cancel each other out, leveraging stack-based state management.
Crawler Log Folder
Simulate folder navigation based on a list of operations to determine the current folder depth.
Maximum Nesting Depth of the Parentheses
Find the maximum nesting depth of parentheses in a valid string using stack-based state management.
Find the Most Competitive Subsequence
Identify the lexicographically smallest subsequence of size k using stack-based greedy selection in array traversal.
Number of Students Unable to Eat Lunch
Simulate a queue of students with sandwich preferences and determine how many can't eat based on available sandwiches.
Maximum Score From Removing Substrings
Compute the highest score by greedily removing specific substrings using a stack to track state transitions efficiently.
Car Fleet II
Car Fleet II involves calculating collision times between cars traveling at different speeds along a one-lane road using…
Maximum Subarray Min-Product
The problem asks to find the maximum min-product of any non-empty subarray of nums.
Remove All Occurrences of a Substring
Remove all occurrences of a specified substring from a string using efficient stack-based state management.
Number of Visible People in a Queue
Compute how many people each person in a queue can see to their right using efficient stack-based state management.
The Number of Weak Characters in the Game
Identify all weak characters in a game by analyzing attack and defense values using a stack-based greedy sorting approac…
Smallest K-Length Subsequence With Occurrences of a Letter
Find the lexicographically smallest subsequence of length k with at least repetition occurrences of a given letter using…
Sum of Subarray Ranges
Compute the total sum of ranges for all contiguous subarrays efficiently using stack-based state management techniques.
Check if a Parentheses String Can Be Valid
Determine if a parentheses string can be transformed into a valid sequence considering locked positions using stack logi…
Replace Non-Coprime Numbers in Array
Replace Non-Coprime Numbers in Array uses stack-based state management to iteratively merge adjacent non-coprime integer…
Count Collisions on a Road
Count Collisions on a Road is a problem where you calculate the number of car collisions based on their movements in a s…
Minimum Deletions to Make Array Beautiful
Determine the minimum deletions required to transform an array into a beautiful sequence using stack-based state managem…
Sum of Total Strength of Wizards
The Sum of Total Strength of Wizards problem asks for the sum of the total strengths of all contiguous subarrays of wiza…
Subarray With Elements Greater Than Varying Threshold
Find the size of a subarray with all elements greater than threshold divided by length using stack-based state managemen…
Construct Smallest Number From DI String
Construct the lexicographically smallest string that fits the increasing and decreasing conditions of a given pattern.
Removing Stars From a String
Remove all stars from a string by simulating the removal process using a stack to manage characters and stars efficientl…
Using a Robot to Print the Lexicographically Smallest String
Solve the problem of using a robot to print the lexicographically smallest string with stack-based state management.
Minimum String Length After Removing Substrings
Determine the smallest string length after repeatedly removing AB or CD substrings using stack-based simulation techniqu…
Robot Collisions
Robot Collisions involves simulating robot movements and handling collisions with stack-based state management.
Apply Operations to Maximize Score
Maximize the score by applying operations on a subarray at most k times, utilizing stack-based state management.
Beautiful Towers I
Solve Beautiful Towers I by testing each peak and enforcing mountain limits with monotonic stack style height propagatio…
Beautiful Towers II
Maximize tower configurations with the stack-based approach while ensuring mountain-like patterns in this medium difficu…
Lexicographically Minimum String After Removing Stars
Find the lexicographically smallest string by removing stars using stack-based state management and careful character se…
Clear Digits
Remove all digits from a given string by applying a repeated operation to form the final string without digits.
Find Mirror Score of a String
Calculate the mirror score of a string using stack-based state management for matching letters efficiently and accuratel…
Maximum and Minimum Sums of at Most Size K Subarrays
Compute the sum of maximum and minimum values in all subarrays up to size k using efficient stack-based state management…
Make Array Non-decreasing
Determine the maximum size of a non-decreasing array by replacing subarrays with their maximum values efficiently.
Resulting String After Adjacent Removals
This problem focuses on removing adjacent characters in a string using a stack-based approach until no more operations a…