Find All Groups of Farmland — Medium Problem & Solution

land[i][j] is 1 for farmland and 0 for forest. Farmland forms rectangular groups, and no two groups touch — not even diagonally.

Difficulty: Medium
Topics: Arrays, Matrix, Breadth-First Search, Depth-First Search
Asked at: Amazon, Google, Walmart
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

land[i][j] is 1 for farmland and 0 for forest. Farmland forms rectangular groups, and no two groups touch — not even diagonally.

Return one entry [r1, c1, r2, c2] per group, giving its top-left and bottom-right corners, ordered by where the top-left corner appears in a row-by-row scan.

Example 1

Input: land = [[1,0,0],[0,1,1],[0,1,1]]
Output: [[0,0,0,0],[1,1,2,2]]
Explanation: A single cell and a 2 × 2 block.

Example 2

Input: land = [[1,1],[1,1]]
Output: [[0,0,1,1]]

Example 3

Input: land = [[0]]
Output: []
Explanation: No farmland at all.

Constraints

m == land.length
n == land[i].length
1 <= m, n <= 300
land[i][j] is 0 or 1
Every group of farmland is rectangular and no two groups are adjacent, even diagonally.

How to solve Find All Groups of Farmland

The rectangle guarantee turns a connected-components problem into a scan. Each group has exactly one top-left corner, identified by a local test, and its extent follows from two straight walks.

Approach

Scan row by row. A cell is a top-left corner if it is farmland and the cells above and to the left are forest or off the grid.
Walk down the same column while the cells are farmland to find r2.
Walk right along the same row to find c2.
Record [r1, c1, r2, c2].

Why it works

In a rectangle only the top-left cell has forest both above and to the left, so the test fires exactly once per group — which is what makes the row-major scan order well defined. The two walks are enough because the group is a full rectangle: its height is the run down the left column and its width the run along the top row.

Complexity

Time — O(m · n)
Space — O(1) beyond the output

Pitfalls

A flood fill also works but is more code and needs a visited grid.
The corner test must treat the grid border as forest.
A grid with no farmland returns an empty list, not a list with an empty entry.

Reference solution

Python

from typing import List

def findFarmland(land: List[List[int]]) -> List[List[int]]:
    m, n = len(land), len(land[0])
    out = []
    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 = i
                while r + 1 < m and land[r + 1][j] == 1:
                    r += 1
                c = j
                while c + 1 < n and land[i][c + 1] == 1:
                    c += 1
                out.append([i, j, r, c])
    return out

JavaScript

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

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue