Find All Groups of Farmland

medium array dfs bfs matrix

Problem

Given a binary grid, each rectangular group of 1s represents a farmland with no other farmland adjacent. Return [r1, c1, r2, c2] for each block.

Inputland = [[1,0,0],[0,1,1],[0,1,1]]

Output[[0,0,0,0],[1,1,2,2]]

Two rectangles: a 1×1 at (0,0) and a 2×2 spanning rows 1–2, cols 1–2.

grid (rows separated by ;)

def find_farmland(land):
    m, n = len(land), len(land[0])
    res = []
    for i in range(m):
        for j in range(n):
            if land[i][j] == 1 and (i == 0 or land[i-1][j] == 0) and (j == 0 or land[i][j-1] == 0):
                r, c = i, j
                while r + 1 < m and land[r+1][j] == 1: r += 1
                while c + 1 < n and land[i][c+1] == 1: c += 1
                res.append([i, j, r, c])
    return res

function findFarmland(land) {
  const m = land.length, n = land[0].length, res = [];
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (land[i][j] === 1 && (i === 0 || land[i - 1][j] === 0) && (j === 0 || land[i][j - 1] === 0)) {
        let r = i, c = j;
        while (r + 1 < m && land[r + 1][j] === 1) r++;
        while (c + 1 < n && land[i][c + 1] === 1) c++;
        res.push([i, j, r, c]);
      }
    }
  }
  return res;
}

class Solution {
    public int[][] findFarmland(int[][] land) {
        int m = land.length, n = land[0].length;
        java.util.List<int[]> res = new java.util.ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (land[i][j] == 1 && (i == 0 || land[i - 1][j] == 0) && (j == 0 || land[i][j - 1] == 0)) {
                    int r = i, c = j;
                    while (r + 1 < m && land[r + 1][j] == 1) r++;
                    while (c + 1 < n && land[i][c + 1] == 1) c++;
                    res.add(new int[]{ i, j, r, c });
                }
            }
        }
        return res.toArray(new int[0][]);
    }
}

vector<vector<int>> findFarmland(vector<vector<int>>& land) {
    int m = land.size(), n = land[0].size();
    vector<vector<int>> res;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (land[i][j] == 1 && (i == 0 || land[i - 1][j] == 0) && (j == 0 || land[i][j - 1] == 0)) {
                int r = i, c = j;
                while (r + 1 < m && land[r + 1][j] == 1) r++;
                while (c + 1 < n && land[i][c + 1] == 1) c++;
                res.push_back({ i, j, r, c });
            }
        }
    }
    return res;
}

Explanation

Every farmland is a solid rectangle of 1s, so we do not even need a flood fill. We just need to find each rectangle's top-left corner and then measure how far it stretches.

Scanning row by row, a cell (i, j) is a top-left corner when it is land and there is no land directly above it (i==0 or land[i-1][j]==0) and none directly to its left (j==0 or land[i][j-1]==0). That condition uniquely picks the corner of each block.

From that corner we walk straight down while cells are 1 to find the bottom row r, and straight right to find the rightmost column c. Since the block is a full rectangle, those two edges fully describe it, and we record [i, j, r, c].

Example: land=[[1,0,0],[0,1,1],[0,1,1]]. Cell (0,0) is a corner with no land below or right of it, giving the 1×1 rectangle [0,0,0,0]. Cell (1,1) is the corner of the 2×2 block, giving [1,1,2,2].

Each cell is checked a constant number of times, so one grid scan finds every farmland with no extra bookkeeping.

Time: O(m·n) Space: O(1) extra