<p>There is a <strong>1-based</strong> binary matrix where <code>0</code> represents land and <code>1</code> represents water. You are given integers <code>row</code> and <code>col</code> representing the number of rows and columns in the matrix, respectively.</p>

<p>Initially on day <code>0</code>, the <strong>entire</strong> matrix is <strong>land</strong>. However, each day a new cell becomes flooded with <strong>water</strong>. You are given a <strong>1-based</strong> 2D array <code>cells</code>, where <code>cells[i] = [r<sub>i</sub>, c<sub>i</sub>]</code> represents that on the <code>i<sup>th</sup></code> day, the cell on the <code>r<sub>i</sub><sup>th</sup></code> row and <code>c<sub>i</sub><sup>th</sup></code> column (<strong>1-based</strong> coordinates) will be covered with <strong>water</strong> (i.e., changed to <code>1</code>).</p>

<p>You want to find the <strong>last</strong> day that it is possible to walk from the <strong>top</strong> to the <strong>bottom</strong> by only walking on land cells. You can start from <strong>any</strong> cell in the top row and end at <strong>any</strong> cell in the bottom row. You can only travel in the<strong> four</strong> cardinal directions (left, right, up, and down).</p>

<p>Return <em>the <strong>last</strong> day where it is possible to walk from the <strong>top</strong> to the <strong>bottom</strong> by only walking on land cells</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/27/1.png" style="width: 624px; height: 162px;" />
<pre>
<strong>Input:</strong> row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> The above image depicts how the matrix changes each day starting from day 0.
The last day where it is possible to cross from top to bottom is on day 2.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/27/2.png" style="width: 504px; height: 178px;" />
<pre>
<strong>Input:</strong> row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]]
<strong>Output:</strong> 1
<strong>Explanation:</strong> The above image depicts how the matrix changes each day starting from day 0.
The last day where it is possible to cross from top to bottom is on day 1.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/27/3.png" style="width: 666px; height: 167px;" />
<pre>
<strong>Input:</strong> row = 3, col = 3, cells = [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> The above image depicts how the matrix changes each day starting from day 0.
The last day where it is possible to cross from top to bottom is on day 3.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= row, col &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>4 &lt;= row * col &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>cells.length == row * col</code></li>
	<li><code>1 &lt;= r<sub>i</sub> &lt;= row</code></li>
	<li><code>1 &lt;= c<sub>i</sub> &lt;= col</code></li>
	<li>All the values of <code>cells</code> are <strong>unique</strong>.</li>
</ul>

class UnionFind:

    # Time complexity: O(nm).
    # Space complexity: O(nm).
    def __init__(self, rows: int, columns: int) -> None:
        self.parent = {}
        self.size = {}
        for row in range(rows):
            for column in range(columns):
                self.parent[(row, column)] = (row, column)
                self.size[(row, column)] = 1
    
        # Key point: Add virtual left and right nodes to tell if water covers the matrix from side-to-side.
        self._left_node = (rows // 2, -float("inf"))
        self._right_node = (rows // 2, float("inf"))
        self.parent[self._left_node] = self._left_node
        self.parent[self._right_node] = self._right_node
        self.size[self._left_node] = 0
        self.size[self._right_node] = 0

    @property
    def left_node(self) -> tuple[int, int]:
        return self._left_node

    @property
    def right_node(self) -> tuple[int, int]:
        return self._right_node    # Time complexity: O(alpha(nm)) ~ O(1).

    # Space complexity: O(1)
    def find(self, node: tuple[int, int]) -> int:
        """Find the root representative of the disjoint set an element belongs to."""
        # If the element is not equal to its parent, recursively search for the root
        # and set the parent of the current element to the root (path compression).
        if self.parent[node] != node:
            self.parent[node] = self.find(self.parent[node])
        return self.parent[node]
    
    # Time complexity: O(alpha(nm)) ~ O(1).
    # Space complexity: O(1)
    def union(self, node1: tuple[int, int], node2: tuple[int, int]) -> None:
        """Union the sets two nodes belong to."""
        root1 = self.find(node1)
        root2 = self.find(node2)

        # If the two roots are different, the nodes belong to different sets.
        # Join the two by setting the parent of the root with less nodes to the other root (union by size).
        if root1 != root2:
            if self.size[root1] <= self.size[root1]:
                self.parent[root1] = root2
                self.size[root2] += self.size[root1]
            else:
                self.parent[root2] = root1
                self.size[root1] += self.size[root2]


class Solution:

    # Problem type: Union-find.
    # Time complexity:
    # Space complexity:
    def latestDayToCross(self, rows: int, columns: int, water: List[List[int]]) -> int:
        """Return the last day we can cross from the top row to the bottom row of a binary matrix."""
        # 1) Initialize matrix with all land cells.
        matrix = [[0] * columns for _ in range(rows)]
        water_directions = ((1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1))

        # 2) Iteratively fill water cells day by day, joining with any 8-directionally adjacent water cells.
        union_find = UnionFind(rows, columns)
        day = 0
        for row, column in water:
            # Rows and columns in the water array are 1-indexed.
            row, column = row - 1, column - 1

            # Fill the current cell with water and join with any 8-directionally adjacent water cells.
            matrix[row][column] = 1
            for row_step, column_step in water_directions:
                adjacent_row = row + row_step
                adjacent_column = column + column_step
                if 0 <= adjacent_row < rows and 0 <= adjacent_column < columns:
                    if matrix[adjacent_row][adjacent_column] == 1:
                        union_find.union(
                            (row, column),
                            (adjacent_row, adjacent_column),
                        )
    
            # Key point:
            # - If the current water cell is on the left hand side, join with the virtual left node.
            # - If the current water cell is on the right hand side, join with the virtual right node.
            if column == 0:
                union_find.union(union_find.left_node, (row, column))
            elif column == columns - 1:
                union_find.union((row, column), union_find.right_node)

            # Check if water covers the entire grid from left to right.
            if union_find.find(union_find.left_node) == union_find.find(union_find.right_node):
                break
            # Otherwise, we can cross on this day.
            else:
                day += 1
        return day
1279