Running state [mp]

Micro pattern¶

Description¶

Update a compact summary after each item so it describes the processed prefix, window, or boundary.

Problems¶

Running optimum¶

Maintain an extendable state and the best result observed.

• 53. Maximum Subarray (Top Easy)
• 121. Best Time to Buy and Sell Stock (Top Easy)
• 55. Jump Game (Top Medium)
• 300. Longest Increasing Subsequence (Top Medium)
• 334. Increasing Triplet Subsequence (Top Medium)
• 152. Maximum Product Subarray (Top Hard)
• 11. Container With Most Water (Top Hard)
• 84. Largest Rectangle in Histogram (Top Hard)
• 673. Number of Longest Increasing Subsequence (Dynamic Programming)
• 1218. Longest Arithmetic Subsequence of Given Difference (Dynamic Programming)
• 354. Russian Doll Envelopes (Dynamic Programming)
• 1964. Find the Longest Valid Obstacle Course at Each Position (Dynamic Programming)

Running window¶

Track validity and the best size of an active interval.

• 3. Longest Substring Without Repeating Characters (Top Medium)
• 904. Fruit Into Baskets (Google Prep)
• 239. Sliding Window Maximum (Top Hard)
• 76. Minimum Window Substring (Top Hard)

Prefix and suffix aggregate¶

Carry an aggregate through a directional pass.

• 238. Product of Array Except Self (Top Hard)
• 315. Count of Smaller Numbers After Self (Top Hard)

Boundary maxima¶

Maintain the strongest observed boundary on each active side.

• 42. Trapping Rain Water (Top Hard)

Streaming parser state¶

Retain the current token, pending operator, and completed aggregate.

• 13. Roman to Integer (Top Easy)
• 227. Basic Calculator II (Top Hard)

Dynamic states¶

Update a fixed collection of semantic states as input arrives.

• 309. Best Time to Buy and Sell Stock with Cooldown (Top Hard)
• 295. Find Median from Data Stream (Top Hard)
• 714. Best Time to Buy and Sell Stock with Transaction Fee (Dynamic Programming)
• 123. Best Time to Buy and Sell Stock III (Dynamic Programming)
• 188. Best Time to Buy and Sell Stock IV (Dynamic Programming)