Minimum Time Takes to Reach Destination Without Drowning

Minimum Time Takes to Reach Destination Without Drowning

What is this problem about?

The Minimum Time Takes to Reach Destination Without Drowning problem places you on a grid where some cells are dry land, some are already flooded, and flooding spreads outward each minute. You start at a source cell and need to reach a destination cell. You can only move to non-flooded cells, and flooding advances simultaneously. This hard coding problem requires coordinating two BFS processes — the player's movement and water's spread.

Why is this asked in interviews?

Wix asks this hard problem to test the ability to model simultaneous processes on a grid using multi-source BFS. It requires understanding that water's spread is deterministic and can be precomputed, while the player's movement is then validated against the flood timeline. The array, matrix, and BFS interview pattern is the core here, and the problem tests careful state management in two interleaved processes.

Algorithmic pattern used

Multi-source BFS for flood precomputation + single-source BFS for player. First, run a multi-source BFS starting from all initially flooded cells to compute floodTime[i][j] — the time when cell (i,j) gets flooded. Then run BFS for the player from the source: only move to cell (i,j) at time T if T < floodTime[i][j] (cell is still dry when the player arrives). The destination must be reached before it floods.

Example explanation

Grid:

S . . 
. F . 
. . D 

S = start, D = destination, F = initial flood. Flood spreads: at t=1, neighbors of F flood. Precompute flood times. Player BFS: at each step, only move to cells where arrival time < flood time. If player reaches D at time T < floodTime[D], return T. Otherwise return -1.

Common mistakes candidates make

• Running player BFS without precomputing flood times (can't check feasibility).
• Forgetting that the destination itself can flood — must check floodTime[dest] > arrival time.
• Not treating the initial flooded cells as multi-source BFS starting points.
• Checking flood time with ≤ instead of < (player needs to arrive strictly before flooding).

Interview preparation tip

"Simultaneous process" grid problems always precompute the deterministic process first. Here, flooding is deterministic (same result every run), so precompute all flood times in O(n*m). Then the player's BFS becomes a standard shortest-path problem with time-based constraints. Practice recognizing when two processes can be decoupled — precompute one, then solve the other — as this dramatically simplifies implementation and is a common pattern in hard BFS problems.