Reverse search [mp]

Micro pattern¶

Description¶

Search from targets, endpoints, or known-safe states toward possible origins.

Problems¶

Search outward from all targets¶

Treat every target as an initial source and propagate distances.

• 542. 01 Matrix (Google Prep)

Search from both endpoints¶

Expand source and target frontiers until they meet.

• 127. Word Ladder (Top Hard)

Search the safe complement¶

Start at protected boundaries and identify their reachable region.

• 130. Surrounded Regions (Top Hard)
• 1020. Number of Enclaves (Graph Theory)
• 1254. Number of Closed Islands (Graph Theory)
• 417. Pacific Atlantic Water Flow (Graph Theory)

Search from dependency sources¶

Start with states having no remaining dependencies and propagate availability.

• 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)