Skip to main content
Talentd

Last Day Where You Can Still Cross - Solution & Explanation

HardArrayBinary SearchDepth-First SearchBreadth-First Search42 min readAsked at: Amazon, Meta, Atlassian +1
Practice this problem

Problem Statement

There is 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] = [ri, ci] represents that on the ith day, the cell on the rith row and cith column (1-based coordinates) will be covered with water (i.e., changed to 1).

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

Return the last day where it is possible to walk from the top to the bottom by only walking on land cells.

 

Example 1:

Input: row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]]
Output: 2
Explanation: The above image depicts how the matrix changes each day starting from day 0.
The last day where it is possible to cross from top to bottom is on day 2.

Example 2:

Input: row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]]
Output: 1
Explanation: The above image depicts how the matrix changes each day starting from day 0.
The last day where it is possible to cross from top to bottom is on day 1.

Example 3:

Input: row = 3, col = 3, cells = [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]]
Output: 3
Explanation: The above image depicts how the matrix changes each day starting from day 0.
The last day where it is possible to cross from top to bottom is on day 3.

 

Constraints:

  • 2 <= row, col <= 2 * 104
  • 4 <= row * col <= 2 * 104
  • cells.length == row * col
  • 1 <= ri <= row
  • 1 <= ci <= col
  • All the values of cells are unique.

Approach Overview

Problem Overview: A grid starts as land. Each day, one cell becomes water. You must find the last day when it is still possible to walk from the top row to the bottom row using only land cells moving in four directions.

The key observation: if crossing is possible on day d, it is also possible on every earlier day. Once the grid becomes too flooded, crossing stays impossible afterward. This monotonic behavior allows a binary search on the day number.

Approach 1: Binary Search with DFS/BFS (O(m * n log(m * n)) time, O(m * n) space)

Binary search the answer between day 1 and m * n. For each candidate day, construct the grid where the first day cells in cells are flooded. Start from every land cell in the top row and run DFS or BFS to check if you can reach the bottom row. The traversal only moves through land cells and marks visited positions to avoid repetition. If a path exists, crossing is still possible, so move the binary search window right. Otherwise move left. This approach is straightforward and maps directly to graph traversal on a matrix.

Approach 2: Binary Search with Union-Find (O(m * n log(m * n)) time, O(m * n) space)

Instead of exploring the grid with DFS each time, treat each cell as a node in a Union-Find structure. For a given day in the binary search, mark flooded cells and union adjacent land cells. Two virtual nodes represent the top boundary and bottom boundary. Land cells in the first row connect to the top node, and cells in the last row connect to the bottom node. If both virtual nodes end up in the same connected component, a path from top to bottom exists. Union-Find reduces repeated traversal work and keeps connectivity checks near constant time.

Recommended for interviews: Binary Search with DFS/BFS is usually expected first because it clearly demonstrates the monotonic property and grid traversal logic. After establishing correctness, Union-Find shows deeper understanding of connectivity problems and can lead to cleaner connectivity checks in dense grids.

Approach 1: Binary Search with DFS

This approach involves using a binary search to find the last day a path exists from top to bottom. For each midpoint in the binary search, simulate the grid's flooding and check path connectivity using Depth First Search (DFS). Start by initializing the grid as land then flood the cells according to the days up to midpoint. Using DFS, attempt to find a path from the top to the bottom row.

This C implementation utilizes binary search to identify the last day on which a path exists. A DFS is performed on each iteration to verify path connectivity. The matrix is simulated up to the nth day for the selected midpoint during binary search.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity is O(n * m * log(n * m)) where n is the number of rows and m is the number of columns. Space Complexity is O(n * m) for the visited matrix.

Try this approach in the editor →

Approach 2: Binary Search with Union-Find

This approach involves using a union-find data structure to efficiently check connectivity between the top and bottom rows during a binary search over the days. For each day in the binary search, the cells flooded up to that day are processed, and union operations are performed on adjacent land cells. We add virtual top and bottom nodes in the union-find structure to track connectivity between the top and bottom row cells.

This C code uses union-find to efficiently manage connectivity between cells during binary search on flooding days. Virtual top and bottom nodes simulate the start and finish of paths, confirming connectivity between them.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity is O(n * m * log(n * m)) due to union-find operations, and Space Complexity is O(n * m) for the union-find parent and rank tracking.

Try this approach in the editor →

Approach 3: Binary Search + BFS

We note that if we can walk from the top row to the bottom row on day k, then for any 0 < k' < k, we can also walk from the top row to the bottom row on day k'. This exhibits monotonicity, so we can use binary search to find the largest k such that we can walk from the top row to the bottom row on day k.

We define the left boundary of the binary search as l = 1 and the right boundary as r = |cells|, where |cells| represents the length of the array cells. Then, we perform binary search on k. For each k, we take the first k elements of cells, turn the corresponding cells into water, and then use breadth-first search (BFS) to try to walk from the top row to the bottom row. If we can reach the bottom row, it means we can walk from the top row to the bottom row on day k, so we update the left boundary l to k. Otherwise, we update the right boundary r to k - 1.

The time complexity is O(m times n times log (m times n)), and the space complexity is O(m times n). Here, m and n represent the number of rows and columns of the matrix, respectively.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Approach 4: Union-Find

We can first initialize all land cells as 1, then traverse the array cells in reverse order, turning each corresponding land cell into 0 and merging it with the adjacent land cells (up, down, left, right). We also need to maintain two virtual nodes s and t, representing the virtual nodes for the top row and the bottom row, respectively. If s and t are connected in the union-find set, it means we can walk from the top row to the bottom row on day i.

The time complexity is O(m times n times \alpha(m times n)), and the space complexity is O(m times n). Here, m and n represent the number of rows and columns of the matrix, respectively, and \alpha represents the inverse Ackermann function.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Binary Search with DFS

Time Complexity is O(n * m * log(n * m)) where n is the number of rows and m is the number of columns. Space Complexity is O(n * m) for the visited matrix.

Binary Search with Union-Find

Time Complexity is O(n * m * log(n * m)) due to union-find operations, and Space Complexity is O(n * m) for the union-find parent and rank tracking.

Binary Search + BFS—
Union-Find—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Binary Search + DFS/BFSO(m * n log(m * n))O(m * n)Best starting approach for interviews. Simple grid traversal and easy to implement.
Binary Search + Union-FindO(m * n log(m * n))O(m * n)When frequent connectivity checks are needed. Cleaner path existence checks using disjoint sets.

Video Solution

Last Day Where You Can Still Cross | BFS | DFS | Binary Search | Leetcode 1970 | codestorywithMIK • codestorywithMIK • 11,673 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Last Day Where You Can Still Cross easy or hard?
Last Day Where You Can Still Cross is classified as a Hard problem on LeetCode. The difficulty comes from recognizing the monotonic property that enables binary search and efficiently checking connectivity in a dynamically flooding grid.
Last Day Where You Can Still Cross Python/Java solution
Python and Java implementations typically perform binary search over the day index and rebuild the grid for each check. A DFS/BFS explores reachable land cells from the top row. Java solutions often use iterative BFS with queues, while Python versions commonly use DFS recursion or deque-based BFS.
How to solve Last Day Where You Can Still Cross in O(n)?
A near-linear approach uses Union-Find while processing cells in reverse order (from the last day backward). Each step converts water back to land and unions adjacent land cells. Connectivity between top and bottom boundaries is checked after each step, giving roughly O(m*n α(m*n)) time where α is the inverse Ackermann function.
What is the best approach for Last Day Where You Can Still Cross?
Binary Search combined with DFS or BFS is the most common approach. The key insight is that the ability to cross the grid is monotonic with respect to the day number. Binary search finds the last valid day, while DFS/BFS checks whether a path from the top row to the bottom row exists in O(m*n) time for each check.
Is Last Day Where You Can Still Cross asked at Google/Amazon/Meta?
This problem style appears frequently in interviews at large tech companies including Google, Amazon, and Meta. It tests binary search on answers, grid traversal, and connectivity structures like Union-Find, all common interview patterns for graph and matrix problems.
What data structure is used in Last Day Where You Can Still Cross?
The solution commonly uses a grid matrix with DFS or BFS traversal, combined with binary search over days. An alternative approach uses the Union-Find (Disjoint Set Union) data structure to efficiently track connectivity between cells.
What is the time complexity of Last Day Where You Can Still Cross?
The typical solution runs in O(m * n log(m * n)) time. Binary search performs about log(m*n) checks, and each check runs a grid traversal such as DFS or BFS that touches up to m*n cells. Space complexity is O(m*n) for the grid and visited tracking.

Ready to solve this problem?

Practice Last Day Where You Can Still Cross with our built-in code editor and test cases.

Practice on FleetCode
Previous

Bricks Falling When Hit

Next

Escape the Spreading Fire