#1992

Medium

auto_awesomeArray plus Depth-First Search

LeetCode Problem Workspace

Find All Groups of Farmland

Identify all rectangular farmland groups in a binary matrix using array traversal and depth-first search efficiently.

array depth first search breadth first search matrix

Problem Statement

You are given an m x n binary matrix called land, where 0 represents forested land and 1 represents farmland. Farmland is organized into rectangular groups that are not adjacent to other groups in four directions. Each group must be reported as a rectangle.

Find all farmland groups and return a list of arrays representing their top-left and bottom-right coordinates. Each group with top-left corner at (r1, c1) and bottom-right corner at (r2, c2) should be returned as [r1, c1, r2, c2]. The matrix uses 0-indexed coordinates with top-left at (0,0) and bottom-right at (m-1, n-1).

Examples

Example 1

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

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

The first group has a top left corner at land[0][0] and a bottom right corner at land[0][0]. The second group has a top left corner at land[1][1] and a bottom right corner at land[2][2].

Example 2

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

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

The first group has a top left corner at land[0][0] and a bottom right corner at land[1][1].

Example 3

Input: land = [[0]]

Output: []

There are no groups of farmland.

Constraints

m == land.length
n == land[i].length
1 <= m, n <= 300
land consists of only 0's and 1's.
Groups of farmland are rectangular in shape.

Solution Approach

Scan for Top-Left Corners

Iterate through each cell in the matrix. When a 1 is found that has no 1 above or to the left, mark it as a potential top-left corner of a farmland group. This guarantees detection of all distinct rectangles without overlap.

Expand Each Rectangle Using DFS

From each top-left corner, perform depth-first search to find the extent of the rectangle. Track maximal row and column by moving down and right until zeros are reached. This ensures full coverage of each farmland group efficiently.

Record and Return Coordinates

Store each group's coordinates as [topRow, leftCol, bottomRow, rightCol] in a result list. Continue scanning to locate other groups. Finally, return the complete list, ensuring no group is omitted or counted twice.

Complexity Analysis

Metric	Value
Time	O(M \cdot N)
Space	O(1)

Time complexity is O(M * N) since each cell is visited once during scanning and DFS. Space complexity is O(1) if we mark visited cells in-place or O(M * N) if using extra visited storage.

What Interviewers Usually Probe

They may ask how to detect top-left corners efficiently.
Expect discussion of DFS versus BFS for rectangle expansion.
They could probe edge cases like single-cell or full-matrix farmland.

Common Pitfalls or Variants

Common pitfalls

Failing to check for non-adjacent groups can merge separate rectangles.
Using BFS without careful boundary checks may miss edges of rectangles.
Incorrectly updating coordinates can lead to off-by-one errors in output.

Follow-up variants

Return the area of each farmland group instead of coordinates.
Find groups when farmland can be irregular instead of rectangular.
Use BFS exclusively to expand rectangles rather than DFS.

FAQ

What is the best approach to find all groups of farmland in a matrix?

Use array traversal to locate top-left corners and depth-first search to expand each rectangle, recording coordinates as [r1, c1, r2, c2].

Can this problem be solved using BFS instead of DFS?

Yes, BFS can be used to explore each rectangle, but careful boundary checks are required to avoid missing cells.

How do I handle single-cell or empty farmland cases?

Treat each isolated 1 as a valid rectangle with identical top-left and bottom-right coordinates. If no 1 exists, return an empty list.

What are the common mistakes when implementing this pattern?

Merging adjacent rectangles, off-by-one errors in coordinates, and failing to mark cells as visited are common pitfalls.

Why is this considered an array plus depth-first search pattern?

Because the solution relies on scanning the array for starting points and using DFS to expand each group efficiently.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
        m, n = len(land), len(land[0])
        ans = []
        for i in range(m):
            for j in range(n):
                if (
                    land[i][j] == 0
                    or (j > 0 and land[i][j - 1] == 1)
                    or (i > 0 and land[i - 1][j] == 1)
                ):
                    continue
                x, y = i, j
                while x + 1 < m and land[x + 1][j] == 1:
                    x += 1
                while y + 1 < n and land[x][y + 1] == 1:
                    y += 1
                ans.append([i, j, x, y])
        return ans

Continue Practicing

#1970 last day where you can still cross #1905 count sub islands #2328 number of increasing paths in a grid