Searching from the answer backward

When asking the question from each cell is expensive, ask the opposite question from the edges.

Why it works

Reverse the movement rule too

If moving forward requires going downhill, then searching backward requires going uphill. The rule inverts along with the direction.

Getting that inversion wrong produces a search that runs and returns confidently wrong answers, which is much harder to spot than a crash. Write the forward rule down, then write its reverse explicitly, before coding.

On a real cell the two rules pick out different neighbors, and seeing them side by side is the cheapest way to confirm you have inverted it rather than copied it.

1grid = [[3, 2],2        [4, 5]]3 4row, col = 1, 0                            # standing on the 45neighbors = [(0, 0), (1, 1)]               # the 3 above it and the 5 beside it6 7flows_to = [(r, c) for r, c in neighbors if grid[r][c] <= grid[row][col]]8reached_from = [(r, c) for r, c in neighbors if grid[r][c] >= grid[row][col]]9 10print("water leaves the 4 towards:", flows_to)11print("a backward search from the 4 climbs to:", reached_from)

The two lists are disjoint here, which is the point: forward and backward are not the same walk with the arrows renamed.

Quick check· 5 min

Which rule does the backward search use?

Water flows from a cell to a neighbor whose height is equal or lower. You want every cell from which water can reach the border. Searching outward from the border, what should the neighbor condition be?

Move only to neighbors of equal or greater height, since the search runs against the flowMove only to neighbors of equal or lower height, matching the flow ruleMove to any neighbor, then filter by height afterwardMove only to neighbors of strictly greater height

Problem· 30 min

Pacific Atlantic Water Flow

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Problem· 25 min

Surrounded Regions

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1grid = [[3, 2],2 [4, 5]]3 4row, col = 1, 0 # standing on the 45neighbors = [(0, 0), (1, 1)] # the 3 above it and the 5 beside it6 7flows_to = [(r, c) for r, c in neighbors if grid[r][c] <= grid[row][col]]8reached_from = [(r, c) for r, c in neighbors if grid[r][c] >= grid[row][col]]9 10print("water leaves the 4 towards:", flows_to)11print("a backward search from the 4 climbs to:", reached_from)