Meta VO Interview Question: Maximum Years Until the Start-to-End Path Is Flooded

Given a grid of land heights. For example:

start
6 5 4 5 5
4 2 5 1 1
5 5 2 1 5
2 3 2 4 4
5 4 5 5 6
end

The upper-left corner is the start cell, and the bottom-right corner is the end cell. You may assume that the start and end cells are of equal height and are the highest points in the grid.

Initially, the water level is 0. Due to global warming, the water level increases by 1 every year. A cell is flooded if the water level is greater than or equal to its height.

How many years do we have before there is no longer a path from the start to the end cell?

Example:

S = start, E = end, X = flooded

In 1 year:

S....
...XX
...X.
.....
....E

In 2 years:

S....
.X.XX
..XX.
X.X..
....E

In 3 years:

S....
.X.XX
..XX.
XXX..
....E

Answer: 3

This problem asks for the latest year when a path still exists from the top-left start cell to the bottom-right end cell in a height grid as water rises by 1 each year. The core idea is to view each path by its weakest point: once the water level reaches that critical height, all paths are blocked. A practical solution is to test connectivity for a given year with BFS or DFS, then binary search the answer; alternatively, the problem can be framed as a bottleneck-path or union-find connectivity problem.