Facebook Pixel

2814. Minimum Time Takes to Reach Destination Without Drowning 🔒

HardBreadth-First SearchArrayMatrix
Leetcode Link

Problem Description

You are given an n * m grid representing a land map where you need to navigate from a starting position "S" to a destination "D". The grid contains different types of cells:

  • "." - Empty cells that you can walk through
  • "X" - Stone cells that block your path
  • "*" - Flooded cells filled with water
  • "S" - Your starting position
  • "D" - Your destination

The movement rules are:

  1. Each second, you can move to an adjacent cell (up, down, left, or right) that shares a side with your current position
  2. You cannot step on stone cells ("X")
  3. You cannot step on flooded cells ("*") as you will drown

The flooding mechanic works as follows:

  • At each second, the flood spreads - every empty cell (".") that is adjacent to a flooded cell ("*") becomes flooded
  • The flooding and your movement happen simultaneously, so you cannot step on a cell that gets flooded at the same time you try to move there

Your goal is to find the minimum time in seconds to reach the destination cell "D" from the starting cell "S". If it's impossible to reach the destination, return -1.

The problem guarantees that the destination cell will never be flooded.

The solution uses a two-phase BFS approach:

  1. First BFS calculates how many seconds it takes for the flood to reach each cell, storing these times in a grid g
  2. Second BFS finds the shortest path from "S" to "D", only allowing movement to cells where the flood arrives later than when you would reach that cell (checking g[x][y] > t + 1)

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

  • Yes: The grid can be viewed as a graph where each cell is a node and adjacent cells are connected by edges. We need to find a path from source "S" to destination "D".

Is it a tree?

  • No: The grid structure is not a tree - it contains cycles and multiple paths between cells.

Is the problem related to directed acyclic graphs?

  • No: The grid allows bidirectional movement and contains cycles.

Is the problem related to shortest paths?

  • Yes: We need to find the minimum time (shortest path) to reach from "S" to "D".

Is the graph Weighted?

  • No: Each move takes exactly 1 second (unit weight). All edges have the same weight.

BFS

  • Yes: Since we have an unweighted graph shortest path problem, BFS is the appropriate algorithm.

Conclusion: The flowchart correctly leads us to use BFS for this problem. In fact, the solution uses two BFS traversals:

  1. First BFS to calculate flood spreading times from all water sources
  2. Second BFS to find the shortest path from "S" to "D" while avoiding cells that flood before or at the same time we reach them

The BFS pattern is perfect here because:

  • We explore cells level by level (second by second)
  • Each move has the same cost (1 second)
  • We need the minimum time, which BFS guarantees for unweighted graphs
Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is that we're dealing with two independent spreading processes happening simultaneously - our movement and the flood spreading. Both happen at the same rate (1 cell per second), but they start from different positions.

Think of it like this: imagine you're trying to escape a building while water is flooding it. You need to know which rooms will be flooded and when, so you can plan a route that avoids those rooms.

The critical observation is that we can't just find any path to the destination - we need a path where we always stay ahead of the flood. This means for each cell we want to step on at time t, the flood must not reach that cell until time t+1 or later.

This naturally leads to a two-phase approach:

Phase 1: Map the flood timeline We need to know when each cell gets flooded. Since flood spreads uniformly from all water sources at the same rate (1 cell per second), we can use BFS from all flood sources simultaneously. This gives us a "flood map" where g[i][j] tells us at what second cell (i, j) gets flooded.

Phase 2: Find a safe path Now we can search for the shortest path from "S" to "D", but with an additional constraint: we can only move to cell (x, y) at time t if g[x][y] > t. The condition g[x][y] > t + 1 in the code accounts for the fact that we're moving to that cell at time t + 1.

Why BFS for both phases? Because:

  • Flood spreads uniformly (same speed in all directions) → BFS naturally models this
  • We want the shortest path in an unweighted grid → BFS gives optimal solution
  • Both processes happen in discrete time steps → BFS explores level by level, matching the second-by-second progression

The beauty of this approach is that by pre-computing the flood times, we transform a complex simultaneous process into a simple pathfinding problem with an additional time constraint.

Learn more about Breadth-First Search patterns.

Solution Approach

The implementation follows the two-phase BFS approach outlined in the reference solution:

Phase 1: Calculate Flood Spreading Times

First, we initialize the flood timing grid g with infinity values and collect all initial flood sources:

g = [[inf] * n for _ in range(m)]  # Flood time for each cell
q = deque()  # Queue for BFS
vis = [[False] * n for _ in range(m)]  # Visited cells

# Find all flood sources and starting position
for i, row in enumerate(land):
    for j, c in enumerate(row):
        if c == "*":
            q.append((i, j))  # Add flood sources to queue
        elif c == "S":
            si, sj = i, j  # Record starting position

We perform multi-source BFS from all flood cells simultaneously:

t = 0  # Current time
dirs = (-1, 0, 1, 0, -1)  # Direction vectors for 4-directional movement

while q:
    for _ in range(len(q)):  # Process all cells at current time level
        i, j = q.popleft()
        g[i][j] = t  # Record when this cell gets flooded
      
        # Check all 4 adjacent cells
        for a, b in pairwise(dirs):  # Creates pairs: (-1,0), (0,1), (1,0), (0,-1)
            x, y = i + a, j + b
            if (0 <= x < m and 0 <= y < n  # Within bounds
                and not vis[x][y]           # Not visited
                and land[x][y] in ".S"):     # Can be flooded (empty or start)
                vis[x][y] = True
                q.append((x, y))
    t += 1  # Increment time for next level

Phase 2: Find Shortest Safe Path

Now we perform BFS from the starting position to find the shortest path to destination:

t = 0
q = deque([(si, sj)])  # Start from S
vis = [[False] * n for _ in range(m)]  # Reset visited array
vis[si][sj] = True

while q:
    for _ in range(len(q)):  # Process all cells reachable at time t
        i, j = q.popleft()
      
        if land[i][j] == "D":  # Found destination
            return t
      
        # Try all 4 directions
        for a, b in pairwise(dirs):
            x, y = i + a, j + b
            if (0 <= x < m and 0 <= y < n     # Within bounds
                and g[x][y] > t + 1            # Won't be flooded when we arrive
                and not vis[x][y]              # Not visited
                and land[x][y] in ".D"):       # Can walk (empty or destination)
                vis[x][y] = True
                q.append((x, y))
    t += 1  # Increment time for next move

return -1  # No path found

Key Implementation Details:

  1. Direction Movement: The pairwise(dirs) with dirs = (-1, 0, 1, 0, -1) creates pairs representing the 4 directions: up (-1, 0), right (0, 1), down (1, 0), left (0, -1).

  2. Safety Condition: g[x][y] > t + 1 ensures that when we reach cell (x, y) at time t + 1, it won't be flooded yet. The flood must arrive strictly later than our arrival time.

  3. Level-wise BFS: Both BFS traversals process all cells at the current time level before moving to the next, ensuring we track time accurately.

  4. Cell Type Checking:

    • Phase 1: Only spreads flood to "." and "S" cells
    • Phase 2: Only moves to "." and "D" cells

The time complexity is O(m * n) for each BFS traversal, resulting in O(m * n) overall. The space complexity is also O(m * n) for the grids and queues.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach:

Grid (4x4):
. . * .
. S . .
. X . D
. . . .

Phase 1: Calculate Flood Spreading Times

We start by finding all flood sources (*) and performing multi-source BFS:

Initial state (t=0):

  • Queue: [(0,2)]
  • Flood times grid g:
∞  ∞  0  ∞
∞  ∞  ∞  ∞
∞  X  ∞  ∞
∞  ∞  ∞  ∞

t=1: Flood spreads to adjacent cells from (0,2)

  • Process (0,2) → spreads to (0,1), (0,3), (1,2)
  • Queue: [(0,1), (0,3), (1,2)]
  • Flood times grid g:
∞  1  0  1
∞  ∞  1  ∞
∞  X  ∞  ∞
∞  ∞  ∞  ∞

t=2: Continue spreading

  • Process (0,1), (0,3), (1,2) → spreads to (0,0), (1,1), (2,2)
  • Note: Can't spread through stone X at (2,1)
  • Queue: [(0,0), (1,1), (2,2)]
  • Flood times grid g:
2  1  0  1
∞  2  1  ∞
∞  X  2  ∞
∞  ∞  ∞  ∞

t=3: Continue spreading

  • Process (0,0), (1,1), (2,2) → spreads to (1,0), (2,0), (3,2), (2,3)
  • Queue: [(1,0), (2,0), (3,2), (2,3)]
  • Flood times grid g:
2  1  0  1
3  2  1  ∞
3  X  2  3
∞  ∞  3  ∞

Final flood times after complete BFS:

2  1  0  1
3  2  1  2
3  X  2  3
4  4  3  4

Phase 2: Find Shortest Safe Path

Now we search from S (1,1) to D (2,3), checking flood times:

t=0: Start at S (1,1)

  • Queue: [(1,1)]
  • Current position has flood time g[1][1] = 2

t=1: Move from (1,1)

  • Check adjacent cells:
    • (0,1): g[0][1] = 1, but 1 ≤ 1 (would flood when we arrive) → Can't go
    • (1,0): g[1][0] = 3 > 1+1 = 2 → Safe, add to queue
    • (1,2): g[1][2] = 1, but 1 ≤ 1 → Can't go
    • (2,1): Stone X → Can't go
  • Queue: [(1,0)]

t=2: Move from (1,0)

  • Check adjacent cells:
    • (0,0): g[0][0] = 2, but 2 ≤ 2+1 = 3 → Can't go (floods at same time)
    • (2,0): g[2][0] = 3, but 3 ≤ 2+1 = 3 → Can't go (floods at same time)
    • (1,1): Already visited
  • Queue: [] (empty)

Since we can't reach D, let's try a different path analysis:

Actually, let me recalculate more carefully. From S at (1,1):

t=0: At S (1,1), flood arrives at time 2

t=1: Can move to:

  • (1,0): flood time 3 > 1 ✓
  • (1,2): flood time 1 ≤ 1 ✗
  • (0,1): flood time 1 ≤ 1 ✗

t=2: From (1,0), can move to:

  • (2,0): flood time 3 > 2 ✓
  • (0,0): flood time 2 ≤ 2 ✗

t=3: From (2,0), can move to:

  • (3,0): flood time 4 > 3 ✓

t=4: From (3,0), can move to:

  • (3,1): flood time 4 ≤ 4 ✗

The player gets stuck and cannot reach D. The flooding spreads too quickly, blocking all safe paths.

Result: -1 (impossible to reach destination)

This example demonstrates how the algorithm:

  1. First maps when each cell floods
  2. Then searches for a path where we always stay ahead of the flood
  3. Returns -1 when no safe path exists

Solution Implementation

1from collections import deque
2from math import inf
3from itertools import pairwise
4from typing import List
5
6class Solution:
7    def minimumSeconds(self, land: List[List[str]]) -> int:
8        rows, cols = len(land), len(land[0])
9      
10        # Initialize fire spread time grid and visited matrix for first BFS
11        fire_time = [[inf] * cols for _ in range(rows)]
12        visited_fire = [[False] * cols for _ in range(rows)]
13      
14        # Queue for BFS and variables for start position
15        fire_queue = deque()
16        start_row = start_col = 0
17      
18        # Find all fire sources (*) and the starting position (S)
19        for row in range(rows):
20            for col in range(cols):
21                cell = land[row][col]
22                if cell == "*":
23                    # Add fire sources to queue
24                    fire_queue.append((row, col))
25                    visited_fire[row][col] = True
26                elif cell == "S":
27                    # Record starting position
28                    start_row, start_col = row, col
29      
30        # Direction vectors for 4-directional movement (up, right, down, left)
31        directions = (-1, 0, 1, 0, -1)
32      
33        # First BFS: Calculate fire spread times
34        time = 0
35        while fire_queue:
36            # Process all cells at current time level
37            for _ in range(len(fire_queue)):
38                curr_row, curr_col = fire_queue.popleft()
39                fire_time[curr_row][curr_col] = time
40              
41                # Check all 4 adjacent cells
42                for dr, dc in pairwise(directions):
43                    next_row, next_col = curr_row + dr, curr_col + dc
44                  
45                    # Add valid unvisited cells that can catch fire
46                    if (0 <= next_row < rows and 
47                        0 <= next_col < cols and 
48                        not visited_fire[next_row][next_col] and 
49                        land[next_row][next_col] in ".S"):
50                        visited_fire[next_row][next_col] = True
51                        fire_queue.append((next_row, next_col))
52            time += 1
53      
54        # Second BFS: Find shortest path from S to D avoiding fire
55        time = 0
56        path_queue = deque([(start_row, start_col)])
57        visited_path = [[False] * cols for _ in range(rows)]
58        visited_path[start_row][start_col] = True
59      
60        while path_queue:
61            # Process all cells at current distance level
62            for _ in range(len(path_queue)):
63                curr_row, curr_col = path_queue.popleft()
64              
65                # Check if we reached the destination
66                if land[curr_row][curr_col] == "D":
67                    return time
68              
69                # Check all 4 adjacent cells
70                for dr, dc in pairwise(directions):
71                    next_row, next_col = curr_row + dr, curr_col + dc
72                  
73                    # Add valid cells that are safe from fire at time+1
74                    if (0 <= next_row < rows and 
75                        0 <= next_col < cols and 
76                        fire_time[next_row][next_col] > time + 1 and 
77                        not visited_path[next_row][next_col] and 
78                        land[next_row][next_col] in ".D"):
79                        visited_path[next_row][next_col] = True
80                        path_queue.append((next_row, next_col))
81            time += 1
82      
83        # No path found to destination
84        return -1
85
1class Solution {
2    public int minimumSeconds(List<List<String>> land) {
3        // Get grid dimensions
4        int rows = land.size();
5        int cols = land.get(0).size();
6      
7        // Track visited cells for BFS
8        boolean[][] visited = new boolean[rows][cols];
9      
10        // Store the time when fire reaches each cell
11        int[][] fireTime = new int[rows][cols];
12      
13        // Queue for BFS
14        Deque<int[]> queue = new ArrayDeque<>();
15      
16        // Starting position coordinates
17        int startRow = 0, startCol = 0;
18      
19        // Initialize grid and find fire sources (*) and start position (S)
20        for (int i = 0; i < rows; ++i) {
21            // Initialize all cells with maximum time (unreachable by fire)
22            Arrays.fill(fireTime[i], 1 << 30);
23          
24            for (int j = 0; j < cols; ++j) {
25                String cell = land.get(i).get(j);
26              
27                if ("*".equals(cell)) {
28                    // Add fire source to queue
29                    queue.offer(new int[] {i, j});
30                } else if ("S".equals(cell)) {
31                    // Record starting position
32                    startRow = i;
33                    startCol = j;
34                }
35            }
36        }
37      
38        // Direction vectors for 4-directional movement (up, right, down, left)
39        int[] directions = {-1, 0, 1, 0, -1};
40      
41        // First BFS: Calculate fire spread times
42        for (int time = 0; !queue.isEmpty(); ++time) {
43            int levelSize = queue.size();
44          
45            for (int k = 0; k < levelSize; ++k) {
46                int[] current = queue.poll();
47                int row = current[0];
48                int col = current[1];
49              
50                // Set the time when fire reaches this cell
51                fireTime[row][col] = time;
52              
53                // Explore all 4 adjacent cells
54                for (int d = 0; d < 4; ++d) {
55                    int nextRow = row + directions[d];
56                    int nextCol = col + directions[d + 1];
57                  
58                    // Check if next position is valid and not visited
59                    if (nextRow >= 0 && nextRow < rows && 
60                        nextCol >= 0 && nextCol < cols && 
61                        !visited[nextRow][nextCol]) {
62                      
63                        String nextCell = land.get(nextRow).get(nextCol);
64                        boolean isEmpty = ".".equals(nextCell);
65                        boolean isStart = "S".equals(nextCell);
66                      
67                        // Fire can spread to empty cells and start position
68                        if (isEmpty || isStart) {
69                            visited[nextRow][nextCol] = true;
70                            queue.offer(new int[] {nextRow, nextCol});
71                        }
72                    }
73                }
74            }
75        }
76      
77        // Second BFS: Find path from start to destination avoiding fire
78        queue.offer(new int[] {startRow, startCol});
79        visited = new boolean[rows][cols];  // Reset visited array
80        visited[startRow][startCol] = true;
81      
82        for (int time = 0; !queue.isEmpty(); ++time) {
83            int levelSize = queue.size();
84          
85            for (int k = 0; k < levelSize; ++k) {
86                int[] current = queue.poll();
87                int row = current[0];
88                int col = current[1];
89              
90                // Check if we reached the destination
91                if ("D".equals(land.get(row).get(col))) {
92                    return time;
93                }
94              
95                // Explore all 4 adjacent cells
96                for (int d = 0; d < 4; ++d) {
97                    int nextRow = row + directions[d];
98                    int nextCol = col + directions[d + 1];
99                  
100                    // Check if next position is valid, not visited, and safe from fire
101                    if (nextRow >= 0 && nextRow < rows && 
102                        nextCol >= 0 && nextCol < cols && 
103                        !visited[nextRow][nextCol] && 
104                        fireTime[nextRow][nextCol] > time + 1) {
105                      
106                        String nextCell = land.get(nextRow).get(nextCol);
107                        boolean isEmpty = ".".equals(nextCell);
108                        boolean isDestination = "D".equals(nextCell);
109                      
110                        // Can move to empty cells or destination
111                        if (isEmpty || isDestination) {
112                            visited[nextRow][nextCol] = true;
113                            queue.offer(new int[] {nextRow, nextCol});
114                        }
115                    }
116                }
117            }
118        }
119      
120        // No path found to destination
121        return -1;
122    }
123}
124
1class Solution {
2public:
3    int minimumSeconds(vector<vector<string>>& land) {
4        int rows = land.size();
5        int cols = land[0].size();
6      
7        // Track visited cells for BFS traversals
8        bool visited[rows][cols];
9        // Store the time when fire reaches each cell
10        int fireTime[rows][cols];
11      
12        // Initialize arrays
13        memset(visited, false, sizeof(visited));
14        memset(fireTime, 0x3f, sizeof(fireTime));  // Set to large value (infinity)
15      
16        queue<pair<int, int>> bfsQueue;
17        int startRow = 0, startCol = 0;
18      
19        // Find all fire sources (*) and the starting position (S)
20        for (int i = 0; i < rows; ++i) {
21            for (int j = 0; j < cols; ++j) {
22                string cell = land[i][j];
23                if (cell == "*") {
24                    // Add fire source to queue for multi-source BFS
25                    bfsQueue.emplace(i, j);
26                } else if (cell == "S") {
27                    // Record starting position
28                    startRow = i;
29                    startCol = j;
30                }
31            }
32        }
33      
34        // Direction vectors for 4-directional movement (up, right, down, left)
35        int directions[5] = {-1, 0, 1, 0, -1};
36      
37        // First BFS: Calculate fire spread time to each cell
38        for (int time = 0; !bfsQueue.empty(); ++time) {
39            int currentLevelSize = bfsQueue.size();
40          
41            for (int k = 0; k < currentLevelSize; ++k) {
42                auto [currentRow, currentCol] = bfsQueue.front();
43                bfsQueue.pop();
44              
45                // Record the time fire reaches this cell
46                fireTime[currentRow][currentCol] = time;
47              
48                // Explore all 4 adjacent cells
49                for (int dir = 0; dir < 4; ++dir) {
50                    int nextRow = currentRow + directions[dir];
51                    int nextCol = currentCol + directions[dir + 1];
52                  
53                    // Check if next cell is within bounds and not visited
54                    if (nextRow >= 0 && nextRow < rows && 
55                        nextCol >= 0 && nextCol < cols && 
56                        !visited[nextRow][nextCol]) {
57                      
58                        // Fire can spread to empty cells (.) and start position (S)
59                        bool isEmptyCell = land[nextRow][nextCol] == ".";
60                        bool isStartCell = land[nextRow][nextCol] == "S";
61                      
62                        if (isEmptyCell || isStartCell) {
63                            visited[nextRow][nextCol] = true;
64                            bfsQueue.emplace(nextRow, nextCol);
65                        }
66                    }
67                }
68            }
69        }
70      
71        // Second BFS: Find shortest path from S to D avoiding fire
72        bfsQueue.emplace(startRow, startCol);
73        memset(visited, false, sizeof(visited));
74        visited[startRow][startCol] = true;
75      
76        for (int time = 0; !bfsQueue.empty(); ++time) {
77            int currentLevelSize = bfsQueue.size();
78          
79            for (int k = 0; k < currentLevelSize; ++k) {
80                auto [currentRow, currentCol] = bfsQueue.front();
81                bfsQueue.pop();
82              
83                // Check if we reached the destination
84                if (land[currentRow][currentCol] == "D") {
85                    return time;
86                }
87              
88                // Explore all 4 adjacent cells
89                for (int dir = 0; dir < 4; ++dir) {
90                    int nextRow = currentRow + directions[dir];
91                    int nextCol = currentCol + directions[dir + 1];
92                  
93                    // Check if next cell is valid and safe from fire
94                    if (nextRow >= 0 && nextRow < rows && 
95                        nextCol >= 0 && nextCol < cols && 
96                        !visited[nextRow][nextCol] && 
97                        fireTime[nextRow][nextCol] > time + 1) {  // Can reach before fire
98                      
99                        // Can move to empty cells (.) and destination (D)
100                        bool isEmptyCell = land[nextRow][nextCol] == ".";
101                        bool isDestCell = land[nextRow][nextCol] == "D";
102                      
103                        if (isEmptyCell || isDestCell) {
104                            visited[nextRow][nextCol] = true;
105                            bfsQueue.emplace(nextRow, nextCol);
106                        }
107                    }
108                }
109            }
110        }
111      
112        // No valid path found
113        return -1;
114    }
115};
116
1/**
2 * Finds the minimum seconds needed to reach destination while avoiding spreading hazards
3 * @param land - 2D grid where '*' is hazard source, 'S' is start, 'D' is destination, '.' is empty
4 * @returns Minimum seconds to reach destination, or -1 if impossible
5 */
6function minimumSeconds(land: string[][]): number {
7    const rows = land.length;
8    const cols = land[0].length;
9  
10    // Initialize grid to track when each cell becomes dangerous (hazard arrival time)
11    const hazardTimeGrid: number[][] = Array(rows)
12        .fill(0)
13        .map(() => Array(cols).fill(1 << 30)); // Initialize with large value
14  
15    // Track visited cells for BFS
16    const visited: boolean[][] = Array(rows)
17        .fill(0)
18        .map(() => Array(cols).fill(false));
19  
20    const queue: number[][] = [];
21    let startRow = 0;
22    let startCol = 0;
23  
24    // Find all hazard sources ('*') and starting position ('S')
25    for (let row = 0; row < rows; row++) {
26        for (let col = 0; col < cols; col++) {
27            const cell = land[row][col];
28            if (cell === '*') {
29                // Add hazard sources to queue for multi-source BFS
30                queue.push([row, col]);
31            } else if (cell === 'S') {
32                // Record starting position
33                startRow = row;
34                startCol = col;
35            }
36        }
37    }
38  
39    // Direction vectors for 4-directional movement (up, right, down, left)
40    const directions = [-1, 0, 1, 0, -1];
41  
42    // First BFS: Calculate hazard spread times from all hazard sources
43    let time = 0;
44    while (queue.length > 0) {
45        const levelSize = queue.length;
46      
47        // Process all cells at current time level
48        for (let i = 0; i < levelSize; i++) {
49            const [currentRow, currentCol] = queue.shift()!;
50            hazardTimeGrid[currentRow][currentCol] = time;
51          
52            // Check all 4 adjacent cells
53            for (let dir = 0; dir < 4; dir++) {
54                const nextRow = currentRow + directions[dir];
55                const nextCol = currentCol + directions[dir + 1];
56              
57                // Check bounds and if cell is visitable and not yet visited
58                if (nextRow >= 0 && nextRow < rows && 
59                    nextCol >= 0 && nextCol < cols && 
60                    !visited[nextRow][nextCol] && 
61                    'S.'.includes(land[nextRow][nextCol])) {
62                  
63                    visited[nextRow][nextCol] = true;
64                    queue.push([nextRow, nextCol]);
65                }
66            }
67        }
68        time++;
69    }
70  
71    // Reset for second BFS: Find path from start to destination
72    queue.push([startRow, startCol]);
73  
74    // Reset visited array for path finding
75    for (let row = 0; row < rows; row++) {
76        visited[row].fill(false);
77    }
78    visited[startRow][startCol] = true;
79  
80    // Second BFS: Find shortest safe path from start to destination
81    time = 0;
82    while (queue.length > 0) {
83        const levelSize = queue.length;
84      
85        // Process all cells at current time level
86        for (let i = 0; i < levelSize; i++) {
87            const [currentRow, currentCol] = queue.shift()!;
88          
89            // Check if we reached the destination
90            if (land[currentRow][currentCol] === 'D') {
91                return time;
92            }
93          
94            // Explore all 4 adjacent cells
95            for (let dir = 0; dir < 4; dir++) {
96                const nextRow = currentRow + directions[dir];
97                const nextCol = currentCol + directions[dir + 1];
98              
99                // Check if next cell is valid:
100                // - Within bounds
101                // - Not visited
102                // - We can arrive before hazard spreads there
103                // - Cell is either destination or empty space
104                if (nextRow >= 0 && nextRow < rows && 
105                    nextCol >= 0 && nextCol < cols && 
106                    !visited[nextRow][nextCol] && 
107                    hazardTimeGrid[nextRow][nextCol] > time + 1 && 
108                    'D.'.includes(land[nextRow][nextCol])) {
109                  
110                    visited[nextRow][nextCol] = true;
111                    queue.push([nextRow, nextCol]);
112                }
113            }
114        }
115        time++;
116    }
117  
118    // No path found to destination
119    return -1;
120}
121

Time and Space Complexity

Time Complexity: O(m × n)

The algorithm consists of two separate BFS traversals:

  1. First BFS (from fire sources "*"): Each cell in the grid is visited at most once. The BFS processes all reachable cells from fire sources, which in the worst case is O(m × n) cells. Each cell operation (marking distance, checking neighbors) takes O(1) time.

  2. Second BFS (from start position "S"): Similarly, each cell is visited at most once during the search for destination "D". The BFS processes cells while checking the fire spread constraint g[x][y] > t + 1, visiting at most O(m × n) cells.

Since both BFS operations visit each cell at most once and perform constant-time operations per cell, the total time complexity is O(m × n) + O(m × n) = O(m × n).

Space Complexity: O(m × n)

The algorithm uses the following data structures:

  1. Visited array vis: Two 2D boolean arrays of size m × n, each requiring O(m × n) space (one is reused).

  2. Distance grid g: A 2D array of size m × n storing the time when fire reaches each cell, requiring O(m × n) space.

  3. Queue q: In the worst case, the BFS queue can contain all cells simultaneously (e.g., when all cells are fire sources or all cells are reachable), requiring O(m × n) space.

The total space complexity is O(m × n) + O(m × n) + O(m × n) = O(m × n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Flood Timing Comparison

One of the most common mistakes is using the wrong comparison operator when checking if a cell is safe to move to. The condition fire_time[next_row][next_col] > time + 1 is critical.

Incorrect Implementation:

# Wrong: Using >= instead of >
if fire_time[next_row][next_col] >= time + 1:
    # This allows movement to cells that get flooded at the same time

Why it's wrong: The flood and your movement happen simultaneously. If the fire reaches a cell at time t and you also reach it at time t, you will drown. You need the fire to arrive strictly later than your arrival time.

Correct Implementation:

# Correct: Fire must arrive strictly after we do
if fire_time[next_row][next_col] > time + 1:
    # Safe to move here

2. Not Handling Starting Position Already Flooded

Another pitfall is not checking if the starting position itself is adjacent to flood cells, which would make escape impossible.

Solution: Add a check after the first BFS:

# After calculating fire spread times
if fire_time[start_row][start_col] <= 0:
    return -1  # Starting position floods immediately

3. Forgetting to Mark Starting Cell as Visitable by Fire

When identifying which cells can be flooded, forgetting to include "S" in the valid cells list causes incorrect fire spread calculation.

Incorrect:

# Wrong: Only checking for empty cells
if land[next_row][next_col] == ".":
    # Fire can't spread to starting position

Correct:

# Correct: Fire can spread to both empty cells and starting position
if land[next_row][next_col] in ".S":
    # Fire spreads correctly

4. Using Single BFS Instead of Two-Phase Approach

Attempting to handle both fire spread and pathfinding in a single BFS leads to incorrect results because you need to know all fire timings before planning your route.

Why Two-Phase is Necessary:

  • Phase 1 pre-computes when each cell becomes dangerous
  • Phase 2 uses this complete information to find a safe path
  • Single-phase approach can't look ahead to know future fire positions

5. Incorrect Queue Initialization for Fire Sources

Forgetting to mark initial fire cells as visited before adding them to the queue can cause them to be processed multiple times.

Incorrect:

for row in range(rows):
    for col in range(cols):
        if land[row][col] == "*":
            fire_queue.append((row, col))
            # Forgot: visited_fire[row][col] = True

Correct:

for row in range(rows):
    for col in range(cols):
        if land[row][col] == "*":
            fire_queue.append((row, col))
            visited_fire[row][col] = True  # Mark as visited immediately

These pitfalls can cause the algorithm to either find incorrect paths, miss valid paths, or get stuck in infinite loops. Careful attention to the simultaneous nature of flooding and movement is key to solving this problem correctly.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

Recommended Readings

BFS Fundamentals

https assets algo monster cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell Breadth First Search BFS

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More