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 \times n \times \log (m \times 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 \times 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.

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

HardDepth-First SearchBreadth-First SearchUnion FindArrayBinary SearchMatrix

Problem: #1970
Pattern: Union-Find
Reading time: 5 min
Source: leetcode.com

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

Python

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

Measure	Complexity
Time	O(m \times n \times \log (m \times n))
Space	O(m \times n) auxiliary

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.

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 \times n \times \log (m \times 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 \times 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.