Find All Groups of Farmland

Medium
906.

Find All Groups of Farmland

Find All Groups of Farmland is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon, Google and Walmart interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} land
 * @return {number[][]}
 */
var findFarmland = function(land) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find All Groups of Farmland — Solution in Python, Java & C++

Find All Groups of Farmland solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Find All Groups of Farmland is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon, Google and Walmart interviews.

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.

Hints for Find All Groups of Farmland

  1. Hint 1

    Because groups are rectangles, no flood fill is needed — the corners can be read off directly.

  2. Hint 2

    A cell is a group's top-left corner when it is farmland with forest (or the border) above and to its left.

  3. Hint 3

    From there, walk down and right to find the opposite corner.

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

  1. 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.
  2. Walk down the same column while the cells are farmland to find r2.
  3. Walk right along the same row to find c2.
  4. 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

Java

public static int[][] findFarmland(int[][] land) {
    int m = land.length, n = land[0].length;
    List<int[]> out = new 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;
                while (r + 1 < m && land[r + 1][j] == 1) r++;
                int c = j;
                while (c + 1 < n && land[i][c + 1] == 1) c++;
                out.add(new int[] { i, j, r, c });
            }
        }
    }
    return out.toArray(new int[0][]);
}

C++

vector<vector<int>> findFarmland(vector<vector<int>>& land) {
    int m = (int) land.size(), n = (int) land[0].size();
    vector<vector<int>> out;
    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;
                while (r + 1 < m && land[r + 1][j] == 1) r++;
                int c = j;
                while (c + 1 < n && land[i][c + 1] == 1) c++;
                out.push_back({ 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Depth-First Search (DFS)