Minimal state [mp]

Micro pattern¶

Description¶

Retain the smallest summary needed for future input instead of the complete history.

Problems¶

Candidate state¶

Keep a bounded collection of candidates and counters.

• 169. Majority Element (Top Medium)
• 229. Majority Element II (Google Prep)

Balance or bounded-window state¶

Track a scalar balance or a bounded collection of active keys.

• 1221. Split a String in Balanced Strings (Google Prep)
• 904. Fruit Into Baskets (Google Prep)
• 76. Minimum Window Substring (Top Hard)

Compressed DP state¶

Replace a table with the previous states required by its recurrence.

• 70. Climbing Stairs (Top Easy)
• 198. House Robber (Top Easy)
• 746. Min Cost Climbing Stairs (Google Prep)
• 152. Maximum Product Subarray (Top Hard)
• 91. Decode Ways (Top Hard)
• 309. Best Time to Buy and Sell Stock with Cooldown (Top Hard)
• 509. Fibonacci Number (Dynamic Programming)
• 1137. N-th Tribonacci Number (Dynamic Programming)
• 740. Delete and Earn (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)
• 790. Domino and Tromino Tiling (Dynamic Programming)

Boundary summaries¶

Keep only the strongest boundary observed from each side.

• 11. Container With Most Water (Top Hard)
• 42. Trapping Rain Water (Top Hard)

Deferred arithmetic state¶

Keep completed totals and only the operands and operator needed for the next update.

• 227. Basic Calculator II (Top Hard)