One pass [mp]
Micro pattern¶
Description¶
Produce a result in one ordered scan while maintaining the state needed for the processed prefix.
Problems¶
Maintain an optimum or reachability summary¶
Update the best answer and its supporting summary as each item arrives.
- 121. Best Time to Buy and Sell Stock (Top Easy)
- 53. Maximum Subarray (Top Easy)
- 55. Jump Game (Top Medium)
- 152. Maximum Product Subarray (Top Hard)
- 309. Best Time to Buy and Sell Stock with Cooldown (Top Hard)
- 997. Find the Town Judge (Graph Theory)
- 1557. Minimum Number of Vertices to Reach All Nodes (Graph Theory)
- 1218. Longest Arithmetic Subsequence of Given Difference (Dynamic Programming)
- 714. Best Time to Buy and Sell Stock with Transaction Fee (Dynamic Programming)
- 123. Best Time to Buy and Sell Stock III (Dynamic Programming)
Maintain a window or balance¶
Update an active interval or scalar invariant as input advances.
- 904. Fruit Into Baskets (Google Prep)
- 1221. Split a String in Balanced Strings (Google Prep)
- 239. Sliding Window Maximum (Top Hard)
- 76. Minimum Window Substring (Top Hard)
Merge ordered objects¶
Compare each item with the last merged result.
- 56. Merge Intervals (Top Medium)
Run-length processing¶
Consume each maximal equal-valued run once.
- 38. Count and Say (Top Medium)
Two-ended scan¶
Move an active boundary on every iteration.
- 11. Container With Most Water (Top Hard)
- 42. Trapping Rain Water (Top Hard)
Streaming parsing¶
Finalize a token or term when its delimiter appears.
- 13. Roman to Integer (Top Easy)
- 227. Basic Calculator II (Top Hard)
Monotonic stack scan¶
Resolve candidates when the current value establishes their boundary.
- 84. Largest Rectangle in Histogram (Top Hard)