State propagation [mp]
Micro pattern¶
Description¶
Pass information from a position, node, or layer to its dependent successors.
Problems¶
Carry propagation¶
Pass arithmetic overflow to a more significant position.
- 66. Plus One (Top Easy)
- 2. Add Two Numbers (Top Medium)
- 445. Add Two Numbers II (Google Prep)
Tree context propagation¶
Pass bounds, orientation, time, or established links into descendants.
- 98. Validate Binary Search Tree (Top Easy)
- 404. Sum of Left Leaves (Google Prep)
- 116. Populating Next Right Pointers in Each Node (Top Medium)
- 1376. Time Needed to Inform All Employees (Graph Theory)
- 1466. Reorder Routes to Make All Paths Lead to the City Zero (Graph Theory)
Traversal-layer state¶
Propagate direction, distance, or dependency progress to subsequent states.
- 103. Binary Tree Zigzag Level Order Traversal (Top Medium)
- 542. 01 Matrix (Google Prep)
- 207. Course Schedule (Top Hard)
- 210. Course Schedule II (Top Hard)
- 329. Longest Increasing Path in a Matrix (Top Hard)
- 802. Find Eventual Safe States (Graph Theory)
- 1129. Shortest Path with Alternating Colors (Graph Theory)
- 1926. Nearest Exit from Entrance in Maze (Graph Theory)
- 934. Shortest Bridge (Graph Theory)
- 433. Minimum Genetic Mutation (Graph Theory)
- 1091. Shortest Path in Binary Matrix (Graph Theory)
- 864. Shortest Path to Get All Keys (Graph Theory)
- 1203. Sort Items by Groups Respecting Dependencies (Graph Theory)
- 1857. Largest Color Value in a Directed Graph (Graph Theory)
Simultaneous-state updates¶
Derive next states from preserved old values rather than partially updated values.
- 289. Game of Life (Top Hard)
- 309. Best Time to Buy and Sell Stock with Cooldown (Top Hard)
- 714. Best Time to Buy and Sell Stock with Transaction Fee (Dynamic Programming)