<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 UnionFind:
    def __init__(self, nodeList: List[Tuple[int]], n: int):
        self.cells = nodeList
        self.parent = defaultdict(tuple)
        self.rank = defaultdict(int)
        for cell in self.cells:
            self.parent[cell] = cell
            self.rank[cell] = 1
        self.setSize = n
    def find(self, node: Tuple[int]) -> Tuple[int]:
        if node == self.parent[node]:
            return node
        self.parent[node] = self.find(self.parent[node])
        return self.parent[node]
    def union(self, node1: Tuple[int], node2: Tuple[int]) -> None:
        node1 = self.find(node1)
        node2 = self.find(node2)
        if node1 != node2:
            if self.rank[node1] >= self.rank[node2]:
                self.rank[node1] += self.rank[node2]
                self.parent[node2] = node1
            else:
                self.rank[node2] += self.rank[node1]
                self.parent[node1] = node2
            self.setSize -= 1
        return
class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        # This problem can be solved using Union Find.
        # We will check for the parent of cells of first row and last row land cells. If any of them have the same parent, it means its possible to reach last row from first row. Do it by iterating over all the cells from the end and keep on adding edges of land cell being added. Stop till we have the same parent.
        # Return the ith day.
        # Time complexity - O(c*m + mn), Space complexity - O(mn)
        def checkValidCell(cell: Tuple[int]) -> bool:
            nonlocal row, col
            r = cell[0]
            c = cell[1]
            if r <=0 or r > row or c <= 0 or c > col:
                return False
            return True
        def getEdgeList(landCells: Set[Tuple[int]]) -> List[List[Tuple[int]]]:
            edges = []
            directionVector = [(1,0), (-1,0), (0,1), (0,-1)]
            for cell in landCells:
                for r,c in directionVector:
                    neighbourCell = (cell[0] + r, cell[1] + c)
                    if checkValidCell(neighbourCell) and neighbourCell in landCells:
                        edges.append([cell, neighbourCell])
            return edges
        def checkLastRowReachable(landCells: Set[Tuple[int]], ufObj: UnionFind) -> bool:
            nonlocal row, col
            firstRow = [(1,c) for c in range(1,col+1)]
            lastRow = [(row,c) for c in range(1,col+1)]
            firstRowParentCells = set()
            lastRowParentCells = set()
            for cell in firstRow:
                if cell in landCells:
                    firstRowParentCells.add(ufObj.find(cell))
            for cell in lastRow:
                if cell in landCells:
                    lastRowParentCells.add(ufObj.find(cell))
            return firstRowParentCells & lastRowParentCells
        def addLandCellToMatrix(cell: Tuple[int], landCells: Set[Tuple[int]], ufObj: UnionFind) -> None:
            landCells.add(cell)
            directionVector = [(1,0), (-1,0), (0,1), (0,-1)]
            for r,c in directionVector:
                neighbourCell = (cell[0]+r, cell[1]+c)
                if neighbourCell in landCells:
                    ufObj.union(cell, neighbourCell)
            return
        landCells = set()
        for r in range(1, row+1):
            for c in range(1, col+1):
                landCells.add((r,c))
        for cell in cells:
            landCells.remove(tuple(cell))
        cellList = [(r,c) for r in range(1,row+1) for c in range(1, col+1)]
        ufObj = UnionFind(cellList, len(cellList))
        edges = getEdgeList(landCells)
        for edge in edges:
            ufObj.union(edge[0], edge[1])
        lastDay = len(cells)
        while True:
            if checkLastRowReachable(landCells, ufObj):
                break;
            addLandCellToMatrix(tuple(cells[lastDay - 1]), landCells, ufObj)
            lastDay -= 1
        return lastDay
28200