HardNo. 1970

Last Day Where You Can Still Cross — LeetCode 1970 Python Solution

Pattern
Union-Find
Topics
Depth-First Search, Breadth-First Search, Union Find, Array, Binary Search, Matrix
Reading time
5 min

The problem

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.

Example

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.

Python solution

PythonSolution
class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        def check(k: int) -> bool:
            g = [[0] * col for _ in range(row)]
            for i, j in cells[:k]:
                g[i - 1][j - 1] = 1
            q = [(0, j) for j in range(col) if g[0][j] == 0]
            for x, y in q:
                if x == row - 1:
                    return True
                for a, b in pairwise(dirs):
                    nx, ny = x + a, y + b
                    if 0 <= nx < row and 0 <= ny < col and g[nx][ny] == 0:
                        q.append((nx, ny))
                        g[nx][ny] = 1
            return False

        n = row * col
        l, r = 1, n
        dirs = (-1, 0, 1, 0, -1)
        while l < r:
            mid = (l + r + 1) >> 1
            if check(mid):
                l = mid
            else:
                r = mid - 1
        return l

Complexity

Time
O(m × n × log (m × n))
Space · auxiliary
O(m × n)

Pattern: Union-Find

Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 1970. Last Day Where You Can Still Cross is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.

The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0778Swim in Rising WaterHard
1631Path With Minimum EffortMedium
2812Find the Safest Path in a GridMedium
2258Escape the Spreading FireHard
0074Search a 2D MatrixMedium
0240Search a 2D Matrix IIMedium

Frequently asked questions

How hard is LeetCode 1970. Last Day Where You Can Still Cross?

LeetCode 1970. Last Day Where You Can Still Cross is rated Hard on LeetCode.

What is the time complexity of LeetCode 1970. Last Day Where You Can Still Cross?

The Python solution on this page runs in O(m × n × log (m × n)).

What is the space complexity of LeetCode 1970. Last Day Where You Can Still Cross?

The Python solution on this page uses O(m × n) auxiliary space.

What topics does LeetCode 1970. Last Day Where You Can Still Cross cover?

LeetCode 1970. Last Day Where You Can Still Cross is tagged Depth-First Search, Breadth-First Search, Union Find, Array, Binary Search and Matrix on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.