Problem statement

https://leetcode.com/problems/swim-in-rising-water/

Solution 1

First solution is to use Union Find data structure: on each moment of time we can update connected component and wait for the moment when 0 and N^2-1 are in the same component.

Complexity

Complexity is O(N^2 *log N) if we use union find with ranks (in code above) and O(N^2) if we use it with ranks and paths compression. Space complexity is O(N^2).

Code

class DSU(object):
    def __init__(self, N):
        self.par = list(range(N))
        self.rnk = [0] * N

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

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        if xr == yr:
            return False
        elif self.rnk[xr] < self.rnk[yr]:
            self.par[xr] = yr
        elif self.rnk[xr] > self.rnk[yr]:
            self.par[yr] = xr
        else:
            self.par[yr] = xr
            self.rnk[xr] += 1
        return True

class Solution:
    def swimInWater(self, grid):
        d, N = {}, len(grid)
        for i,j in product(range(N), range(N)):
            d[grid[i][j]] = (i, j)
        
        dsu = DSU(N*N)
        grid = [[0] * N for _ in range(N)] 
        neib_list = [[0,1],[0,-1],[1,0],[-1,0]]
        
        for i in range(N*N):
            x, y = d[i]
            grid[x][y] = 1
            for dx, dy in neib_list:
                if N>x+dx>=0 and N>y+dy>=0 and grid[x+dx][y+dy] == 1:
                    dsu.union((x+dx)*N + y + dy, x*N + y)
                    
            if dsu.find(0) == dsu.find(N*N-1): return i

Solution 2

There is also solution, using heaps: we perform usual dfs, start with (0,0) corner, but on each moment of time we choose node with smallest value to visit. In this way when we reached (N-1, N-1) corner, the answer will be the maximum of visited cells so far.

Complexity

Complexity is again O(N^2 *log N).

Code

class Solution:
    def swimInWater(self, grid):
        N, heap, visited, res = len(grid), [(grid[0][0], 0, 0)], set([(0, 0)]), 0
        
        for i in range(N*N):
            val, x, y = heappop(heap)
            res = max(res, val)
            if x == N-1 and y == N-1: return res
            neib_list = [[0,1],[0,-1],[1,0],[-1,0]]
            
            for dx, dy in neib_list:
                if (x + dx, y + dy) not in visited and 0<=x+dx<N and 0<=y+dy<N:
                    heappush(heap, (grid[x+dx][y+dy], x+dx, y+dy))
                    visited.add((x+dx, y+dy))

Remark

Finally, there is Binary Search solution, where we ask question, given day D if we can reach end point or not. Time complexity is again O(N^2 * log N).