LeetCode 1992 - Find All Groups of Farmland

LeetCode Problem 1992

Difficulty: 🟡 Medium
Topics: Array, Depth-First Search, Breadth-First Search, Matrix

Solution

Problem Understanding

In this problem, we are given a binary matrix called land. Each cell contains either:

• 0, representing forest land
• 1, representing farmland

The farmland cells are organized into rectangular groups. Every group is guaranteed to form a perfect rectangle made entirely of 1s. Additionally, different groups never touch each other in the four cardinal directions, meaning no farmland cell from one group is directly above, below, left, or right of farmland from another group.

Our goal is to identify every farmland rectangle and return its coordinates in the format:

[r1, c1, r2, c2]

where:

• (r1, c1) is the top left corner of the rectangle
• (r2, c2) is the bottom right corner of the rectangle

The answer can be returned in any order.

The matrix dimensions satisfy:

• 1 <= m, n <= 300

This means the matrix can contain up to 90,000 cells. A quadratic or cubic algorithm over the entire matrix could become too slow, so we should aim for a solution that visits each cell only a small number of times.

There are several important observations and guarantees:

• Every farmland group is rectangular
• Different groups never overlap
• Different groups are not adjacent in four directions
• A single farmland cell can itself form a valid rectangle

These guarantees simplify the problem significantly because once we discover the top left corner of a farmland group, we can safely expand rightward and downward to determine the rectangle boundaries.

Some edge cases that could easily cause bugs include:

• A matrix with no farmland at all
• A matrix where the entire grid is one large farmland rectangle
• Single cell farmland groups
• Multiple separated farmland rectangles
• Thin rectangles, such as a single row or single column

A correct implementation must handle all of these situations cleanly. The problem gives a binary matrix representing a piece of land, where 1 indicates farmland and 0 indicates forest. The farmland is not arbitrary; it is organized into disjoint rectangular groups. Each group is a maximal rectangle consisting entirely of 1s, and no two groups touch each other even via four-directional adjacency.

The task is to identify every such rectangle and return its top-left and bottom-right coordinates in the format [r1, c1, r2, c2]. The output order does not matter.

The key constraints are that the matrix can be as large as 300 by 300, and every cell is either 0 or 1. Importantly, groups are guaranteed to be rectangular and non-adjacent, which significantly simplifies detection.

Edge cases include an entirely empty grid, a grid with no farmland, a grid with one large rectangle, and grids where each farmland cell is isolated (each forms a 1x1 rectangle). A naive approach that repeatedly scans or expands from every cell without marking visited nodes efficiently would be too slow if it redundantly processes the same region multiple times.

Approaches

Brute Force Approach

A naive approach would examine every farmland cell and attempt to discover the entire connected component using Depth First Search or Breadth First Search.

For every unvisited 1 cell:

1. Start a DFS or BFS traversal
2. Visit all connected farmland cells
3. Track:

• minimum row
• minimum column
• maximum row
• maximum column

4. Mark all visited cells
5. Store the resulting rectangle

This works because each farmland group is connected and rectangular. By exploring the component, we can determine its boundaries.

However, this solution performs additional traversal overhead and requires an auxiliary visited structure or in-place marking. While still acceptable for the constraints, it does more work than necessary because the problem guarantees that groups are rectangles.

Key Insight for the Optimal Approach

The most important observation is that every farmland group is a rectangle and groups are separated from each other.

This means a farmland group can be uniquely identified by its top left corner.

A cell (r, c) is the top left corner of a farmland group if:

• land[r][c] == 1
• there is no farmland above it
• there is no farmland to its left

In other words:

(r == 0 OR land[r-1][c] == 0)
AND
(c == 0 OR land[r][c-1] == 0)

Once we find such a top left corner, we can:

1. Expand downward to find the last row
2. Expand rightward to find the last column

Because the group is guaranteed to be rectangular, these two boundaries completely determine the rectangle.

This lets us solve the problem in a single pass over the matrix without DFS, BFS, or extra memory.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force DFS/BFS	O(m × n)	O(m × n)	Traverses connected components with visited tracking
Optimal Rectangle Detection	O(m × n)	O(1) extra space	Uses rectangle properties to detect top left corners directly

Algorithm Walkthrough

Step 1: Iterate Through Every Cell

We scan the matrix row by row and column by column.

For every cell (row, col), we check whether it contains farmland:

land[row][col] == 1

Only farmland cells are candidates for starting a rectangle.

Step 2: Identify Whether the Cell Is a Top Left Corner

A farmland cell belongs to exactly one rectangle.

We only want to process each rectangle once, so we detect only the top left corner of each group.

A cell is a top left corner if:

1. It is farmland
2. There is no farmland above it
3. There is no farmland to its left

The conditions are:

(row == 0 or land[row - 1][col] == 0)
and
(col == 0 or land[row][col - 1] == 0)

If either the top or left neighbor is farmland, then this cell belongs somewhere inside an already discovered rectangle.

Step 3: Expand Downward

Once we discover a top left corner, we determine how far the rectangle extends vertically.

Starting from row, keep moving downward while cells remain farmland:

while bottom + 1 < rows and land[bottom + 1][col] == 1:
    bottom += 1

This gives us the bottom boundary.

Step 4: Expand Rightward

Next, determine how far the rectangle extends horizontally.

Starting from col, keep moving right while cells remain farmland:

while right + 1 < cols and land[row][right + 1] == 1:
    right += 1

This gives us the right boundary.

Step 5: Store the Rectangle

Now we know:

• top row = row
• left column = col
• bottom row = bottom
• right column = right

We append:

[row, col, bottom, right]

to the result list.

Step 6: Continue Scanning

We continue scanning the matrix until all cells have been processed.

Because every rectangle has exactly one top left corner, each group is added exactly once.

Why it works

The algorithm relies on the guarantee that every farmland group is a perfect rectangle and that different groups are separated.

Every rectangle has exactly one cell with no farmland above or to the left, namely its top left corner. By detecting only these cells, we process each rectangle once and avoid duplicates.

Once a top left corner is known, expanding downward and rightward correctly identifies the rectangle boundaries because every farmland group is fully rectangular.

Therefore, every farmland group is discovered exactly once with the correct coordinates. A brute force method would iterate over every cell in the matrix. When a 1 is encountered, it would attempt to expand downward and rightward to find the full extent of the rectangle by checking all possible boundaries. After identifying a rectangle, it would still need to mark all its cells as visited or repeatedly re-scan the grid to avoid duplicates.

While this works conceptually, it is inefficient because each cell might be examined multiple times during redundant expansions or scans. Without proper marking, overlapping work becomes expensive. Even with marking, repeated boundary scanning from multiple cells can degrade performance.

Optimal Approach Insight

The key observation is that each farmland group is a perfect rectangle and groups do not touch. This means each rectangle has a unique top-left corner that is not adjacent above or to the left. Therefore, whenever we find a 1 that is not yet visited, it must be the top-left corner of a new rectangle.

From that starting point, we only need to expand rightwards to find the column boundary and downwards to find the row boundary. Once we determine the bottom-right corner, we can mark the entire rectangle as visited in one traversal.

This ensures each cell is processed exactly once.

Complexity Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m²n²) in worst case	O(1) or O(mn)	Repeated boundary scanning and redundant exploration
Optimal DFS Expansion	O(mn)	O(1) extra (excluding recursion stack)	Each cell visited once, rectangle expanded from top-left

Algorithm Walkthrough

The optimal algorithm proceeds as follows:

1. Iterate over every cell (r, c) in the matrix. This ensures we examine every potential starting point for a farmland group. We do this because any unvisited 1 must belong to a new rectangle.
2. When we encounter a cell with value 0, we skip it because it represents forest and is irrelevant.
3. When we encounter a cell with value 1, we treat it as the top-left corner of a new rectangle. This is valid because the problem guarantees no two rectangles are adjacent, so no internal cell of a rectangle can be mistaken for a starting point.
4. From this starting point, we compute the full rectangle boundaries. We first extend the column index c2 to the right as long as we see 1s in the same row. This finds the horizontal boundary of the rectangle.
5. Next, we extend the row index r2 downward. For each row, we ensure that all columns from c1 to c2 are still 1. We stop when this condition fails. This gives us the vertical boundary.
6. Once (r2, c2) is identified, we record the rectangle [r1, c1, r2, c2].
7. We then mark all cells within this rectangle as visited (for example, by setting them to 0) to avoid reprocessing.
8. Continue scanning the matrix until all cells have been processed.

Why it works

The correctness relies on the invariant that every farmland group is a contiguous rectangle and that rectangles are disjoint and non-adjacent. Therefore, the first unvisited 1 encountered during iteration must be the top-left corner of a previously unseen rectangle. Expanding from it in both dimensions correctly reconstructs the full group without ambiguity.

Python Solution

from typing import List

class Solution:
    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
        rows = len(land)
        cols = len(land[0])

        result = []

        for row in range(rows):
            for col in range(cols):

                # Check whether this cell is the top-left corner
                # of a farmland group.
                if (
                    land[row][col] == 1
                    and (row == 0 or land[row - 1][col] == 0)
                    and (col == 0 or land[row][col - 1] == 0)
                ):

                    bottom = row
                    right = col

                    # Expand downward
                    while (
                        bottom + 1 < rows
                        and land[bottom + 1][col] == 1
                    ):
                        bottom += 1

                    # Expand rightward
                    while (
                        right + 1 < cols
                        and land[row][right + 1] == 1
                    ):
                        right += 1

                    result.append([row, col, bottom, right])
        if not land or not land[0]:
            return []

        m, n = len(land), len(land[0])
        result = []

        for r in range(m):
            for c in range(n):
                if land[r][c] == 0:
                    continue

                r1, c1 = r, c

                c2 = c1
                while c2 + 1 < n and land[r1][c2 + 1] == 1:
                    c2 += 1

                r2 = r1
                valid = True
                while r2 + 1 < m and valid:
                    for j in range(c1, c2 + 1):
                        if land[r2 + 1][j] == 0:
                            valid = False
                            break
                    if valid:
                        r2 += 1

                for i in range(r1, r2 + 1):
                    for j in range(c1, c2 + 1):
                        land[i][j] = 0

                result.append([r1, c1, r2, c2])

        return result

The implementation begins by determining the matrix dimensions and initializing the result list.

The nested loops scan every cell in the matrix. For each farmland cell, the code checks whether it qualifies as the top left corner of a farmland rectangle. This prevents duplicate processing.

Once a top left corner is found, the code expands downward to determine the rectangle height and expands rightward to determine the rectangle width.

Because the problem guarantees rectangular farmland groups, these two expansions fully determine the rectangle boundaries.

Finally, the rectangle coordinates are appended to the result list and returned after the full scan completes.

Explanation of Python Code

The algorithm scans the grid linearly. When it finds a 1, it expands horizontally to find the right boundary, then vertically to find the bottom boundary by validating that each row maintains the rectangular property. Once the rectangle is identified, all its cells are marked as 0 to avoid revisiting. This ensures each farmland group is processed exactly once.

Go Solution

func findFarmland(land [][]int) [][]int {
	rows := len(land)
	cols := len(land[0])

	result := [][]int{}

	for row := 0; row < rows; row++ {
		for col := 0; col < cols; col++ {

			// Check whether this cell is the top-left corner
			// of a farmland group.
			if land[row][col] == 1 &&
				(row == 0 || land[row-1][col] == 0) &&
				(col == 0 || land[row][col-1] == 0) {

				bottom := row
				right := col

				// Expand downward
				for bottom+1 < rows &&
					land[bottom+1][col] == 1 {
					bottom++
				}

				// Expand rightward
				for right+1 < cols &&
					land[row][right+1] == 1 {
					right++
				}

				result = append(result, []int{
					row,
					col,
					bottom,
					right,
				})
			}
		}
	}

	return result
}

The Go implementation follows exactly the same logic as the Python version.

Slices are used to store the result rectangles. Since Go slices are dynamic, append cleanly handles adding each farmland group.

No special integer overflow handling is required because all coordinates remain within the matrix bounds, which are at most 300 x 300.

The solution also avoids any additional visited matrix, keeping extra space usage constant aside from the output itself. m := len(land) if m == 0 { return [][]int{} } n := len(land[0])

res := make([][]int, 0)

for r := 0; r < m; r++ {
    for c := 0; c < n; c++ {
        if land[r][c] == 0 {
            continue
        }

        r1, c1 := r, c

        c2 := c1
        for c2+1 < n && land[r1][c2+1] == 1 {
            c2++
        }

        r2 := r1
        valid := true
        for valid && r2+1 < m {
            for j := c1; j <= c2; j++ {
                if land[r2+1][j] == 0 {
                    valid = false
                    break
                }
            }
            if valid {
                r2++
            }
        }

        for i := r1; i <= r2; i++ {
            for j := c1; j <= c2; j++ {
                land[i][j] = 0
            }
        }

        res = append(res, []int{r1, c1, r2, c2})
    }
}

return res

}

### Go-Specific Notes

The Go implementation mirrors the Python logic but uses explicit `for` loops instead of `while`. Slices are used for the result, and integer variables are managed explicitly without concerns for overflow since indices remain within matrix bounds. The mutation of `land` is used to track visited cells in place.

## Worked Examples

### Example 1

land = [ [1,0,0], [0,1,1], [0,1,1] ]

### Initial Scan

| Position | Value | Top Left Corner? | Action |
| --- | --- | --- | --- |
| (0,0) | 1 | Yes | Discover rectangle |
| (0,1) | 0 | No | Skip |
| (0,2) | 0 | No | Skip |
| (1,0) | 0 | No | Skip |
| (1,1) | 1 | Yes | Discover rectangle |

### First Rectangle

Starting at `(0,0)`:

#### Expand Downward

`land[1][0] == 0`

So:

bottom = 0

#### Expand Rightward

`land[0][1] == 0`

So:

right = 0

Rectangle:

[0,0,0,0]

### Second Rectangle

Starting at `(1,1)`:

#### Expand Downward

| Row | Value |
| --- | --- |
| 1 | 1 |
| 2 | 1 |

So:

bottom = 2

#### Expand Rightward

| Column | Value |
| --- | --- |
| 1 | 1 |
| 2 | 1 |

So:

right = 2

Rectangle:

[1,1,2,2]

Input:

[[1,0,0], [0,1,1], [0,1,1]]

We scan from `(0,0)`:

- land[0][0] = 1 → new rectangle
- Expand right: only column 0 → c2 = 0
- Expand down: only row 0 → r2 = 0
- Record `[0,0,0,0]`
- Mark visited

Next unvisited 1 at `(1,1)`:

- Expand right: (1,2) is 1 → c2 = 2
- Expand down: row 2 also all ones in columns 1 to 2 → r2 = 2
- Record `[1,1,2,2]`
- Mark visited

Final result:

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

## Example 2

land = [ [1,1], [1,1] ]

### Scan

Cell `(0,0)` is farmland and has no farmland above or left.

This is the top left corner.

### Expand Downward

| Row | Value |
| --- | --- |
| 0 | 1 |
| 1 | 1 |

So:

bottom = 1

### Expand Rightward

| Column | Value |
| --- | --- |
| 0 | 1 |
| 1 | 1 |

So:

right = 1

Rectangle:

[0,0,1,1]

Final result:

[[0,0,1,1]]

## Example 3

land = [[0]]

The only cell is forest land.

No farmland groups exist.

Final result:

[]

### Example 2

Input:

[[1,1], [1,1]]

Start at `(0,0)`:

- Expand right → c2 = 1
- Expand down → r2 = 1
- Rectangle is entire grid
- Output: `[0,0,1,1]`

### Example 3

Input:

[[0]]

- Only cell is `0`
- No rectangles found
- Output: `[]`

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(m × n) | Every cell is processed at most a constant number of times |
| Space | O(1) extra space | No auxiliary data structures are used besides the output |

The matrix scan visits every cell exactly once. The downward and rightward expansions across all rectangles together still remain linear overall because each farmland boundary is traversed only a limited number of times.

The algorithm uses only a few variables in addition to the output list, so the auxiliary space complexity is constant.

## Test Cases

```python
from typing import List

class Solution:
    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
        rows = len(land)
        cols = len(land[0])

        result = []

        for row in range(rows):
            for col in range(cols):

                if (
                    land[row][col] == 1
                    and (row == 0 or land[row - 1][col] == 0)
                    and (col == 0 or land[row][col - 1] == 0)
                ):

                    bottom = row
                    right = col

                    while (
                        bottom + 1 < rows
                        and land[bottom + 1][col] == 1
                    ):
                        bottom += 1

                    while (
                        right + 1 < cols
                        and land[row][right + 1] == 1
                    ):
                        right += 1

                    result.append([row, col, bottom, right])

        return result

solution = Solution()

# Example 1
assert solution.findFarmland([
    [1,0,0],
    [0,1,1],
    [0,1,1]
]) == [[0,0,0,0],[1,1,2,2]]

# Example 2
assert solution.findFarmland([
    [1,1],
    [1,1]
]) == [[0,0,1,1]]

# Example 3, no farmland
assert solution.findFarmland([
    [0]
]) == []

# Single farmland cell
assert solution.findFarmland([
    [1]
]) == [[0,0,0,0]]

# Single row rectangle
assert solution.findFarmland([
    [1,1,1,1]
]) == [[0,0,0,3]]

# Single column rectangle
assert solution.findFarmland([
    [1],
    [1],
    [1]
]) == [[0,0,2,0]]

# Multiple isolated cells
assert solution.findFarmland([
    [1,0,1],
    [0,0,0],
    [1,0,1]
]) == [
    [0,0,0,0],
    [0,2,0,2],
    [2,0,2,0],
    [2,2,2,2]
]

# Large rectangle inside matrix
assert solution.findFarmland([
    [0,0,0,0],
    [0,1,1,1],
    [0,1,1,1],
    [0,1,1,1]
]) == [[1,1,3,3]]

# Thin horizontal rectangles
assert solution.findFarmland([
    [1,1,0,1,1]
]) == [
    [0,0,0,1],
    [0,3,0,4]
]

# Thin vertical rectangles
assert solution.findFarmland([
    [1,0],
    [1,0],
    [0,1],
    [0,1]
]) == [
    [0,0,1,0],
    [2,1,3,1]
]

Test Case Summary

Test	Why
[[1,0,0],[0,1,1],[0,1,1]]	Validates multiple rectangles
[[1,1],[1,1]]	Validates one large rectangle
[[0]]	Validates empty result
[[1]]	Validates single cell farmland
Single row rectangle	Tests horizontal expansion
Single column rectangle	Tests vertical expansion
Multiple isolated cells	Tests many tiny rectangles
Large centered rectangle	Tests internal rectangle detection
Thin horizontal rectangles	Tests separated row groups
Thin vertical rectangles	Tests separated column groups

Edge Cases

Empty Farmland Matrix

A matrix may contain only 0s, meaning no farmland exists anywhere.

This case can cause issues if the implementation assumes every scan eventually finds a rectangle. The algorithm handles this naturally because no cell satisfies the farmland condition, so the result list remains empty.

Single Cell Farmland

A farmland group may consist of only one cell.

This is important because downward and rightward expansion loops should stop immediately without going out of bounds. The implementation correctly leaves both bottom and right equal to the starting coordinates.

Thin Rectangles

A farmland group may occupy only one row or one column.

For example:

[1,1,1,1]

or

[
 [1],
 [1],
 [1]
]

These cases can expose bugs in algorithms that incorrectly assume both dimensions expand simultaneously. The implementation handles them correctly because vertical and horizontal expansion are computed independently.

Multiple Nearby Groups

Several farmland groups may exist close to each other diagonally.

Although groups cannot touch in four directions, diagonal placement is allowed. A careless implementation might accidentally merge them.

Because this solution only expands through direct farmland continuity and identifies rectangles using top left corners, diagonal groups remain separate and are processed independently. | Time | O(mn) | Each cell is visited and marked at most once as part of a rectangle scan | | Space | O(1) extra | No auxiliary structures besides output; grid modified in place |

The algorithm is linear in the number of cells because each cell is consumed exactly once when its rectangle is processed.

Test Cases

assert Solution().findFarmland([[1,0,0],[0,1,1],[0,1,1]]) == [[0,0,0,0],[1,1,2,2]]  # mixed rectangles
assert Solution().findFarmland([[1,1],[1,1]]) == [[0,0,1,1]]  # single large rectangle
assert Solution().findFarmland([[0]]) == []  # no farmland
assert Solution().findFarmland([[1]]) == [[0,0,0,0]]  # single cell rectangle
assert Solution().findFarmland([[1,0],[0,1]]) == [[0,0,0,0],[1,1,1,1]]  # diagonal separation
assert Solution().findFarmland([[1,1,0],[1,1,0],[0,0,1]]) == [[0,0,1,1],[2,2,2,2]]  # two rectangles

Test	Why
mixed rectangles grid	validates multiple disjoint groups
full grid ones	validates single large rectangle
single zero cell	validates empty output
single one cell	validates smallest rectangle
diagonal ones	ensures non-adjacency handling
multiple blocks	checks correctness with multiple components

Edge Cases

One important edge case is a grid containing no 1s at all. In this case, the algorithm never enters the rectangle expansion logic, and the result remains empty. The early skip condition ensures no invalid access occurs.

Another edge case is a grid where every 1 is isolated. Each such cell becomes a 1x1 rectangle. The algorithm handles this naturally because expansion fails immediately in all directions, producing single-cell rectangles correctly.

A third edge case is a large single rectangle filling the entire grid. The algorithm correctly expands from the first cell to the full boundary and marks everything as visited, ensuring no duplicate processing and producing exactly one result.