2814. Minimum Time Takes to Reach Destination Without Drowning π
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:
- Each second, you can move to an adjacent cell (up, down, left, or right) that shares a side with your current position
- You cannot step on stone cells (
"X"
) - 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:
- First BFS calculates how many seconds it takes for the flood to reach each cell, storing these times in a grid
g
- 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 (checkingg[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:
- First BFS to calculate flood spreading times from all water sources
- 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
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:
-
Direction Movement: The
pairwise(dirs)
withdirs = (-1, 0, 1, 0, -1)
creates pairs representing the 4 directions: up(-1, 0)
, right(0, 1)
, down(1, 0)
, left(0, -1)
. -
Safety Condition:
g[x][y] > t + 1
ensures that when we reach cell(x, y)
at timet + 1
, it won't be flooded yet. The flood must arrive strictly later than our arrival time. -
Level-wise BFS: Both BFS traversals process all cells at the current time level before moving to the next, ensuring we track time accurately.
-
Cell Type Checking:
- Phase 1: Only spreads flood to
"."
and"S"
cells - Phase 2: Only moves to
"."
and"D"
cells
- Phase 1: Only spreads flood to
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 EvaluatorExample 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:
- First maps when each cell floods
- Then searches for a path where we always stay ahead of the flood
- 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:
-
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) takesO(1)
time. -
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 mostO(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:
-
Visited array
vis
: Two 2D boolean arrays of sizem Γ n
, each requiringO(m Γ n)
space (one is reused). -
Distance grid
g
: A 2D array of sizem Γ n
storing the time when fire reaches each cell, requiringO(m Γ n)
space. -
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), requiringO(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.
Consider the classic dynamic programming of longest increasing subsequence:
Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
For example, the length of LIS for [50, 3, 10, 7, 40, 80]
is 4
and LIS is
[3, 7, 40, 80]
.
What is the recurrence relation?
Recommended Readings
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 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 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!