Find All Groups of Farmland - Practice Coding Problems

Find All Groups of Farmland - 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.

Input & Output

Example 1 — Two Separate Groups

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

› Output: [[0,0,0,0],[1,1,2,2]]

💡 Note: First group is single cell at (0,0). Second group forms 2×2 rectangle from (1,1) to (2,2).

Example 2 — Single Large Rectangle

$ Input: land = [[1,1],[1,1]]

› Output: [[0,0,1,1]]

💡 Note: Entire 2×2 matrix is one farmland group with corners at (0,0) and (1,1).

Example 3 — No Farmland

$ Input: land = [[0,0],[0,0]]

› Output: []

💡 Note: No farmland cells found, so return empty array.

Constraints

m == land.length
n == land[i].length
1 ≤ m, n ≤ 300
land[i][j] is 0 or 1
Groups of farmland are rectangular in shape

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

Binary matrix with 1=farmland, 0=forest

Find Groups

Identify connected rectangular farmland regions

Output Coordinates

Return [top-left, bottom-right] for each group

Key Takeaway

🎯 Key Insight: Farmland groups are guaranteed rectangles, so we can find boundaries efficiently without full traversal

Asked in

A Amazon 25 G Google 20 M Microsoft 15 F Facebook 12

The key insight is that farmland groups are guaranteed to be perfect rectangles. Best approach uses direct rectangle detection by expanding right and down from each top-left corner. Time: O(m×n), Space: O(m×n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with DFS	O(m×n)	O(m×n)	For each unvisited farmland cell, use DFS to explore the entire rectangular group
Single Pass Rectangle Detection	O(m×n)	O(m×n)	When we find a farmland cell, immediately determine the full rectangle without DFS

Brute Force with DFS — Algorithm Steps

Iterate through all cells in the matrix
For each unvisited farmland cell, start DFS
During DFS, mark cells as visited and track min/max coordinates
Add rectangle coordinates [r1, c1, r2, c2] to result

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Start

Locate first unvisited farmland cell (1)

DFS Explore

Recursively visit all connected farmland cells

Track Bounds

Record min/max coordinates to form rectangle

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int m, n;
int** visited;
int** land;
int result[1000][4];
int resultCount = 0;

void dfs(int r, int c, int* bounds) {
    if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] || land[r][c] == 0) {
        return;
    }
    
    visited[r][c] = 1;
    if (r < bounds[0]) bounds[0] = r;
    if (c < bounds[1]) bounds[1] = c;
    if (r > bounds[2]) bounds[2] = r;
    if (c > bounds[3]) bounds[3] = c;
    
    dfs(r+1, c, bounds);
    dfs(r-1, c, bounds);
    dfs(r, c+1, bounds);
    dfs(r, c-1, bounds);
}

void solution() {
    resultCount = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (land[i][j] == 1 && !visited[i][j]) {
                int bounds[4] = {i, j, i, j};
                dfs(i, j, bounds);
                result[resultCount][0] = bounds[0];
                result[resultCount][1] = bounds[1];
                result[resultCount][2] = bounds[2];
                result[resultCount][3] = bounds[3];
                resultCount++;
            }
        }
    }
}

int main() {
    // Simplified parsing for basic test cases
    scanf("%d %d", &m, &n);
    
    land = malloc(m * sizeof(int*));
    visited = malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        land[i] = malloc(n * sizeof(int));
        visited[i] = calloc(n, sizeof(int));
        for (int j = 0; j < n; j++) {
            scanf("%d", &land[i][j]);
        }
    }
    
    solution();
    
    printf("[");
    for (int i = 0; i < resultCount; i++) {
        if (i > 0) printf(",");
        printf("[%d,%d,%d,%d]", result[i][0], result[i][1], result[i][2], result[i][3]);
    }
    printf("]\n");
    
    // Free memory
    for (int i = 0; i < m; i++) {
        free(land[i]);
        free(visited[i]);
    }
    free(land);
    free(visited);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n)

Each cell is visited at most twice: once during iteration and once during DFS

✓ Linear Growth

Space Complexity

O(m×n)

Visited array of same size as input matrix plus recursion stack depth

⚡ Linearithmic Space

32.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler