<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>

from collections import defaultdict

class ConnectedComponents:
    def __init__(self):
        self.parent = {}
        self.size = {}
        self.touch_left = {}
        self.touch_right = {}

    def find(self, node):
        if node not in self.parent:
            self.parent[node] = node
        elif node != self.parent[node]:
            self.parent[node] = self.find(self.parent[node])
        return self.parent[node]

    def union(self, node1, node2):
        comp1 = self.find(node1)
        comp2 = self.find(node2)
        if comp1 != comp2:
            if self.size[comp1] >= self.size[comp2]:
                self.parent[comp2] = comp1
                self.size[comp1] += self.size[comp2]
                self.touch_left[comp1] |= self.touch_left[comp2]
                self.touch_right[comp1] |= self.touch_right[comp2]
                return comp1
            else:
                self.parent[comp1] = comp2
                self.size[comp2] += self.size[comp1]
                self.touch_left[comp2] |= self.touch_left[comp1]
                self.touch_right[comp2] |= self.touch_right[comp1]
                return comp2
        else:
            return comp1


class Solution:
    def latestDayToCross(self, row: int, col: int, cells: list[list[int]]) -> int:
        self.nrows = row
        self.ncols = col
        # Per the Hint, use binary search to look for the last (largest) day on
        # which it's still possible to cross, by calling the function "canCross".
        # "canCross" returns True iff one of the top-row cells is in the same
        # connected component (through 4-connected land cells) as one of the
        # bottom-row cells.  Another approach is to solve the dual problem:
        # Find the earliest day at which we can make an 8-connected wter component
        # that spans the left column to the right column.  The advantage of this
        # approach is that it allows the connected component analysis to be
        # done incrementally.  The disadvantage is that having to look at
        # 8-connectedness doubles the search time.
        #
        conn_comps = ConnectedComponents()
        # To satisfy the requirement that water cells span left to right,
        # we have to keep track for each connected component whether it
        # is connected to left column and whether it is connected to the
        # right column.

        map = defaultdict(lambda: 0)
        for i_day in range(row * col):  # Every day, 1 more water cell.
            # Next cell to be flooded on day "i_day":
            cell = tuple(cells[i_day])
            conn_comps.parent[cell] = cell
            conn_comps.size[cell] = 1
            conn_comps.touch_left[cell] = cell[1] == 1
            conn_comps.touch_right[cell] = cell[1] == self.ncols
            map[cell] = 1
            # Look at up to 8 neighbors:
            for drow, dcol in ((0, 1), (-1, 1), (-1, 0), (-1, -1),
                               (0, -1), (1, - 1), (1, 0), (1, 1,)):
                neigh_cell = (cell[0] + drow, cell[1] + dcol)
                # If "cell" and "neigh_cell" are both 1's (water), then
                # group them in the same connected component
                if map[neigh_cell]:
                    if 1 <= neigh_cell[0] <= row and 1 <= neigh_cell[1] <= col:
                        conn_comps.union(cell, neigh_cell)
                    # See whether any connected component of water touches both
                    # left and right wall:
                    cell_comp = conn_comps.find(cell)
                    if conn_comps.touch_left[cell_comp] and conn_comps.touch_right[cell_comp]:
                        return i_day
        return -1

27000