Problem statement

https://leetcode.com/problems/last-day-where-you-can-still-cross/

Solution

When you see that problem is about connectivity of some parts of graph, you should immedietly think about Union Find. In fact this problem is very similar to problem 0803. Bricks Falling When Hit, let us go through algorithm.

  1. First of all, we are asked to find the moment of time when graph stop to be connected, so we remove connections one by one and union find allows us to do the opposite: add connections. So, what we need to do is to start from the end: we add all water cells to our grid and then create all connections: between pairs of adjacent 0. Also we need to create dummy variables for element which connected with top row and another element which connected with bottom row. So, our dsu structure will have mn + 2 elements in total. update Actually it is given in problem description that len(C) = m*n, so in the end we will have all elements being water.
  2. After we created all connections for the last position, we start form the last element in C and replace water with land: we make grid[x][y] = 0 and then create all connections. If we see that cell 0 is connected with cell mn + 1, it means that we have path from the top to bottom.

Complexity

It is O(mn + C*alpha(mn)), where alpha is inverse Ackermann function. Given that it grows very slow we can say that it is just O(mn). Space complexity is O(mn) as well.

Code

class DSU:
    def __init__(self, N):
        self.p = list(range(N))

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        self.p[xr] = yr

class Solution:
    def latestDayToCross(self, n, m, C):
        row, col = len(C), len(C[0])
        dsu = DSU(m*n + 2)
        grid = [[1] * m for _ in range(n)]
        neibs = [[0,1],[0,-1],[1,0],[-1,0]]
        C = [(x-1, y-1) for x, y in C]

        def index(x, y):
            return x * m + y + 1

        for i in range(len(C) - 1, -1, -1):
            x, y = C[i][0], C[i][1]

            grid[x][y] = 0
            for dx, dy in neibs:
                ind = index(x+dx, y+dy)
                if x+dx>=0 and x+dx<n and y + dy >= 0 and y + dy < m and grid[x+dx][y+dy] == 0:
                    dsu.union(ind, index(x, y))
            if x == 0:
                dsu.union(0, index(x, y))
            if x == n - 1:
                dsu.union(m*n + 1, index(x, y))

            if dsu.find(0) == dsu.find(m*n + 1):
                return i

Remark

I just realized that it is possible to solve this problem with binary search as well: we need to find the moment of time when graph becomes unconnected, complexity will be O(mn*log(C)).