Find All Groups of Farmland: Rectangle Scanning Pattern

You are given a 0-indexed m x n binary matrix land where 0 represents forested land and 1 represents farmland. Groups of farmland are always rectangular regions formed entirely of 1s. No two groups are adjacent (they do not share an edge), so every group is a standalone rectangle. Return an array of [r1, c1, r2, c2] for each group, where (r1, c1) is the top-left corner and (r2, c2) is the bottom-right corner.

This is LeetCode 1992: Find All Groups of Farmland, and it teaches a useful pattern: instead of running a full DFS or BFS to explore a connected region, you can exploit the rectangular structure of the groups to find each one in a single directional scan.

The key insight

Because every farmland group is guaranteed to be a rectangle with no two groups sharing an edge, you do not need flood fill. You just need to find the top-left corner of each rectangle and then expand right and down to find the bottom-right corner.

How do you know if a 1 cell is the top-left corner of a rectangle? Check two things:

1. The cell directly above it (row - 1) is either out of bounds or 0
2. The cell directly to its left (col - 1) is either out of bounds or 0

If both conditions hold, this 1 is the start of a new farmland group. From there, expand right along the same row while cells are 1 to find the rightmost column. Then expand down from that corner while cells are 1 to find the bottommost row. You now have [r1, c1, r2, c2].

The algorithm:

1. Scan every cell in row-major order
2. When you find a 1 that is a top-left corner, expand right then down
3. Record [r1, c1, r2, c2] for that group
4. Continue scanning (cells that belong to already-found groups will fail the top-left corner check)

The solution

def find_farmland(land: list[list[int]]) -> list[list[int]]:
    rows, cols = len(land), len(land[0])
    result = []

    for r in range(rows):
        for c in range(cols):
            if land[r][c] == 0:
                continue

            if r > 0 and land[r - 1][c] == 1:
                continue
            if c > 0 and land[r][c - 1] == 1:
                continue

            r2, c2 = r, c

            while c2 + 1 < cols and land[r][c2 + 1] == 1:
                c2 += 1

            while r2 + 1 < rows and land[r2 + 1][c] == 1:
                r2 += 1

            result.append([r, c, r2, c2])

    return result

Let's walk through this piece by piece.

The outer loop scans every cell in row-major order. If the cell is 0, skip it. If the cell is 1 but has a 1 directly above or directly to its left, it is not a top-left corner, so skip it too.

When you find a genuine top-left corner at (r, c), initialize r2 and c2 to (r, c). Expand c2 to the right while the next cell in the same row is still 1. Then expand r2 downward while the next cell in the same column is still 1. Once both expansions stop, (r2, c2) is the bottom-right corner of this rectangle.

Append [r, c, r2, c2] to the result and keep scanning. Every other cell in this rectangle will fail the top-left corner check because it has a 1 above or to its left.

Visual walkthrough

Let's trace through a 4x5 grid with three farmland groups. Watch how the scanner finds each top-left corner and expands to find the bottom-right.

The scanner moves left to right, top to bottom. Each time it finds a 1 with no 1 above or to the left, it knows it has hit a new rectangle. The expansion step finds the extent of that rectangle in two passes: one rightward, one downward. No recursion, no queue, no visited set.

Complexity analysis

Time is O(m * n). The outer loop visits every cell once. The expansion steps for each group touch cells within that group, and no cell is expanded from more than once. Total work across all expansions is bounded by the number of cells.

Space is O(1) extra (beyond the output array). No visited set, no recursion stack, no queue. The top-left corner check eliminates the need for any auxiliary data structure. If you count the output array, it is O(g) where g is the number of groups, but that is required by the problem.

This is the main advantage over a DFS/BFS approach. Flood fill would work here (find a 1, explore the entire connected region, record the min/max row and column), but it needs O(m * n) space for a visited set. The rectangle scanning approach skips all of that.

The building blocks

This problem is built on two reusable pieces that CodeBricks drills independently:

1. Top-left corner detection

The pattern of identifying the starting cell of a rectangular region by checking its neighbors:

if r > 0 and land[r - 1][c] == 1:
    continue
if c > 0 and land[r][c - 1] == 1:
    continue

This is a boundary condition check. You are asking: "Is this the first cell in this rectangle I would encounter during a row-major scan?" If the cell above is 1, I already passed through this rectangle in a previous row. If the cell to the left is 1, I already passed through it earlier in this row. Either way, skip it.

This same idea appears anytime you need to detect the "start" of a contiguous region during a linear scan, like finding the beginning of a streak in an array.

2. Directional expansion

The pattern of expanding from a known cell in one direction to find the boundary:

while c2 + 1 < cols and land[r][c2 + 1] == 1:
    c2 += 1

while r2 + 1 < rows and land[r2 + 1][c] == 1:
    r2 += 1

This is the same idea as finding the end of a window or the boundary of a region. You start at a known-good position and step forward while the condition holds. The bounds check (c2 + 1 < cols) comes before the value check (land[r][c2 + 1] == 1) to avoid index errors. You will see this expansion pattern in sliding window problems, interval merging, and matrix region detection.

Edge cases

Before submitting, check these:

• Single cell farmland: a lone 1 surrounded by 0s. The expansion finds r2 = r, c2 = c, so you get [r, c, r, c]. Works correctly.
• Entire grid is farmland: every cell is 1. The only top-left corner is (0, 0). Expansion reaches (rows-1, cols-1). Result is [[0, 0, rows-1, cols-1]].
• No farmland: every cell is 0. The inner check land[r][c] == 0 skips everything. Result is [].
• Single row or column: the expansion in one direction finds nothing, and the other direction covers the streak. Works because the while loop simply does not execute when there is nothing to expand into.
• Multiple groups in the same row: each group has a gap of 0s between them. The left-neighbor check correctly identifies each new group's start.

From understanding to recall

You have seen how the top-left corner detection and directional expansion combine to solve this problem without any graph traversal. The key insight, that guaranteed-rectangular groups can be found with a simple scan instead of DFS, is the hard part. The code itself is short and uses no auxiliary data structures.

But can you write the top-left corner check and the two expansion loops from scratch under time pressure? The details matter: checking r > 0 before accessing land[r - 1][c], expanding c2 first then r2, using c2 + 1 < cols as the loop guard. These are recall challenges, not conceptual ones.

Spaced repetition closes that gap. You practice writing the scanner and expansion from memory at increasing intervals. After a few rounds, the pattern is automatic. You see a matrix problem with rectangular regions, and the code flows out without hesitation.

Related posts

• Number of Islands - The foundational grid traversal problem using DFS flood fill, the technique you would use here if groups were not guaranteed to be rectangular
• Surrounded Regions - Another grid problem that exploits structure (border connectivity) to avoid brute-force region tracking
• Pacific Atlantic Water Flow - Multi-source DFS on a grid, showing how to think about reachability from edges inward

CodeBricks breaks Find All Groups of Farmland into its top-left-corner-detection and directional-expansion building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a matrix scanning problem shows up in your interview, you do not think about it. You just write it.