# Find All Groups of Farmland
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-all-groups-of-farmland)
Canonical: https://scaleengineer.com/dsa/problems/find-all-groups-of-farmland
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Matrix
**Companies:** [Citrix](https://scaleengineer.com/companies/citrix)
---
## Problem
You are given a **0-indexed** `m x n` binary matrix `land` where a `0` represents a hectare of forested land and a `1` represents a hectare of farmland.

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

`land` can be represented by a coordinate system where the top left corner of `land` is `(0, 0)` and the bottom right corner of `land` is `(m-1, n-1)`. Find the coordinates of the top left and bottom right corner of each **group** of farmland. A **group** of farmland with a top left corner at `(r1, c1)` and a bottom right corner at `(r2, c2)` is represented by the 4-length array `[r1, c1, r2, c2].`

Return _a 2D array containing the 4-length arrays described above for each **group** of farmland in_ `land`_. If there are no groups of farmland, return an empty array. You may return the answer in **any order**_.

**Example 1:**

![](https://assets.glich.co/dsa/find-all-groups-of-farmland/image0.png) 

**Input:** land = [[1,0,0],[0,1,1],[0,1,1]]
**Output:** [[0,0,0,0],[1,1,2,2]]
**Explanation:**
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].

**Example 2:**

![](https://assets.glich.co/dsa/find-all-groups-of-farmland/image1.png) 

**Input:** land = [[1,1],[1,1]]
**Output:** [[0,0,1,1]]
**Explanation:**
The first group has a top left corner at land[0][0] and a bottom right corner at land[1][1].

**Example 3:**

![](https://assets.glich.co/dsa/find-all-groups-of-farmland/image2.png) 

**Input:** land = [[0]]
**Output:** []
**Explanation:**
There are no groups of farmland.

**Constraints:**

* `m == land.length`
* `n == land[i].length`
* `1 <= m, n <= 300`
* `land` consists of only `0`'s and `1`'s.
* Groups of farmland are **rectangular** in shape.

# Approaches
## Graph Traversal (DFS/BFS) with Visited Matrix
This approach models the grid as a graph, where each cell containing a '1' is a node, and adjacent '1's are connected by edges. We traverse the grid cell by cell. When we encounter a '1' that hasn't been visited yet, we initiate a graph traversal algorithm like Depth-First Search (DFS) or Breadth-First Search (BFS) from that cell. This traversal explores the entire connected component of farmland. During the search, we keep track of the maximum row and column indices to identify the bottom-right corner of the rectangular group. A separate boolean matrix, `visited`, is used to ensure that each cell is processed only once.
**Time:** O(m * n), where `m` is the number of rows and `n` is the number of columns. Each cell is visited a constant number of times. · **Space:** O(m * n) to store the `visited` matrix. The recursion stack for DFS (or queue for BFS) can also grow up to `O(m * n)` in the worst case.
**Pros:** It's a standard and general approach for finding connected components in a grid.; Does not modify the original input `land` matrix.
**Cons:** Requires extra space for the `visited` matrix, leading to `O(m * n)` space complexity.; The recursive DFS might lead to a stack overflow for very large groups, although the constraints `m, n <= 300` make this unlikely.; It's less efficient than necessary because the problem guarantees rectangular, non-adjacent groups, which allows for a simpler search than a full DFS/BFS.
### Explanation
We iterate through the `land` matrix. If we find a cell `(r, c)` with a '1' that we haven't visited, we know it's the top-left corner of a new group. We then start a DFS from `(r, c)`. The DFS will explore all reachable '1's from this starting point. We pass a reference to an array (e.g., `maxCoords`) to the DFS function to keep track of the maximum row and column index seen so far in the current component. The DFS function marks the current cell as visited, updates `maxCoords`, and recursively calls itself for all four neighbors. Once the DFS for a component is complete, `(r, c)` is the top-left corner and `(maxCoords[0], maxCoords[1])` is the bottom-right corner. We add these coordinates to our result list. This process continues until the entire grid has been scanned.

```java
class Solution {
    public int[][] findFarmland(int[][] land) {
        int m = land.length;
        int n = land[0].length;
        boolean[][] visited = new boolean[m][n];
        List<int[]> result = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (land[i][j] == 1 && !visited[i][j]) {
                    int[] maxCoords = new int[]{i, j}; // [max_r, max_c]
                    dfs(land, visited, i, j, maxCoords);
                    result.add(new int[]{i, j, maxCoords[0], maxCoords[1]});
                }
            }
        }
        return result.toArray(new int[result.size()][]);
    }

    private void dfs(int[][] land, boolean[][] visited, int r, int c, int[] maxCoords) {
        int m = land.length;
        int n = land[0].length;

        if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] || land[r][c] == 0) {
            return;
        }

        visited[r][c] = true;
        maxCoords[0] = Math.max(maxCoords[0], r);
        maxCoords[1] = Math.max(maxCoords[1], c);

        dfs(land, visited, r + 1, c, maxCoords);
        dfs(land, visited, r - 1, c, maxCoords);
        dfs(land, visited, r, c + 1, maxCoords);
        dfs(land, visited, r, c - 1, maxCoords);
    }
}
```
### Algorithm
*   Initialize an `m x n` boolean matrix `visited` to all `false`.
*   Initialize an empty list `result` to store the coordinates.
*   Iterate through each cell `(r, c)` of the `land` matrix.
*   If `land[r][c] == 1` and `visited[r][c]` is `false`:
    *   This is a new group. The top-left corner is `(r, c)`.
    *   Initialize `max_r = r` and `max_c = c`.
    *   Start a DFS/BFS from `(r, c)`. In the traversal, for each cell `(curr_r, curr_c)`:
        *   Mark `(curr_r, curr_c)` as visited.
        *   Update `max_r = max(max_r, curr_r)` and `max_c = max(max_c, curr_c)`.
        *   Explore its unvisited '1' neighbors.
    *   After the traversal, add `[r, c, max_r, max_c]` to `result`.
*   Return `result`.

## Greedy Scan with In-place Modification
This is a more efficient approach that leverages the specific properties of the problem: the farmland groups are rectangular and non-adjacent. We can iterate through the grid, and whenever we find a '1', we can be certain it's the top-left corner of a new group. This is because if there were a '1' to its top or left, we would have already processed it in our top-to-bottom, left-to-right scan. Once a top-left corner is found, we can easily find the bottom-right corner by just extending downwards and rightwards. To avoid re-processing the same group, we modify the input grid by changing the '1's of the found group to '0's. This eliminates the need for an auxiliary `visited` matrix.
**Time:** O(m * n). Each cell is visited a constant number of times. Although there are nested loops for clearing the rectangle, each '1' cell is part of exactly one rectangle and will be cleared only once. · **Space:** O(1) auxiliary space. The space for the result list depends on the number of farmland groups, but no extra data structures proportional to the grid size are needed.
**Pros:** Highly space-efficient, using `O(1)` auxiliary space (if the output list is not counted).; Very fast and efficient as it's tailored to the problem's specific constraints (rectangular, non-adjacent groups).; The logic is simple and avoids the overhead of recursion or an explicit stack/queue.
**Cons:** Modifies the input grid, which may be undesirable in some scenarios where the original data must be preserved.
### Explanation
The core idea is to find the top-left corner of a rectangle, determine its full extent, record it, and then "erase" it from the grid to ensure it's not processed again. We iterate through the grid with nested loops. When `land[r][c]` is '1', we've found a top-left corner. We then find the bottom-most row `r2` of this rectangle by scanning down from `(r, c)`. Similarly, we find the right-most column `c2` by scanning right from `(r, c)`. The coordinates `[r, c, r2, c2]` define the group. After recording the group, we iterate through this `(r, c)` to `(r2, c2)` subgrid and set all `land` values to '0'. This acts as our "visited" marker. Because we clear the found rectangles, any '1' we encounter later in the main scan is guaranteed to be a new top-left corner.

```java
class Solution {
    public int[][] findFarmland(int[][] land) {
        int m = land.length;
        int n = land[0].length;
        List<int[]> result = new ArrayList<>();

        for (int r1 = 0; r1 < m; r1++) {
            for (int c1 = 0; c1 < n; c1++) {
                if (land[r1][c1] == 1) {
                    // Found the top-left corner of a group
                    int r2 = r1;
                    int c2 = c1;

                    // Find the bottom-right corner
                    // Since it's a rectangle, we only need to check one column to find the last row
                    // and one row to find the last column.
                    while (r2 + 1 < m && land[r2 + 1][c1] == 1) {
                        r2++;
                    }
                    while (c2 + 1 < n && land[r1][c2 + 1] == 1) {
                        c2++;
                    }
                    
                    result.add(new int[]{r1, c1, r2, c2});

                    // Mark this farmland as visited by changing 1s to 0s
                    for (int i = r1; i <= r2; i++) {
                        for (int j = c1; j <= c2; j++) {
                            land[i][j] = 0;
                        }
                    }
                }
            }
        }
        return result.toArray(new int[result.size()][]);
    }
}
```
### Algorithm
*   Initialize an empty list `result`.
*   Iterate `r` from `0` to `m-1`.
*   Iterate `c` from `0` to `n-1`.
*   If `land[r][c] == 1`:
    *   This is the top-left corner `(r1, c1) = (r, c)`.
    *   Find the bottom-right corner `(r2, c2)`.
    *   Initialize `r2 = r`, `c2 = c`.
    *   Extend downwards: while `r2 + 1 < m` and `land[r2 + 1][c] == 1`, increment `r2`.
    *   Extend rightwards: while `c2 + 1 < n` and `land[r][c2 + 1] == 1`, increment `c2`.
    *   Add `[r1, c1, r2, c2]` to `result`.
    *   Mark the rectangle as processed by setting `land[i][j] = 0` for all `i` from `r1` to `r2` and `j` from `c1` to `c2`.

# Solutions
### Java

```java
class Solution {
public
  int[][] findFarmland(int[][] land) {
    List<int[]> ans = new ArrayList<>();
    int m = land.length;
    int n = land[0].length;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (land[i][j] == 0 || (j > 0 && land[i][j - 1] == 1) ||
            (i > 0 && land[i - 1][j] == 1)) {
          continue;
        }
        int x = i;
        int y = j;
        for (; x + 1 < m && land[x + 1][j] == 1; ++x)
          ;
        for (; y + 1 < n && land[x][y + 1] == 1; ++y)
          ;
        ans.add(new int[]{i, j, x, y});
      }
    }
    return ans.toArray(new int[ans.size()][4]);
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> findFarmland(vector<vector<int>> &land) {
    vector<vector<int>> ans;
    int m = land.size();
    int n = land[0].size();
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (land[i][j] == 0 || (j > 0 && land[i][j - 1] == 1) ||
            (i > 0 && land[i - 1][j] == 1))
          continue;
        int x = i;
        int y = j;
        for (; x + 1 < m && land[x + 1][j] == 1; ++x)
          ;
        for (; y + 1 < n && land[x][y + 1] == 1; ++y)
          ;
        ans.push_back({i, j, x, y});
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findFarmland(self, land: List[List[int]]) -> List[List[int]]: m, n = len(land), len(land[0]) ans = [] for i in range(m): for j in range(n): if (land[i][j] == 0 or (j > 0 and land[i][j - 1] == 1) or (i > 0 and land[i - 1][j] == 1)): continue x, y = i, j while x + 1 < m and land[x + 1][j] == 1: x += 1 while y + 1 < n and land[x][y + 1] == 1: y += 1 ans . append([i, j, x, y]) return ans

```