Find all groups of farmland

Array Depth-First Search Breadth-First Search Matrix

75.5% acceptance

Feb 25, 2026

1441

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn find_farmland(land: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let m = land.len();
    let n = land[0].len();
    let mut visited = vec![vec![false; n]; m];
    let mut result = vec![];
    
    for i in 0..m {
      for j in 0..n {
        if land[i][j] == 1 && !visited[i][j] {
          // Find bottom-right corner of this rectangular group
          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 r in i..=r2 {
            for c in j..=c2 {
              visited[r][c] = true;
            }
          }
          result.push(vec![i as i32, j as i32, r2 as i32, c2 as i32]);
        }
      }
    }
    result
  }
}