1970. Last Day Where You Can Still Cross

HardDepth-First SearchBreadth-First SearchUnion FindArrayBinary SearchMatrix

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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

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:

Flooding all cells that should be water by day mid (the first mid cells from the cells array)
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 Implementation

1class Solution:
2    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
3        def can_cross(day: int) -> bool:
4            """Check if it's possible to cross from top to bottom on the given day."""
5            grid = [[0] * col for _ in range(row)]
6
7            for i in range(day):
8                r, c = cells[i]
9                grid[r - 1][c - 1] = 1
10
11            queue = []
12            for j in range(col):
13                if grid[0][j] == 0:
14                    queue.append((0, j))
15                    grid[0][j] = 1
16
17            idx = 0
18            while idx < len(queue):
19                x, y = queue[idx]
20                idx += 1
21
22                if x == row - 1:
23                    return True
24
25                for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
26                    next_x, next_y = x + dx, y + dy
27                    if 0 <= next_x < row and 0 <= next_y < col and grid[next_x][next_y] == 0:
28                        queue.append((next_x, next_y))
29                        grid[next_x][next_y] = 1
30
31            return False
32
33        def feasible(day: int) -> bool:
34            """Returns true when crossing is NOT possible (inverted condition)."""
35            return not can_cross(day)
36
37        # Binary search for first day where crossing becomes impossible
38        left, right = 1, len(cells)
39        first_true_index = -1
40
41        while left <= right:
42            mid = (left + right) // 2
43            if feasible(mid):
44                first_true_index = mid
45                right = mid - 1
46            else:
47                left = mid + 1
48
49        # Return the last day where crossing was still possible
50        return first_true_index - 1
51

1class Solution {
2    private int[][] cells;
3    private int rows;
4    private int cols;
5
6    public int latestDayToCross(int row, int col, int[][] cells) {
7        this.cells = cells;
8        this.rows = row;
9        this.cols = col;
10
11        // Binary search for first day where crossing becomes impossible
12        int left = 1;
13        int right = cells.length;
14        int firstTrueIndex = -1;
15
16        while (left <= right) {
17            int mid = left + (right - left) / 2;
18            if (feasible(mid)) {
19                firstTrueIndex = mid;
20                right = mid - 1;
21            } else {
22                left = mid + 1;
23            }
24        }
25
26        // Return last day where crossing was still possible
27        return firstTrueIndex - 1;
28    }
29
30    private boolean feasible(int day) {
31        // Returns true when crossing is NOT possible (inverted condition)
32        return !canCross(day);
33    }
34
35    private boolean canCross(int dayCount) {
36        int[][] grid = new int[rows][cols];
37
38        for (int i = 0; i < dayCount; i++) {
39            grid[cells[i][0] - 1][cells[i][1] - 1] = 1;
40        }
41
42        final int[] directions = {-1, 0, 1, 0, -1};
43        Deque<int[]> queue = new ArrayDeque<>();
44
45        for (int c = 0; c < cols; c++) {
46            if (grid[0][c] == 0) {
47                queue.offer(new int[] {0, c});
48                grid[0][c] = 1;
49            }
50        }
51
52        while (!queue.isEmpty()) {
53            int[] position = queue.poll();
54            int currentRow = position[0];
55            int currentCol = position[1];
56
57            if (currentRow == rows - 1) {
58                return true;
59            }
60
61            for (int i = 0; i < 4; i++) {
62                int nextRow = currentRow + directions[i];
63                int nextCol = currentCol + directions[i + 1];
64
65                if (nextRow >= 0 && nextRow < rows &&
66                    nextCol >= 0 && nextCol < cols &&
67                    grid[nextRow][nextCol] == 0) {
68                    queue.offer(new int[] {nextRow, nextCol});
69                    grid[nextRow][nextCol] = 1;
70                }
71            }
72        }
73
74        return false;
75    }
76}
77

1class Solution {
2public:
3    int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
4        int directions[5] = {0, 1, 0, -1, 0};
5
6        auto canCross = [&](int day) -> bool {
7            vector<vector<int>> grid(row, vector<int>(col, 0));
8
9            for (int i = 0; i < day; ++i) {
10                grid[cells[i][0] - 1][cells[i][1] - 1] = 1;
11            }
12
13            queue<pair<int, int>> bfsQueue;
14
15            for (int j = 0; j < col; ++j) {
16                if (grid[0][j] == 0) {
17                    bfsQueue.emplace(0, j);
18                    grid[0][j] = 1;
19                }
20            }
21
22            while (!bfsQueue.empty()) {
23                auto [currentRow, currentCol] = bfsQueue.front();
24                bfsQueue.pop();
25
26                if (currentRow == row - 1) {
27                    return true;
28                }
29
30                for (int i = 0; i < 4; ++i) {
31                    int nextRow = currentRow + directions[i];
32                    int nextCol = currentCol + directions[i + 1];
33
34                    if (nextRow >= 0 && nextRow < row &&
35                        nextCol >= 0 && nextCol < col &&
36                        grid[nextRow][nextCol] == 0) {
37                        bfsQueue.emplace(nextRow, nextCol);
38                        grid[nextRow][nextCol] = 1;
39                    }
40                }
41            }
42
43            return false;
44        };
45
46        auto feasible = [&](int day) -> bool {
47            return !canCross(day);
48        };
49
50        // Binary search for first day where crossing becomes impossible
51        int left = 1;
52        int right = cells.size();
53        int firstTrueIndex = -1;
54
55        while (left <= right) {
56            int mid = left + (right - left) / 2;
57            if (feasible(mid)) {
58                firstTrueIndex = mid;
59                right = mid - 1;
60            } else {
61                left = mid + 1;
62            }
63        }
64
65        // Return last day where crossing was still possible
66        return firstTrueIndex - 1;
67    }
68};
69

1function latestDayToCross(row: number, col: number, cells: number[][]): number {
2    const canCrossOnDay = (dayNumber: number): boolean => {
3        const grid: number[][] = Array.from({ length: row }, () => Array(col).fill(0));
4
5        for (let i = 0; i < dayNumber; ++i) {
6            const [cellRow, cellCol] = cells[i];
7            grid[cellRow - 1][cellCol - 1] = 1;
8        }
9
10        const queue: number[][] = [];
11
12        for (let j = 0; j < col; ++j) {
13            if (grid[0][j] === 0) {
14                queue.push([0, j]);
15                grid[0][j] = 1;
16            }
17        }
18
19        const directions: number[] = [-1, 0, 1, 0, -1];
20
21        for (const [currentRow, currentCol] of queue) {
22            if (currentRow === row - 1) {
23                return true;
24            }
25
26            for (let i = 0; i < 4; ++i) {
27                const nextRow: number = currentRow + directions[i];
28                const nextCol: number = currentCol + directions[i + 1];
29
30                if (nextRow >= 0 && nextRow < row &&
31                    nextCol >= 0 && nextCol < col &&
32                    grid[nextRow][nextCol] === 0) {
33                    queue.push([nextRow, nextCol]);
34                    grid[nextRow][nextCol] = 1;
35                }
36            }
37        }
38
39        return false;
40    };
41
42    const feasible = (day: number): boolean => {
43        return !canCrossOnDay(day);
44    };
45
46    // Binary search for first day where crossing becomes impossible
47    let left = 1;
48    let right = cells.length;
49    let firstTrueIndex = -1;
50
51    while (left <= right) {
52        const mid = Math.floor((left + right) / 2);
53        if (feasible(mid)) {
54            firstTrueIndex = mid;
55            right = mid - 1;
56        } else {
57            left = mid + 1;
58        }
59    }
60
61    // Return last day where crossing was still possible
62    return firstTrueIndex - 1;
63}
64

Solution Approach

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

Binary Search Template Application:

We need to find the last day where crossing is possible. To use the standard "find first true" template, we reframe the problem: find the first day where crossing becomes impossible, then return first_true_index - 1.

The feasible function is defined as: feasible(day) = !canCross(day) (returns true when crossing is NOT possible).

Algorithm Steps:

Initialize search bounds:
- left = 1, right = row * col
- first_true_index = -1 (tracks the first day where crossing becomes impossible)
Binary search loop (while left <= right):
- Calculate mid = (left + right) // 2
- If !canCross(mid) is true (crossing impossible on day mid):
  - Save first_true_index = mid
  - Search for an earlier impossible day: right = mid - 1
- If !canCross(mid) is false (crossing still possible):
  - Need a later day: left = mid + 1
Return the last crossable day: first_true_index - 1

The canCross Helper Function (BFS):

For each candidate day k, check if crossing is possible:

Build the grid state: Create a 2D grid, mark the first k cells as water (1).
BFS from top row: Initialize queue with all land cells from row 0.
BFS exploration: For each cell, check if we've reached the bottom row. Explore all 4 directions, adding unvisited land cells to the queue.
Return result: True if we reach bottom row, False otherwise.

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

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

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

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 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
left = 1, right = 5, first_true_index = -1
We're finding the first day where crossing becomes impossible, then subtracting 1.
feasible(day) = !canCross(day) (true when crossing is impossible)

Binary Search Iteration 1:

mid = (1 + 5) // 2 = 3
Check !canCross(3): After flooding cells [1,2], [2,2], [3,2]
Grid state:
```
0 1 0
0 1 0
0 1 0
```
BFS from (0,0): (0,0) → (1,0) → (2,0) - reached bottom row!
canCross(3) = true, so !canCross(3) = false
Not feasible (can still cross): left = 3 + 1 = 4

Binary Search Iteration 2:

mid = (4 + 5) // 2 = 4
Check !canCross(4): After flooding cells [1,2], [2,2], [3,2], [1,1]
Grid state:
```
1 1 0
0 1 0
0 1 0
```
BFS from (0,2): (0,2) → blocked by water, no path to bottom
canCross(4) = false, so !canCross(4) = true
Feasible (crossing impossible): first_true_index = 4, right = 4 - 1 = 3

Binary Search Iteration 3:

left = 4 > right = 3, loop ends

Final Result:

first_true_index = 4 (first day crossing is impossible)
Return first_true_index - 1 = 3 (last day crossing is possible)

The last day we can cross from top to bottom is day 3.

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. Using Wrong Binary Search Template Variant

A common mistake is using the while left < right with left = mid variant. The standard template uses while left <= right with right = mid - 1.

Incorrect Implementation:

while left < right:
    mid = (left + right + 1) // 2
    if can_cross(mid):
        left = mid  # Wrong pattern
    else:
        right = mid - 1
return left

Correct Implementation (using template with inverted condition):

left, right = 1, len(cells)
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if not can_cross(mid):  # feasible = cannot cross
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return first_true_index - 1

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

The problem provides 1-based coordinates in the cells array, but 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. 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

4. Forgetting to Invert the Condition for Template

When using the "find first true" template for a "find last true" problem, you must invert the feasible condition.

Why: The template finds the first index where feasible(x) returns true. For "find last day where crossing is possible", we define feasible(day) = !canCross(day) (first day where crossing is impossible), then return first_true_index - 1.

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).

Optimal:

left, right = 1, len(cells)

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