You are given a 1-based binary matrix where 0 represents land and 1 represents water. You are given integers row
and col
representing the number of rows and columns in the matrix, respectively.
Initially on day 0, the entire matrix is land. However, each day a new cell becomes flooded with water. You are given a 1-based 2D array cells
, where cells[i] = [r_i, c_i]
represents that on the ith day, the cell on the r_ith row and c_ith column will be covered with water.
You want to find the last day that it is possible to walk from the top to the bottom by only walking on land cells. You can start from any cell in the top row and end at any cell in the bottom row. You can only travel in the four cardinal directions (left, right, up, and down).
For example:
row = 2
, col = 2
, and cells = [[1,1],[2,1],[1,2],[2,2]]
, the output should be 2.row = 2
, col = 2
, and cells = [[1,1],[1,2],[2,1],[2,2]]
, the output should be 1.row = 3
, col = 3
, and cells = [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]]
, the output should be 3.Could you provide an algorithm to efficiently solve this problem, considering the constraints 2 <= row, col <= 2 * 10^4
, 4 <= row * col <= 2 * 10^4
, cells.length == row * col
, 1 <= r_i <= row
, 1 <= c_i <= col
, and all values in cells are unique?
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The brute force approach involves checking every single day to see if a path exists from the top to the bottom of the grid without touching water. We simulate the submersion process day by day and for each day, we check if crossing is still possible.
Here's how the algorithm would work step-by-step:
def last_day_to_cross_brute_force(row, col, cells):
last_possible_day = 0
for day in range(1, len(cells) + 1):
flooded_grid = [[0] * col for _ in range(row)]
# Simulate flooding the grid up to the current day
for current_day in range(day):
current_row, current_col = cells[current_day][0] - 1, cells[current_day][1] - 1
flooded_grid[current_row][current_col] = 1
# Check if a path exists on the current day
if can_cross(flooded_grid):
last_possible_day = day
return last_possible_day
def can_cross(flooded_grid):
row = len(flooded_grid)
col = len(flooded_grid[0])
# Start from the top row and try to find a path to the bottom.
for start_col in range(col):
if flooded_grid[0][start_col] == 0:
visited = [[False] * col for _ in range(row)]
if depth_first_search(flooded_grid, 0, start_col, visited):
return True
return False
def depth_first_search(flooded_grid, current_row, current_col, visited):
row = len(flooded_grid)
col = len(flooded_grid[0])
# If we reached the bottom row, we can cross
if current_row == row - 1:
return True
# Check boundaries and if the cell is flooded or already visited.
if current_row < 0 or current_row >= row or current_col < 0 or current_col >= col or \
flooded_grid[current_row][current_col] == 1 or visited[current_row][current_col]:
return False
visited[current_row][current_col] = True
# Explore all four possible directions.
if depth_first_search(flooded_grid, current_row + 1, current_col, visited):
return True
if depth_first_search(flooded_grid, current_row - 1, current_col, visited):
return True
if depth_first_search(flooded_grid, current_row, current_col + 1, visited):
return True
if depth_first_search(flooded_grid, current_row, current_col - 1, visited):
return True
return False
The best way to solve this is to use a technique that lets us efficiently check if we can cross the grid up to a certain day. Instead of checking each day individually, we will use a method to quickly narrow down the possibilities.
Here's how the algorithm would work step-by-step:
def last_day_to_cross(row, col, cells):
left = 1
right = len(cells)
def can_cross(day):
grid = [[0] * col for _ in range(row)]
for i in range(day):
row_index, col_index = cells[i]
grid[row_index - 1][col_index - 1] = 1
queue = []
visited = set()
for column_index in range(col):
if grid[0][column_index] == 0:
queue.append((0, column_index))
visited.add((0, column_index))
while queue:
current_row, current_col = queue.pop(0)
if current_row == row - 1:
return True
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for delta_row, delta_col in directions:
new_row = current_row + delta_row
new_col = current_col + delta_col
if 0 <= new_row < row and 0 <= new_col < col and \
grid[new_row][new_col] == 0 and (new_row, new_col) not in visited:
queue.append((new_row, new_col))
visited.add((new_row, new_col))
return False
answer = 0
while left <= right:
middle = (left + right) // 2
# Check if a path exists up to day 'middle'.
if can_cross(middle):
# If a path exists, try a later day
answer = middle
left = middle + 1
# If no path exists, try an earlier day.
else:
right = middle - 1
# Return the last day a path existed.
return answer
Case | How to Handle |
---|---|
Null or empty grid input (rows or cols = 0) | Return -1 immediately, as crossing is impossible with an invalid grid. |
Grid is 1x1 | If the first cell is flooded on day 1, return 0; otherwise, return the last day. |
All cells are flooded on day 1 | Return 0, since the crossing is blocked from the very beginning. |
No path can ever be formed to cross the grid | Binary search will converge to the last day of the cells array. |
Maximum grid size (large rows and cols values) | Ensure that the DFS or BFS used within the binary search does not exceed memory or time limits by optimizing data structures and search strategies. |
Integer overflow when calculating cell indices | Use appropriate data types (e.g., long) to prevent integer overflow when mapping row and col to a 1D index. |
Cells array contains invalid row/col combinations (out of bounds) | Filter out invalid cells from the input array or add checks during cell processing to prevent array index out of bounds errors. |
The last cell in 'cells' is part of a path | The algorithm must still correctly validate this path exists before that last cell appears. |