stack-queue-problems.md

Stack & Queue

General Applications

Problem	Difficulty	Note
844. Backspace String Compare	Easy (1227)
155. Min Stack	Easy	Two stacks for O(1) min.
232. Implement Queue using Stacks	Easy	Flush only when pop is called.
225. Implement Stack using Queues	Easy	Rotation trick to maintain top.
**1472. Design Browser History	Medium (1453)	Doubly linked list.
946. Validate Stack Sequences	Medium (1461)	Be able to pop when peek matches the popped array.
71. Simplify Path	Medium	Handle . and .. and other cases.
636. Exclusive Time of Functions	Medium	A -> B, A lends time to B. A.time -= B.time
**895. Maximum Frequency Stack	Hard (2027)	Bucket of stacks or heap with (freq, index) as state.

• Solved: https://leetcode.com/problems/build-an-array-with-stack-operations/description/ 1180
• Solved: https://leetcode.com/problems/design-a-stack-with-increment-operation/description/ 1285 // Using array + top pointer to simulate stack, should have very clear definition of the top pointer. 2024/10/21
• Solved: https://leetcode.com/problems/baseball-game/description/ // To get previous elements, use stack. 2024/10/21
• Solved: https://leetcode.com/problems/removing-stars-from-a-string/description/ 1347 // Very easy problem, mind the edge case. 2024/10/21

Nested Structure

Problem	Difficulty	Note
150. Evaluate Reverse Polish Notation	Medium
1190. Reverse Substrings Between Each Pair of Parentheses	Medium (1485)
**856. Score of Parentheses	Medium (1562)
**341. Flatten Nested List Iterator	Medium
394. Decode String	Medium	Multi-digit[xyz] patterns.
**1106. Parsing A Boolean Expression	Hard (1880)	Recursion.
726. Number of Atoms	Hard	Merge counts when pop.
**227. Basic Calculator II	Medium	How to handle - at first and flush the last number.
**224. Basic Calculator	Hard

Parentheses

Problem	Difficulty	Note
20. Valid Parentheses	Easy
1614. Maximum Nesting Depth of the Parentheses	Easy (1322)
1021. Remove Outermost Parentheses	Easy (1311)
**921. Minimum Add to Make Parentheses Valid	Medium (1242)
1249. Minimum Remove to Make Valid Parentheses	Medium (1657)
**1541. Minimum Insertions to Balance a Parentheses String	Medium (1759)	Check 2 )), then 1 (.
**678. Valid Parenthesis String	Medium (1700)	Greedy range [min,max].
**1963. Minimum Number of Swaps to Make the String Balanced	Medium (1688)

• https://leetcode.com/problems/remove-invalid-parentheses/description/ h https://leetcode.com/problems/check-if-a-parentheses-string-can-be-valid/description/ 2037

Remove Adjacent Items

Problem	Difficulty
735. Asteroid Collision	Medium
1047. Remove All Adjacent Duplicates In String	Easy (1286)

• https://leetcode.com/problems/make-the-string-great/description/ 1344
• https://leetcode.com/problems/check-if-word-is-valid-after-substitutions/description/ 1426
• https://leetcode.com/problems/minimum-deletions-to-make-array-beautiful/description/ 1510
• https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/description/ 1541
• https://leetcode.com/problems/maximum-score-from-removing-substrings/description/ 1868
• https://leetcode.com/problems/robot-collisions/description/ 2091
• Solved: https://leetcode.com/problems/minimum-string-length-after-removing-substrings 1282 // Easy to solve by stack and learned two pointers approach, 2024/10/30

Monotonic Stack

Basic

Problem	Difficulty
739. Daily Temperatures	Medium
496. Next Greater Element I	Easy
503. Next Greater Element II	Medium
901. Online Stock Span	Medium (1709)

• https://leetcode.com/problems/final-prices-with-a-special-discount-in-a-shop/description/ 1212
• https://leetcode.com/problems/car-fleet/description/ 1678

Advanced (Optional)

Problem	Difficulty

• https://leetcode.com/problems/next-greater-node-in-linked-list/ 1570
• https://leetcode.com/problems/maximum-width-ramp/description/ 1607
• https://leetcode.com/problems/longest-well-performing-interval/description/ 1908
• https://leetcode.com/problems/132-pattern/ 2000
• TODO: 2866. Beautiful Towers II 2071

Rectangle

Problem	Difficulty
42. Trapping Rain Water	Hard
3676. Count Bowl Subarrays	Medium
84. Largest Rectangle in Histogram	Hard
85. Maximal Rectangle	Hard

• https://leetcode.com/problems/maximum-score-of-a-good-subarray/description/ 1945

Contributions

Problem	Difficulty
907. Sum of Subarray Minimums	Medium (1976)
2104. Sum of Subarray Ranges	Medium (2000)

• https://leetcode.com/problems/maximum-subarray-min-product/description/ 2051

Lexicographical

Problem	Difficulty
402. Remove K Digits	Medium (1800)
316. Remove Duplicate Letters	Medium (2184?)

• https://leetcode.com/problems/find-the-most-competitive-subsequence/description/ 1802

Queue Basics

Problem	Difficulty
622. Design Circular Queue	Medium
1823. Find the Winner of the Circular Game	Medium
641. Design Circular Deque	Medium

• https://leetcode.com/problems/number-of-recent-calls/description/ 1337
• https://leetcode.com/problems/reveal-cards-in-increasing-order/description/ 1686
• https://leetcode.com/problems/dota2-senate/description/ m
• https://leetcode.com/problems/design-front-middle-back-queue/description/ 1610

Monotonic Queue

Problem	Difficulty
239. Sliding Window Maximum	Hard

• https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/description/ 1672
• https://leetcode.com/problems/continuous-subarrays/description/ 1940

Explanation

• 155. Min Stack
• 946. Validate Stack Sequences
• 636. Exclusive Time of Functions
• 150. Evaluate Reverse Polish Notation
• 394. Decode String
• 856. Score of Parentheses
• 1106. Parsing A Boolean Expression
• 227. Basic Calculator II
• 224. Basic Calculator
• 921. Minimum Add to Make Parentheses Valid
• 1249. Minimum Remove to Make Valid Parentheses
• 1541. Minimum Insertions to Balance a Parentheses String
• 678. Valid Parenthesis String
• 1963. Minimum Number of Swaps to Make the String Balanced
• 735. Asteroid Collision
• 239. Sliding Window Maximum

TODO: Add more explanation videos for monotonous stack.