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.

Examples

Example 1:

$$ \begin{bmatrix} 1 & \colorbox{green} 0 & \colorbox{green} 0 \\ \colorbox{green}0 & 1 & 1 \\ \colorbox{green}0 & 1 & 1 \end{bmatrix} $$

1
2
3
4
5

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:

$$ \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} $$

1
2
3
4

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: $$ \begin{bmatrix} \colorbox{green} 0 \end{bmatrix} $$

1
2
3
4

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

Solution

Method 1 – Depth-First Search (DFS) (1)

Intuition

The key idea is to use DFS to find the extent of each farmland group. When a farmland cell is found, expand to the right and down to find the bottom-right corner, marking all visited cells to avoid revisiting.

Approach

  1. Iterate through each cell in the matrix.
  2. When a farmland cell (1) is found, perform DFS to find the bottom-right corner of the group.
  3. Mark all cells in the group as visited (set to 0 or use a visited array).
  4. Record the top-left and bottom-right coordinates.
  5. Continue until all groups are found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    vector<vector<int>> findFarmland(vector<vector<int>>& land) {
        int m = land.size(), n = land[0].size();
        vector<vector<int>> ans;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (land[i][j] == 1) {
                    int r2 = i, c2 = j;
                    // Expand down
                    while (r2 + 1 < m && land[r2 + 1][j] == 1) ++r2;
                    // Expand right
                    while (c2 + 1 < n && land[i][c2 + 1] == 1) ++c2;
                    // Mark all as visited
                    for (int x = i; x <= r2; ++x)
                        for (int y = j; y <= c2; ++y)
                            land[x][y] = 0;
                    ans.push_back({i, j, r2, c2});
                }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func findFarmland(land [][]int) [][]int {
    m, n := len(land), len(land[0])
    var ans [][]int
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if land[i][j] == 1 {
                r2, c2 := i, j
                for r2+1 < m && land[r2+1][j] == 1 {
                    r2++
                }
                for c2+1 < n && land[i][c2+1] == 1 {
                    c2++
                }
                for x := i; x <= r2; x++ {
                    for y := j; y <= c2; y++ {
                        land[x][y] = 0
                    }
                }
                ans = append(ans, []int{i, j, r2, c2})
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int[][] findFarmland(int[][] land) {
        int m = land.length, n = land[0].length;
        List<int[]> ans = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (land[i][j] == 1) {
                    int r2 = i, c2 = j;
                    while (r2 + 1 < m && land[r2 + 1][j] == 1) r2++;
                    while (c2 + 1 < n && land[i][c2 + 1] == 1) c2++;
                    for (int x = i; x <= r2; x++)
                        for (int y = j; y <= c2; y++)
                            land[x][y] = 0;
                    ans.add(new int[]{i, j, r2, c2});
                }
            }
        }
        return ans.toArray(new int[ans.size()][]);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun findFarmland(land: Array<IntArray>): Array<IntArray> {
        val m = land.size
        val n = land[0].size
        val ans = mutableListOf<IntArray>()
        for (i in 0 until m) {
            for (j in 0 until n) {
                if (land[i][j] == 1) {
                    var r2 = i
                    var c2 = j
                    while (r2 + 1 < m && land[r2 + 1][j] == 1) r2++
                    while (c2 + 1 < n && land[i][c2 + 1] == 1) c2++
                    for (x in i..r2) for (y in j..c2) land[x][y] = 0
                    ans.add(intArrayOf(i, j, r2, c2))
                }
            }
        }
        return ans.toTypedArray()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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] == 1:
                    r2, c2 = i, j
                    while r2 + 1 < m and land[r2 + 1][j] == 1:
                        r2 += 1
                    while c2 + 1 < n and land[i][c2 + 1] == 1:
                        c2 += 1
                    for x in range(i, r2 + 1):
                        for y in range(j, c2 + 1):
                            land[x][y] = 0
                    ans.append([i, j, r2, c2])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

impl Solution {
    pub fn find_farmland(mut land: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let m = land.len();
        let n = land[0].len();
        let mut ans = vec![];
        for i in 0..m {
            for j in 0..n {
                if land[i][j] == 1 {
                    let mut r2 = i;
                    let mut c2 = j;
                    while r2 + 1 < m && land[r2 + 1][j] == 1 { r2 += 1; }
                    while c2 + 1 < n && land[i][c2 + 1] == 1 { c2 += 1; }
                    for x in i..=r2 {
                        for y in j..=c2 {
                            land[x][y] = 0;
                        }
                    }
                    ans.push(vec![i as i32, j as i32, r2 as i32, c2 as i32]);
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    findFarmland(land: number[][]): number[][] {
        const m = land.length, n = land[0].length;
        const ans: number[][] = [];
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                if (land[i][j] === 1) {
                    let r2 = i, c2 = j;
                    while (r2 + 1 < m && land[r2 + 1][j] === 1) r2++;
                    while (c2 + 1 < n && land[i][c2 + 1] === 1) c2++;
                    for (let x = i; x <= r2; x++)
                        for (let y = j; y <= c2; y++)
                            land[x][y] = 0;
                    ans.push([i, j, r2, c2]);
                }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(mn), since each cell is visited at most once.
  • 🧺 Space complexity: O(1), ignoring the output array, since we mark cells in-place.