Problem Description

You have a grid/matrix with row rows and col columns. Initially (day 0), the entire grid is land (represented by 0). Each day, one cell gets flooded with water (changes from 0 to 1).

You're given an array cells where cells[i] = [ri, ci] tells you that on day i, the cell at row ri and column ci will be flooded with water. Note that all coordinates are 1-based (rows and columns start from 1, not 0).

Your task is to find the last day when you can still walk from any cell in the top row to any cell in the bottom row by only stepping on land cells (cells with value 0). You can move in four directions: up, down, left, and right.

For example:

• If you have a 2×2 grid and cells = [[1,1], [2,1], [1,2], [2,2]]
• Day 0: All cells are land
• Day 1: Cell (1,1) becomes water
• Day 2: Cell (2,1) becomes water
• Day 3: Cell (1,2) becomes water
• Day 4: Cell (2,2) becomes water

You need to determine on which day you can no longer traverse from the top row to the bottom row while staying on land.

The solution uses binary search combined with BFS. Since if you can cross on day k, you can also cross on any earlier day (monotonic property), binary search helps find the maximum day efficiently. For each candidate day mid, the algorithm floods the first mid cells and checks if a path still exists from top to bottom using BFS.

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 problem involves a grid/matrix where we need to find paths. A grid can be viewed as a graph where each cell is a node and adjacent cells are connected by edges.

Is it a tree?

• No: The grid structure is not a tree. It's a general graph that can have multiple paths between nodes and may contain cycles (you can move in 4 directions and potentially return to the same cell).

Is the problem related to directed acyclic graphs?

• No: The grid allows movement in all four directions (bidirectional), and cycles are possible, so it's not a DAG.

Is the problem related to shortest paths?

• No: We're not looking for the shortest path. We just need to determine if ANY path exists from the top row to the bottom row.

Does the problem involve connectivity?

• Yes: The core of the problem is checking connectivity - specifically, whether there exists a connected path from any cell in the top row to any cell in the bottom row through land cells only.

Disjoint Set Union

• While DSU could be used here, the solution uses BFS instead. However, following the flowchart strictly would lead us to DSU.

Alternative Path - Small Constraints:

• Looking at the problem differently, if we consider the search space has manageable constraints (the grid size and number of days to check), we could also arrive at:

Does the problem have small constraints?

• Yes (relatively): While not explicitly small, the binary search reduces the search space significantly.

DFS/backtracking

• Yes: DFS could be used to explore paths from top to bottom row. The solution uses BFS, but DFS would work equally well for checking connectivity.

Conclusion: The flowchart suggests using either DSU for connectivity or DFS/backtracking for path exploration. The actual solution combines binary search with BFS (which is interchangeable with DFS for this connectivity check). DFS would traverse the land cells recursively to determine if a path exists from top to bottom row.

Intuition

The key insight is recognizing the monotonic property of this problem. If you can walk from top to bottom on day k, you can definitely walk on any earlier day because fewer cells would be flooded. Conversely, if you cannot walk on day k, you cannot walk on any later day either because more cells will be flooded.

This monotonic behavior immediately suggests binary search. Instead of checking every single day sequentially (which would be inefficient), we can use binary search to find the exact turning point - the last day when crossing is still possible.

Think of it like this: imagine you're watching a time-lapse video of an island slowly sinking into the ocean. At first, there are many paths from north to south. As more land floods each day, paths start disappearing. Eventually, there comes a specific day when the last possible path gets cut off. We want to find that exact day.

For any given day mid, we need to check if a path exists. We do this by:

1. Flooding all cells that should be water by day mid (the first mid cells from the cells array)
2. Checking if we can still traverse from top to bottom

The traversal check is a classic graph connectivity problem. We can use either DFS or BFS to explore from any starting cell in the top row and see if we can reach any cell in the bottom row. The solution uses BFS, but DFS would work equally well.

The binary search bounds are straightforward:

• Minimum: day 1 (we know day 0 always works since everything is land)
• Maximum: total number of cells (worst case, all cells get flooded)

By combining binary search with path-finding (BFS/DFS), we efficiently find the answer in O(row × col × log(row × col)) time instead of checking every single day sequentially.

Learn more about Depth-First Search, Breadth-First Search, Union Find and Binary Search patterns.

Solution Approach

The solution implements binary search combined with BFS to find the last day we can cross from top to bottom.

Binary Search Setup:

• Initialize search bounds: l = 1 (left) and r = row * col (right)
• We search for the maximum day k where crossing is still possible
• Use the variant mid = (l + r + 1) >> 1 to avoid infinite loops when l and r are adjacent

The Check Function: For each candidate day k, we need to verify if crossing is possible:

1. Build the grid state at day k:

   • Create a 2D grid g initialized with all 0s (land)
   • Mark the first k cells from cells array as water (1)
   • Convert 1-based coordinates to 0-based: g[i-1][j-1] = 1

2. BFS from top row:

   • Initialize queue q with all land cells from the top row: (0, j) where g[0][j] == 0
   • These are all possible starting points

3. BFS exploration:

   • For each cell (x, y) in the queue:
     • Check if we've reached the bottom row: if x == row - 1: return True
     • Explore all 4 directions using dirs = (-1, 0, 1, 0, -1) pattern
     • The pairwise(dirs) generates pairs: (-1, 0), (0, 1), (1, 0), (0, -1) representing up, right, down, left
     • For each valid neighbor that's still land:
       • Add to queue: q.append((nx, ny))
       • Mark as visited by setting g[nx][ny] = 1 (prevents revisiting)

4. Return result:

   • If we reach bottom row during BFS: return True
   • If BFS completes without reaching bottom: return False

Binary Search Logic:

• If check(mid) returns True: we can still cross on day mid
  • Update l = mid (search for a later day)
• If check(mid) returns False: we cannot cross on day mid
  • Update r = mid - 1 (search for an earlier day)
• Continue until l == r, which gives us the last valid day

Time Complexity: O(row × col × log(row × col))

• Binary search iterations: O(log(row × col))
• Each check function: O(row × col) for BFS traversal

Space Complexity: O(row × col) for the grid and BFS queue

Example Walkthrough

Let's walk through a small example with a 3×3 grid and cells = [[1,2], [2,2], [3,2], [1,1], [3,3]].

Initial Setup:

• Grid dimensions: 3 rows × 3 columns
• Binary search bounds: l = 1, r = 9 (though we only have 5 cells to flood)
• We'll search for the last day we can walk from row 1 to row 3

Binary Search Iteration 1:

• mid = (1 + 9 + 1) >> 1 = 5
• Check if we can cross on day 5 (all 5 cells flooded)
• Flood cells: [1,2], [2,2], [3,2], [1,1], [3,3]
• Grid state after flooding:

  1 1 0
  0 1 0  
  0 1 1

• BFS from top row: Start from (0,2) - the only land cell in top row
• BFS explores: (0,2) → cannot reach any neighbors that lead to bottom
• Result: Cannot cross! Update r = mid - 1 = 4

Binary Search Iteration 2:

• mid = (1 + 4 + 1) >> 1 = 3
• Check if we can cross on day 3 (first 3 cells flooded)
• Flood cells: [1,2], [2,2], [3,2]
• Grid state:

  0 1 0
  0 1 0
  0 1 0

• BFS from top row: Start from (0,0) and (0,2)
• From (0,0): explore (0,0) → (1,0) → (2,0) - reached bottom row!
• Result: Can cross! Update l = mid = 3

Binary Search Iteration 3:

• mid = (3 + 4 + 1) >> 1 = 4
• Check if we can cross on day 4 (first 4 cells flooded)
• Flood cells: [1,2], [2,2], [3,2], [1,1]
• Grid state:

  1 1 0
  0 1 0
  0 1 0

• BFS from top row: Start from (0,2)
• From (0,2): explore (0,2) → (1,2) is water, cannot proceed
• Try going around: no valid path to bottom exists
• Result: Cannot cross! Update r = mid - 1 = 3

Final Result:

• l == r == 3
• The last day we can cross from top to bottom is day 3

This demonstrates how binary search efficiently narrows down the answer by checking strategic midpoints rather than testing every single day sequentially.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n × log(m × n))

The algorithm uses binary search on the range [1, m × n], which requires O(log(m × n)) iterations. For each binary search iteration, the check function is called, which performs a BFS traversal on an m × n grid. The BFS visits each cell at most once, taking O(m × n) time. Therefore, the overall time complexity is O(m × n × log(m × n)).

Space Complexity: O(m × n)

The space complexity is dominated by:

• The grid g created in the check function: O(m × n)
• The queue q used for BFS, which in the worst case can contain all cells: O(m × n)
• The cells array is given as input and not counted in auxiliary space

Therefore, the total space complexity is O(m × n).

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

Common Pitfalls

1. Off-by-One Error in Binary Search

The most critical pitfall is using the wrong binary search formula when searching for the maximum valid value. Using mid = (left + right) // 2 instead of mid = (left + right + 1) // 2 causes an infinite loop.

Why it happens:

• When left = k and right = k + 1, using floor division gives mid = k
• If can_cross(k) returns True, we set left = k (unchanged)
• This creates an infinite loop since the bounds never converge

Solution: Always use mid = (left + right + 1) // 2 when:

• Searching for maximum valid value
• Updating with left = mid when condition is met

2. Coordinate System Confusion (1-based vs 0-based)

The problem provides 1-based coordinates in the cells array, but Python arrays are 0-based. Forgetting to convert leads to IndexError or wrong cells being flooded.

Incorrect:

grid[r][c] = 1  # Direct use of 1-based coordinates

Correct:

grid[r - 1][c - 1] = 1  # Convert to 0-based

3. Inefficient BFS Implementation

Using collections.deque with popleft() or list with pop(0) creates unnecessary overhead.

Less efficient:

from collections import deque
queue = deque()
while queue:
    x, y = queue.popleft()  # O(1) but with deque overhead

More efficient for this problem:

queue = []
idx = 0
while idx < len(queue):
    x, y = queue[idx]
    idx += 1  # Simple index advancement, no removal needed

4. Not Marking Cells as Visited Immediately

Marking cells as visited only after dequeuing (instead of when enqueuing) can cause the same cell to be added multiple times, leading to TLE.

Incorrect:

while queue:
    x, y = queue[idx]
    grid[x][y] = 1  # Mark visited after dequeuing - TOO LATE!
    for dx, dy in directions:
        if valid and grid[nx][ny] == 0:
            queue.append((nx, ny))

Correct:

for dx, dy in directions:
    if valid and grid[nx][ny] == 0:
        queue.append((nx, ny))
        grid[nx][ny] = 1  # Mark visited immediately when enqueuing

5. Binary Search Bounds Initialization

Starting with left = 0 instead of left = 1 wastes an iteration since day 0 means no cells are flooded (always crossable).

Suboptimal:

left, right = 0, row * col

Optimal:

left, right = 1, row * col