LeetCode 1970 Solution Explained Step by Step

At first glance, LeetCode 1970 looks intimidating. There’s a grid, flooding cells day by day, and somehow you’re supposed to figure out the last possible day you can still cross from the top to the bottom.

If your first thought was “Do I simulate every day?” — you’re not alone.
Let’s slow it down and solve this step by step, in a way that actually makes sense.

🧠 Understanding the Problem (In Plain English)

You’re given:

A grid with row x col cells
A list cells, where each entry tells you which cell gets flooded on a given day

Rules:

On day 1, the first cell floods
On day 2, the second cell floods
And so on…

Your goal:

Find the last day when you can still walk from the top row to the bottom row, moving only through unflooded cells.

You can move:

Up, down, left, right (no diagonals)

❌ The Naive Idea (And Why It Fails)

A brute-force approach would be:

Simulate flooding day by day
After each day, check if a path exists

But checking paths every day is expensive:

Grid size can be up to 2×10⁴ cells
Path search (BFS/DFS) every day = too slow

So we need something smarter.

💡 Key Insight: Think Backwards

Instead of asking:

“On which day does crossing stop being possible?”

Ask:

“If I start from the last day and undo flooding, when does crossing become possible again?”

This small change makes a huge difference.

🚀 Strategy That Actually Works

We combine Binary Search + BFS.

Why Binary Search?

The answer is a day number
If you can cross on day d, you can also cross on any earlier day
That means the condition is monotonic
Perfect use case for binary search

🧪 Step-by-Step Approach

Step 1: Binary Search on Days

We search between:

left = 1
right = row * col

For a given day mid, we ask:

“Is it possible to cross on this day?”

Step 2: Check if Crossing Is Possible (BFS)

For day mid:

Mark the first mid cells as flooded
Start BFS from all unflooded cells in the top row
Try to reach the bottom row

If we reach the bottom → crossing is possible
If not → crossing is impossible

✅ Final Solution Code (Python)

from collections import deque

class Solution:
    def latestDayToCross(self, row: int, col: int, cells: list[list[int]]) -> int:
        
        def canCross(day):
            grid = [[0] * col for _ in range(row)]
            
            # Flood cells up to given day
            for i in range(day):
                r, c = cells[i]
                grid[r - 1][c - 1] = 1
            
            queue = deque()
            visited = [[False] * col for _ in range(row)]
            
            # Start BFS from top row
            for c in range(col):
                if grid[0][c] == 0:
                    queue.append((0, c))
                    visited[0][c] = True
            
            directions = [(1,0), (-1,0), (0,1), (0,-1)]
            
            while queue:
                r, c = queue.popleft()
                if r == row - 1:
                    return True
                
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < row and 0 <= nc < col:
                        if not visited[nr][nc] and grid[nr][nc] == 0:
                            visited[nr][nc] = True
                            queue.append((nr, nc))
            
            return False
        
        left, right = 1, row * col
        answer = 0
        
        while left <= right:
            mid = (left + right) // 2
            if canCross(mid):
                answer = mid
                left = mid + 1
            else:
                right = mid - 1
        
        return answer

⏱ Time & Space Complexity

Time Complexity

Binary Search: O(log(row * col))
BFS per check: O(row * col)
Total: O(row * col * log(row * col))

Space Complexity

Grid + visited matrix: O(row * col)

Efficient enough for large inputs.

🧩 Why This Solution Feels Smart

You avoid checking every day
You only run BFS ~log(n) times
The problem becomes manageable instead of overwhelming

This is a classic example of:

Reframing the problem → simpler solution

🏁 Final Thoughts

LeetCode 1970 isn’t really about grids or flooding.
It’s about recognizing monotonic behavior and combining:

Binary Search
Graph traversal (BFS)

Once that clicks, the problem goes from “hard” to “oh… that’s clever.”