{x}
blog image

Find All Groups of Farmland

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.

 

Example 1:

Input: land = [[1,0,0],[0,1,1],[0,1,1]]
Output: [[0,0,0,0],[1,1,2,2]]
Explanation:
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]]
Explanation:
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: []
Explanation:
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 Explanation

This problem asks to find all groups of farmland in a given binary matrix land. A group of farmland is a rectangular area consisting entirely of 1s (farmland). The solution efficiently identifies these rectangular groups without redundant checks.

Approach

The core idea is to iterate through the matrix and identify the top-left corner of each farmland group. Once a top-left corner is found, we expand to find the bottom-right corner by iterating downwards and rightwards until we encounter a 0 or the edge of the matrix. This avoids unnecessary checks within already explored groups.

  1. Iteration: The code iterates through the matrix using nested loops.

  2. Top-Left Corner Identification: A cell (i, j) is considered a potential top-left corner if:

    • It's a farmland (value 1).
    • It's not to the right or below another farmland (preventing revisits). This check is done using (j > 0 and land[i][j - 1] == 1) and (i > 0 and land[i - 1][j] == 1).

  3. Bottom-Right Corner Expansion: Once a top-left corner is found, two loops expand to find the bottom-right corner:

    • The first loop expands downwards (x direction) as long as the cell below is a farmland.
    • The second loop expands rightwards (y direction), starting from the updated x (bottom row of the group) as long as the cell to the right is a farmland.

  4. Result: The coordinates of the top-left (i, j) and bottom-right (x, y) corners are added to the result list.

Time and Space Complexity Analysis

  • Time Complexity: O(mn), where 'm' and 'n' are the dimensions of the matrix. The code iterates through each cell of the matrix once in the worst case. The expansion to find the bottom-right corner is done only for the top-left corners of each group, which is proportional to the number of groups (at most mn).

  • Space Complexity: O(k), where 'k' is the number of groups of farmland found. The space used is primarily for storing the result, which is a list of groups (each group being a 4-element array). In the worst-case scenario where every cell is part of a different group, k could be up to m*n. However, in practice, the number of groups is usually much smaller.

Code Examples (with detailed comments)

The code examples in Python3, Java, C++, and Go presented earlier are all highly optimized and closely follow the approach described above. The comments within those code examples explain each step in greater detail.

This detailed explanation provides a comprehensive understanding of the algorithm, its implementation, and its performance characteristics.