<p>You are given a <strong>0-indexed</strong> <code>m x n</code> binary matrix <code>land</code> where a <code>0</code> represents a hectare of forested land and a <code>1</code> represents a hectare of farmland.</p>

<p>To keep the land organized, there are designated rectangular areas of hectares that consist <strong>entirely</strong> of farmland. These rectangular areas are called <strong>groups</strong>. No two groups are adjacent, meaning farmland in one group is <strong>not</strong> four-directionally adjacent to another farmland in a different group.</p>

<p><code>land</code> can be represented by a coordinate system where the top left corner of <code>land</code> is <code>(0, 0)</code> and the bottom right corner of <code>land</code> is <code>(m-1, n-1)</code>. Find the coordinates of the top left and bottom right corner of each <strong>group</strong> of farmland. A <strong>group</strong> of farmland with a top left corner at <code>(r<sub>1</sub>, c<sub>1</sub>)</code> and a bottom right corner at <code>(r<sub>2</sub>, c<sub>2</sub>)</code> is represented by the 4-length array <code>[r<sub>1</sub>, c<sub>1</sub>, r<sub>2</sub>, c<sub>2</sub>].</code></p>

<p>Return <em>a 2D array containing the 4-length arrays described above for each <strong>group</strong> of farmland in </em><code>land</code><em>. If there are no groups of farmland, return an empty array. You may return the answer in <strong>any order</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/27/screenshot-2021-07-27-at-12-23-15-copy-of-diagram-drawio-diagrams-net.png" style="width: 300px; height: 300px;" />
<pre>
<strong>Input:</strong> land = [[1,0,0],[0,1,1],[0,1,1]]
<strong>Output:</strong> [[0,0,0,0],[1,1,2,2]]
<strong>Explanation:</strong>
The first group has a top left corner at land[0][0] and a bottom right corner at land[0][0].
The second group has a top left corner at land[1][1] and a bottom right corner at land[2][2].
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/27/screenshot-2021-07-27-at-12-30-26-copy-of-diagram-drawio-diagrams-net.png" style="width: 200px; height: 200px;" />
<pre>
<strong>Input:</strong> land = [[1,1],[1,1]]
<strong>Output:</strong> [[0,0,1,1]]
<strong>Explanation:</strong>
The first group has a top left corner at land[0][0] and a bottom right corner at land[1][1].
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/27/screenshot-2021-07-27-at-12-32-24-copy-of-diagram-drawio-diagrams-net.png" style="width: 100px; height: 100px;" />
<pre>
<strong>Input:</strong> land = [[0]]
<strong>Output:</strong> []
<strong>Explanation:</strong>
There are no groups of farmland.
</pre>

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

<ul>
	<li><code>m == land.length</code></li>
	<li><code>n == land[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 300</code></li>
	<li><code>land</code> consists of only <code>0</code>&#39;s and <code>1</code>&#39;s.</li>
	<li>Groups of farmland are <strong>rectangular</strong> in shape.</li>
</ul>

class Solution:
    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
        # bfs: new dir (0, 1), (1, 0); the first and last coord
        #   O(m*n), O(min(m, n))
        # dfs: track max-coord; O(m*n), O(m*n)
        # union find: for each group and track its smllest and largest coord
        #   O(m*n*alpha(m, n)), O(m*n)
        # greedy, for the topleft to topright, ;
        #                 topleft to bottomleft; fillallwith zero
        #         two loops each [0], break
        #  O(m*n), O(1)

        if not land or not land[0]:
            return []

        M, N = len(land), len(land[0])

        def dfs(row: int, col: int, group: int) -> None:
            # return top-right
            nonlocal r2, c2
            land[row][col] = group
            r2, c2 = max(r2, row), max(c2, col)
            for dr, dc in (0, 1), (0, -1), (1, 0), (-1, 0):
                row2, col2 = row + dr, col + dc
                if 0 <= row2 < M and 0 <= col2 < N and land[row2][col2] == 1:
                    dfs(row2, col2, group)
                    
            

        ans = []
        group = 2
        for i in range(M):
            for j in range(N):
                if land[i][j] == 1:
                    r2, c2 = i, j
                    dfs(i, j, group)
                    ans.append([i, j, r2, c2])
                    group += 1
        return ans

    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
        if not land or not land[0]:
            return []

        M, N = len(land), len(land[0])

        VISITED = 2
        ans = []
        for i in range(M):
            for j in range(N):
                if land[i][j] == 1:
                    queue = collections.deque([(i, j)])
                    land[i][j] = VISITED

                    r, c = i, j
                    while queue:
                        if len(queue) > 2 * min(M, N):
                            raise RuntimeError(f"{len(queue)}, {M}, {N}")
                        r, c = queue.popleft()
                        if r + 1 < M and land[r + 1][c] == 1:
                            queue.append((r + 1, c))
                            land[r + 1][c] = VISITED
                        if c + 1 < N and land[r][c + 1] == 1:
                            queue.append((r, c + 1))
                            land[r][c + 1] = VISITED
                    
                    ans.append([i, j, r, c])
        return ans

    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
        if not land or not land[0]:
            return []

        ans = []
        M, N = len(land), len(land[0])
        for i in range(M):
            for j in range(N):
                if land[i][j] == 1:
                    r2 = i
                    while r2 < M and land[r2][j] == 1:
                        c2 = j
                        while c2 < N and land[r2][c2] == 1:
                            land[r2][c2] = 0
                            c2 += 1
                        r2 += 1
                    ans.append([i, j, r2 - 1, c2 - 1])
        return ans
                    
    




354