Solution Explanation for LeetCode 1970. Last Day Where You Can Still Cross

This problem asks to find the last day when it's still possible to traverse a grid from top to bottom, given that each day a new cell is flooded (turned from land to water). The key observation is that the possibility of traversal is monotonically decreasing: if you can cross on day k, you can also cross on any day before k. This allows us to use binary search for an efficient solution.

Approach 1: Binary Search + Breadth-First Search (BFS)

1. Binary Search: We perform a binary search on the days (from 1 to the total number of cells). The check(k) function determines if a path exists on day k.

2. check(k) function: This function simulates the flooding up to day k. It uses BFS to explore the grid, starting from all cells in the top row that are still land. If BFS can reach any cell in the bottom row, it returns True; otherwise, False.

3. Time Complexity: The binary search takes O(log(mn)) iterations, where 'm' and 'n' are the number of rows and columns, respectively. Each BFS call takes O(mn) in the worst case. Therefore, the overall time complexity is O(mn log(mn)).

4. Space Complexity: The space complexity is dominated by the grid and the BFS queue, which is O(mn).

Approach 2: Union-Find

This approach cleverly uses a disjoint-set union (Union-Find) data structure to track connectivity.

1. Reverse Iteration: We process the cells array in reverse order, simulating the unflooding of cells.

2. Union-Find Initialization: A union-find data structure is initialized to represent the grid's cells. We also add two virtual nodes: s (representing the top row) and t (representing the bottom row).

3. Unflooding and Union: For each day (in reverse), we "unflood" the cell and check for connections. If a cell is adjacent to another unflooded cell, we perform a union operation in the Union-Find structure. If a cell is in the top row, we unite it with the s node. If a cell is in the bottom row, we unite it with the t node.

4. Connectivity Check: After each unflooding, we check if s and t are connected using the find operation in Union-Find. If they are connected, it means we can traverse the grid from top to bottom. This is because a path now exists between the top and bottom.

5. Time Complexity: The Union-Find operations (find and union) take nearly constant time on average, using path compression and union by rank optimizations (close to O(α(mn)), where α is the inverse Ackermann function, which grows incredibly slowly and is considered practically constant for all reasonable input sizes). The overall time complexity is therefore dominated by the loop iterating through the cells, making it O(mn α(mn)) ≈ O(mn).

6. Space Complexity: The space complexity is O(mn) for the Union-Find data structure and grid.

Code Examples (Python):

Approach 1 (Binary Search + BFS):

from itertools import pairwise
 
class Solution:
    def latestDayToCross(self, row, col, cells):
        def check(k):  #Check if path exists on day k
            grid = [[0] * col for _ in range(row)]
            for r, c in cells[:k]:
                grid[r - 1][c - 1] = 1
            q = [(0, j) for j in range(col) if grid[0][j] == 0]
            visited = set(q)
            while q:
                r, c = q.pop(0)
                if r == row - 1:
                    return True
                for dr, dc in pairwise([-1, 0, 1, 0, -1]):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < row and 0 <= nc < col and grid[nr][nc] == 0 and (nr, nc) not in visited:
                        q.append((nr, nc))
                        visited.add((nr, nc))
            return False
 
        left, right = 1, len(cells)
        while left < right:
            mid = (left + right + 1) // 2
            if check(mid):
                left = mid
            else:
                right = mid - 1
        return left
 

Approach 2 (Union-Find):

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
 
    def find(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.find(self.parent[i])
        return self.parent[i]
 
    def union(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i != root_j:
            if self.rank[root_i] < self.rank[root_j]:
                self.parent[root_i] = root_j
            elif self.rank[root_i] > self.rank[root_j]:
                self.parent[root_j] = root_i
            else:
                self.parent[root_j] = root_i
                self.rank[root_i] += 1
            return True
        return False
 
class Solution:
    def latestDayToCross(self, row, col, cells):
        uf = UnionFind(row * col + 2)  # Add 2 virtual nodes
        grid = [[1] * col for _ in range(row)]
        top = row * col
        bottom = row * col + 1
        for i in range(len(cells) - 1, -1, -1):
            r, c = cells[i]
            grid[r - 1][c - 1] = 0
            idx = (r - 1) * col + (c - 1)
            if r == 1:
                uf.union(idx, top)
            if r == row:
                uf.union(idx, bottom)
            for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nr, nc = r + dr - 1, c + dc - 1
                if 0 <= nr < row and 0 <= nc < col and grid[nr][nc] == 0:
                    uf.union(idx, nr * col + nc)
            if uf.find(top) == uf.find(bottom):
                return i

Both approaches correctly solve the problem, but the Union-Find approach is generally faster for larger grids due to its near-constant-time operations. Choose the approach that best suits your understanding and coding style. The provided code includes detailed comments to aid in comprehension.