LeetCode 1970: Last Day Where You Can Still Cross

link

The grid can be considered as an undirected graph where land cells are the vertices and an edge exists between two vertices if the land cells are neighbors.

DFS

In the grid graph, for each day, we can check if there is a path from any of the sources (land cells on first row) to any of the destinations (land cells on last row).

Time: $\mathcal{O}((m \cdot n) \cdot (m \cdot n)) = \mathcal{O}\left((m \cdot n)^2\right)$ , space: $\mathcal{O}(m \cdot n)$ .

class Solution:
    def neibors(self, u, m, n, flooded_cells):
        r, c = u
        for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            r2, c2 = r + dr, c + dc
            if not (1 <= r2 <= m):
                continue
            if not (1 <= c2 <= n):
                continue
            if (r2, c2) in flooded_cells:
                continue

            yield (r2, c2)

    def has_path(self, u, destinations, m, n, flooded_cells, visited):
        if u in destinations:
            return True

        visited.add(u)
        for v in self.neibors(u, m, n, flooded_cells):
            if v in visited:
                continue
            if self.has_path(v, destinations, m, n, flooded_cells, visited):
                return True
        visited.remove(u)

        return False

    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        sources, destinations = set(), set()
        for col in range(1, col + 1):
            sources.add((1, col))
            destinations.add((row, col))

        flooded_cells = set()
        for day, cell in enumerate(cells, start=1):
            u = tuple(cell)
            flooded_cells.add(u)
            sources.discard(u)
            destinations.discard(u)

            if not any(
                self.has_path(s, destinations, row, col, flooded_cells, set())
                for s in sources
            ):
                return day - 1

        return None

BFS

Time: $\mathcal{O}((m \cdot n) \cdot (m \cdot n)) = \mathcal{O}\left((m \cdot n)^2\right)$ , space: $\mathcal{O}(m \cdot n)$ .

class Solution:
    def neibors(self, u, m, n, flooded_cells):
        r, c = u
        for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            r2, c2 = r+dr, c+dc
            if not (1 <= r2 <= m):
                continue
            if not (1 <= c2 <= n):
                continue
            if (r2, c2) in flooded_cells:
                continue
            
            yield (r2, c2)

    def has_path(self, sources, destinations, m, n, flooded_cells):
        visited = set(sources)
        q = deque(list(sources))
        while q:
            u = q.popleft()
            if u in destinations:
                return True
            for v in self.neibors(u, m, n, flooded_cells):
                if v in visited:
                    continue
                visited.add(v)
                q.append(v)
        
        return False

    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        sources, destinations = set(), set()
        for col in range(1, col+1):
            sources.add((1, col))
            destinations.add((row, col))

        flooded_cells = set()
        for day, cell in enumerate(cells, start=1):
            u = tuple(cell)
            flooded_cells.add(u)
            sources.discard(u)
            destinations.discard(u)
            if not self.has_path(sources, destinations, row, col, flooded_cells):
                return day-1
        
        return None

BFS with heuristic

We can use Manhattan distance to one of the destinations as a heuristic to direct the path finding towards destination.

from heapq import heapify, heappush as push, heappop as pop

class Solution:
    def neibors(self, u, m, n, flooded_cells):
        r, c = u
        for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            r2, c2 = r+dr, c+dc
            if not (1 <= r2 <= m):
                continue
            if not (1 <= c2 <= n):
                continue
            if (r2, c2) in flooded_cells:
                continue
            
            yield (r2, c2)

    def has_path(self, sources, destinations, m, n, flooded_cells):
        def manhattan_distance(u, v):
            return abs(u[0]-v[0]) + abs(u[1]-v[1])

        if not destinations:
            return False

        visited = set(sources)
        d0 = next(d for d in destinations)
        q = []
        for s in sources:
            dist = manhattan_distance(s, d0)
            q.append((dist, 0, s))
        heapify(q)

        while q:
            _, l, u = pop(q)
            if u in destinations:
                return True
            for v in self.neibors(u, m, n, flooded_cells):
                if v in visited:
                    continue
                visited.add(v)
                dist = manhattan_distance(v, d0)
                push(q, (l+dist, l+1, v))
        
        return False

    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        sources, destinations = set(), set()
        for col in range(1, col+1):
            sources.add((1, col))
            destinations.add((row, col))

        flooded_cells = set()
        for day, cell in enumerate(cells, start=1):
            u = tuple(cell)
            flooded_cells.add(u)
            sources.discard(u)
            destinations.discard(u)
            if not self.has_path(sources, destinations, row, col, flooded_cells):
                return day-1
        
        return None

Union-Find

In the beginning the grid (land) graph has a single, big connected component. As the cells get flooded, the number of connected components increases or the size of connected components shrink. The latest day when a connected component still has cells from both the first row and the last row, is the day we want. For the example below, we want day 3.

We can also think backwards, starting from the last flood day. Initially the land graph is empty and as we undo flooded cells, the connected component count or size grows. For the example above, Day 4 is then the first day which if we undid, would have had a connected component having cells from both row 1 and row 3. So, the day before Day 4, is the day we want. We can use Union-Find to keep track of the connected components — represented as row-set. During union, we merge the two row sets.

Time: $\mathcal{O}(m \cdot n \cdot (\lg^*{(m \cdot n)} + m))$ , space: $\mathcal{O}(m \cdot n)$ .

class UnionFind:
    def __init__(self, m, n):
        self.m, self.n = m, n
        self.parent_of, self.rank_of = {}, {}
        self.cc = {}
        self.top_bottom_connected = False

    def neibors(self, u):
        r, c = u
        for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            r2, c2 = r + dr, c + dc
            if not (1 <= r2 <= self.m):
                continue
            if not (1 <= c2 <= self.n):
                continue
            if (r2, c2) not in self.parent_of:
                continue

            yield (r2, c2)

    def __compress_path(self, u, root):
        while u != (p := self.parent_of[u]):
            self.parent_of[u] = root
            u = p

    def __find(self, u):
        root = u
        while root != (p := self.parent_of[root]):
            root = p
        self.__compress_path(u, root)
        return root

    def __union(self, u, v):
        def update_cc(root, child):
            self.cc[root].update(self.cc[child])
            del self.cc[child]
            self.top_bottom_connected = 1 in self.cc[root] and self.m in self.cc[root]

        root_u = self.__find(u)
        root_v = self.__find(v)
        if root_u == root_v:
            return

        rank_u = self.rank_of[root_u]
        rank_v = self.rank_of[root_v]
        root, child = None, None
        if rank_u == rank_v:
            self.parent_of[root_u] = root_v
            self.rank_of[root_v] += 1
            update_cc(root_v, root_u)
            return

        if rank_u < rank_v:
            self.parent_of[root_u] = root_v
            update_cc(root_v, root_u)
        else:
            self.parent_of[root_v] = root_u
            update_cc(root_u, root_v)

    def add(self, u):
        self.parent_of[u] = u
        self.rank_of[u] = 0
        self.cc[u] = {u[0]}

        for v in self.neibors(u):
            self.__union(u, v)

    def has_path(self):
        return self.top_bottom_connected


class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        uf = UnionFind(row, col)
        for d in range(len(cells), 0, -1):
            u = tuple(cells[d - 1])
            uf.add(u)
            if uf.has_path():
                # If we undid day d, we would have
                # had a path. So, the previous day is
                # the last day the top and bottom
                # were connected.
                return d - 1

        return None

Binary search with BFS

Note, has_path() is a step-function — once it evaluates to False, it remains False. In other words, has_path() is a monotonic function of days. So, we can use binary-search on the days to find the last day where has_path() is True.

Time: $\mathcal{O}(\lg{(m \cdot n)} \cdot (m \cdot n))$ , space: $\mathcal{O}(m \cdot n)$ .

class Solution:
    def neibors(self, u, m, n, flooded_cells):
        r, c = u
        for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            r2, c2 = r+dr, c+dc
            if not (1 <= r2 <= m):
                continue
            if not (1 <= c2 <= n):
                continue
            if (r2, c2) in flooded_cells:
                continue
             
            yield (r2, c2)
 
    def has_path(self, m, n, cells, day):
        sources, destinations = set(), set()
        for col in range(1, n+1):
            sources.add((1, col))
            destinations.add((m, col))
        
        flooded_cells = set()
        for d in range(day):
            u = tuple(cells[d])
            flooded_cells.add(u)
            sources.discard(u)
            destinations.discard(u)

        visited = set(sources)
        q = deque(list(sources))
        while q:
            u = q.popleft()
            if u in destinations:
                return True
            for v in self.neibors(u, m, n, flooded_cells):
                if v in visited:
                    continue
                visited.add(v)
                q.append(v)
         
        return False
 
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        lo, hi = 1, len(cells)
        while lo <= hi:
            mid = (lo+hi) // 2
            if self.has_path(row, col, cells, mid):
                lo = mid+1
            else:
                hi = mid-1

        return lo-1

unreasonably effective