In-place marking [mp]

Micro pattern¶

Description¶

Replace input values with markers to avoid a separate visited or metadata structure.

Problems¶

Metadata markers¶

Reserve positions or bits to record a later transformation.

• 73. Set Matrix Zeroes (Top Medium)
• 289. Game of Life (Top Hard)

Backtracking-path markers¶

Mark a cell during one path and restore it afterward.

• 79. Word Search (Top Medium)
• 212. Word Search II (Top Hard)

Permanent component markers¶

Overwrite visited cells when their original value is no longer needed.

• 200. Number of Islands (Top Medium)
• 1926. Nearest Exit from Entrance in Maze (Graph Theory)
• 934. Shortest Bridge (Graph Theory)
• 1091. Shortest Path in Binary Matrix (Graph Theory)
• 695. Max Area of Island (Graph Theory)

Protected-complement markers¶

Mark boundary-connected cells before processing their unmarked complement.

• 130. Surrounded Regions (Top Hard)
• 1020. Number of Enclaves (Graph Theory)
• 1254. Number of Closed Islands (Graph Theory)