Augment basic data structure [mp]

Micro pattern¶

Description¶

Store extra metadata or combine structures so ordinary operations also maintain information needed for faster queries.

Problems¶

Store aggregate state with each item¶

Attach a summary of the processed state to each stored item.

• 155. Min Stack (Top Easy)
• 84. Largest Rectangle in Histogram (Top Hard)

Store traversal state with each node¶

Pair a node with contextual state needed when it is processed.

• 104. Maximum Depth of Binary Tree (Top Easy)
• 404. Sum of Left Leaves (Google Prep)
• 124. Binary Tree Maximum Path Sum (Top Hard)
• 1376. Time Needed to Inform All Employees (Graph Theory)
• 1192. Critical Connections in a Network (Graph Theory)
• 1926. Nearest Exit from Entrance in Maze (Graph Theory)
• 1091. Shortest Path in Binary Matrix (Graph Theory)
• 864. Shortest Path to Get All Keys (Graph Theory)
• 337. House Robber III (Dynamic Programming)

Combine complementary structures¶

Use structures with different strengths together to support efficient operations.

• 380. Insert Delete GetRandom O(1) (Top Medium)
• 146. LRU Cache (Top Hard)
• 295. Find Median from Data Stream (Top Hard)

Encode multiple states in one value¶

Reserve separate bits or fields for states that must coexist during an update.

• 289. Game of Life (Top Hard)
• 864. Shortest Path to Get All Keys (Graph Theory)