Skip to content

1992. Find All Groups of Farmland 👍

  • Time: $O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
 public:
  vector<vector<int>> findFarmland(vector<vector<int>>& land) {
    vector<vector<int>> ans;

    for (int i = 0; i < land.size(); ++i)
      for (int j = 0; j < land[0].size(); ++j)
        if (land[i][j] == 1) {
          int x = i;
          int y = j;
          dfs(land, i, j, x, y);
          ans.push_back({i, j, x, y});
        }

    return ans;
  }

 private:
  void dfs(vector<vector<int>>& land, int i, int j, int& x, int& y) {
    if (i < 0 || i == land.size() || j < 0 || j == land[0].size())
      return;
    if (land[i][j] != 1)
      return;
    land[i][j] = 2;  // Mark as visited.
    x = max(x, i);
    y = max(y, j);
    dfs(land, i + 1, j, x, y);
    dfs(land, i, j + 1, x, y);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
  public int[][] findFarmland(int[][] land) {
    List<int[]> ans = new ArrayList<>();

    for (int i = 0; i < land.length; ++i)
      for (int j = 0; j < land[0].length; ++j)
        if (land[i][j] == 1) {
          int[] cell = new int[] {i, j};
          dfs(land, i, j, cell);
          ans.add(new int[] {i, j, cell[0], cell[1]});
        }

    return ans.stream().toArray(int[][] ::new);
  }

  private void dfs(int[][] land, int i, int j, int[] cell) {
    if (i < 0 || i == land.length || j < 0 || j == land[0].length)
      return;
    if (land[i][j] != 1)
      return;
    land[i][j] = 2; // Mark as visited.
    cell[0] = Math.max(cell[0], i);
    cell[1] = Math.max(cell[1], j);
    dfs(land, i + 1, j, cell);
    dfs(land, i, j + 1, cell);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def findFarmland(self, land: list[list[int]]) -> list[list[int]]:
    ans = []

    def dfs(i: int, j: int, cell: list[int]) -> None:
      if i < 0 or i == len(land) or j < 0 or j == len(land[0]):
        return
      if land[i][j] != 1:
        return
      land[i][j] = 2  # Mark as visited.
      cell[0] = max(cell[0], i)
      cell[1] = max(cell[1], j)
      dfs(i + 1, j, cell)
      dfs(i, j + 1, cell)

    for i in range(len(land)):
      for j in range(len(land[0])):
        if land[i][j] == 1:
          cell = [i, j]
          dfs(i, j, cell)
          ans.append([i, j, *cell])

    return ans