Skip to main content
Talentd

Minimum Time Takes to Reach Destination Without Drowning - Solution & Explanation

HardPremiumFree on FleetCodeArrayBreadth-First SearchMatrix10 min read
Practice this problem

Problem Statement

You are given an n * m 0-indexed grid of string land. Right now, you are standing at the cell that contains "S", and you want to get to the cell containing "D". There are three other types of cells in this land:

  • ".": These cells are empty.
  • "X": These cells are stone.
  • "*": These cells are flooded.

At each second, you can move to a cell that shares a side with your current cell (if it exists). Also, at each second, every empty cell that shares a side with a flooded cell becomes flooded as well.
There are two problems ahead of your journey:

  • You can't step on stone cells.
  • You can't step on flooded cells since you will drown (also, you can't step on a cell that will be flooded at the same time as you step on it).

Return the minimum time it takes you to reach the destination in seconds, or -1 if it is impossible.

Note that the destination will never be flooded.

 

Example 1:

Input: land = [["D",".","*"],[".",".","."],[".","S","."]]
Output: 3
Explanation: The picture below shows the simulation of the land second by second. The blue cells are flooded, and the gray cells are stone.
Picture (0) shows the initial state and picture (3) shows the final state when we reach destination. As you see, it takes us 3 second to reach destination and the answer would be 3.
It can be shown that 3 is the minimum time needed to reach from S to D.

Example 2:

Input: land = [["D","X","*"],[".",".","."],[".",".","S"]]
Output: -1
Explanation: The picture below shows the simulation of the land second by second. The blue cells are flooded, and the gray cells are stone.
Picture (0) shows the initial state. As you see, no matter which paths we choose, we will drown at the 3rd second. Also the minimum path takes us 4 seconds to reach from S to D.
So the answer would be -1.

Example 3:

Input: land = [["D",".",".",".","*","."],[".","X",".","X",".","."],[".",".",".",".","S","."]]
Output: 6
Explanation: It can be shown that we can reach destination in 6 seconds. Also it can be shown that 6 is the minimum seconds one need to reach from S to D.

 

Constraints:

  • 2 <= n, m <= 100
  • land consists only of "S", "D", ".", "*" and "X".
  • Exactly one of the cells is equal to "S".
  • Exactly one of the cells is equal to "D".

Approach Overview

Problem Overview: You are given a grid where water spreads every minute and certain cells are blocked. Starting from the source, you must reach the destination before water reaches the same cell. The goal is to compute the minimum time required to safely reach the destination without stepping into flooded cells.

Approach 1: Brute Force Time Simulation with BFS (O((m*n)^2) time, O(m*n) space)

Simulate the grid minute by minute. At each minute, expand all water cells to adjacent positions, then run a BFS from the player's current frontier to explore reachable cells. If water reaches a cell before or at the same time as the player, that path becomes invalid. This method repeatedly recomputes reachable states while the grid changes, which causes heavy redundant work. It helps understand the interaction between flood spread and path movement but quickly becomes inefficient on larger matrix inputs.

Approach 2: Binary Search + BFS Feasibility Check (O(m*n log(m*n)) time, O(m*n) space)

Instead of simulating every minute, treat the waiting time before starting as a decision problem. Binary search the maximum safe delay and run a BFS feasibility check for each candidate delay. During the BFS, ensure the player only enters cells strictly before water arrives. This separates path validation from flood expansion and reduces repeated simulation, but still requires multiple traversals of the grid. It works well when you want to reason about safe starting delays but is not the simplest implementation.

Approach 3: Two BFS Traversals (O(m*n) time, O(m*n) space)

The optimal strategy computes water arrival times first, then performs a second BFS for the player. Start a multi-source breadth-first search from every water cell simultaneously to build a grid waterTime[r][c] representing the earliest minute water floods each cell. Next, run another BFS from the start position. When exploring neighbors, only move into a cell if the arrival time of the player is strictly less than waterTime for that cell. This guarantees the player never steps into water or arrives simultaneously with it. Each cell is processed at most once in both traversals, giving linear complexity relative to the grid size.

The key insight is separating the two processes: compute flood timing once, then treat it as a constraint during pathfinding. This transforms a dynamic environment into a deterministic shortest-path problem over a grid array.

Recommended for interviews: The two-BFS approach is what interviewers typically expect. It shows you understand multi-source BFS and how to precompute environmental constraints. Mentioning the brute force simulation demonstrates problem exploration, but implementing the linear-time two-pass BFS solution shows strong algorithmic thinking.

Solution

First, we run a BFS (Breadth-First Search) to calculate the shortest distance from each cell to the water, and record it in the array g. Then, we run another BFS starting from the cell (s_i, s_j) to find the shortest distance to the target cell (d_i, d_j). During this process, if the adjacent cell (x, y) of the current cell (i, j) satisfies g[x][y] > t + 1, then we can move from (x, y) to (i, j).

The time complexity is O(m times n) and the space complexity is O(m times n). Where m and n are the number of rows and columns of the array land, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Simulation + BFSO((m*n)^2)O(m*n)Conceptual approach to understand how flood expansion interacts with path traversal
Binary Search + BFS CheckO(m*n log(m*n))O(m*n)Useful when modeling the problem as a maximum safe waiting time before starting
Two BFS TraversalsO(m*n)O(m*n)Optimal approach. Precompute water arrival times and run BFS for the player once

Video Solution

leetcode 2814. Minimum Time Takes to Reach Destination Without Drowning - BFS • Code-Yao • 369 views views

Frequently Asked Questions

Is Minimum Time Takes to Reach Destination Without Drowning easy or hard?
The problem is rated Hard because it combines multiple BFS concepts. You must model environmental changes over time, compute water spread with multi-source BFS, and then enforce those constraints during pathfinding. Managing timing conditions correctly is the main challenge.
Minimum Time Takes to Reach Destination Without Drowning Python/Java solution
Implement two BFS passes. First compute water arrival times using a queue seeded with all water cells. Then perform BFS from the start cell while checking that the player's time is less than the stored water time. This logic translates cleanly to Python, Java, C++, Go, and TypeScript using standard queue-based BFS.
How to solve Minimum Time Takes to Reach Destination Without Drowning in O(m*n)?
Run a multi-source BFS from all water cells to compute when water floods each position. Store these times in a grid. Then run a second BFS from the start cell and move only if the player's arrival time is strictly less than the water arrival time. This ensures every move stays ahead of the flood while exploring the grid only once.
What is the best approach for Minimum Time Takes to Reach Destination Without Drowning?
The most efficient approach uses two BFS traversals. The first multi-source BFS computes the earliest time water reaches each cell. The second BFS starts from the player's position and only moves into cells where the player arrives strictly before the water. This approach runs in O(m*n) time and O(m*n) space.
Is Minimum Time Takes to Reach Destination Without Drowning asked at Google/Amazon/Meta?
Grid BFS problems with spreading constraints frequently appear in interviews at companies like Amazon, Google, and Meta. Variants include problems where fire spreads, zombies infect cells, or water floods terrain. The core pattern is multi-source BFS combined with shortest path traversal.
What data structure is used in Minimum Time Takes to Reach Destination Without Drowning?
The main data structure is a queue used for breadth-first search. Two BFS traversals are performed: one multi-source queue for water expansion and another queue for the player's movement. A matrix is used to store the earliest water arrival time for each cell.
What is the time complexity of Minimum Time Takes to Reach Destination Without Drowning?
The optimal solution runs in O(m*n) time where m and n are the grid dimensions. One BFS computes water arrival times and another BFS finds the shortest safe path for the player. Each cell is processed at most once per traversal, so the total work is linear in the number of cells.

Ready to solve this problem?

Practice Minimum Time Takes to Reach Destination Without Drowning with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays