Find All Groups of Farmland

Updated on 29 May, 2025
Find All Groups of Farmland header image

Problem Statement

In this task, you are given a binary matrix land where the matrix dimensions are m x n. Within this matrix:

  • A value of 0 indicates forested land.
  • A value of 1 indicates farmland.

The matrix is organized into distinct rectangular regions, or groups, that contain only farmland (1s). Each group of farmland is entirely surrounded by forested land (0s), or by the boundaries of the matrix - no group is directly adjacent to another.

The key objective is to identify these groups and determine two sets of coordinates for each:

  • The top-left corner of the group.
  • The bottom-right corner of the group.

These coordinates for each group are then to be returned as pairs within an array, where each group is represented by a 4-length array of the form [r1, c1, r2, c2]. An empty array should be returned if no such groups exist.

Examples

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.

Approach and Intuition

Given the binary nature of the matrix and the problem's constraints, we'll approach it as a variant of the common "connected components in a graph" problem. The "farmland" (1s) areas can be viewed as nodes in a grid graph, where contiguous patches need to be identified as separate components.

  1. Traversing the Matrix:

    • We iterate through each cell of the matrix. If we encounter a 1, we check if it has not already been considered part of another group.
  2. Group Detection using DFS/BFS:

    • Starting from the initial 1 encountered, we can use a Depth-First Search (DFS) or Breadth-First Search (BFS) to explore all directly connected 1s (i.e., those that are horizontally or vertically adjacent, but not diagonally).
    • Keep track of the smallest and largest row and column indices reached during this exploration, as these will correspond to the top-left and bottom-right corners of the current farmland group.
  3. Storage and Output:

    • After identifying a complete group, store its bounding coordinates [r1, c1, r2, c2] in the output array.
    • Reset and continue the matrix traversal, skipping over any cells that have already been included in a group.

The DFS/BFS ensures that each cell is visited no more than once, leading to a linear time complexity relative to the number of cells, i.e., (O(m \times n)), where (m) and (n) are the matrix dimensions. This approach efficiently handles the upper constraint limits given.

Solutions

  • C++
  • Java
  • Python
cpp
class Solution {
public:
    vector<vector<int>> detectFarmland(vector<vector<int>>& landMatrix) {
        int rows = landMatrix.size(), cols = landMatrix[0].size();
        vector<vector<int>> farmlands;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (landMatrix[i][j] == 1) {
                    int endRow = i, endCol = j;
                    
                    while (endRow < rows && landMatrix[endRow][j] == 1) {
                        while (endCol < cols && landMatrix[endRow][endCol] == 1) {
                            landMatrix[endRow][endCol] = 0;
                            endCol++;
                        }
                        endRow++;
                        endCol = j;
                    }

                    farmlands.push_back({i, j, endRow - 1, endCol - 1});
                }
            }
        }
        
        return farmlands;
    }
};

The provided C++ solution describes an approach to find all contiguous rectangular groups of farmland within a given 2D grid, where each cell contains either a 1 (representing farmland) or a 0 (representing non-farmland). The solution utilizes a vector<vector<int>> to represent the output list of farmland rectangles, which are characterized by their top-left and bottom-right corner coordinates.

Upon initiating the detectFarmland function, the following steps are taken:

  • Initialize the rows and columns based on the input grid's dimensions.

  • Define a vector<vector<int>> farmlands to gather the coordinates of each detected rectangular farmland area.

  • Iterate through each cell in the grid using nested loops:

    • If the cell at position (i, j) is a farm cell (landMatrix[i][j] == 1), initialize endRow and endCol to the starting coordinates (i, j).
    • Expand in both the horizontal (columns) and vertical (rows) directions to determine the full extent of the rectangle:
      • Continue expanding endCol while cells in the same row and increasing columns contain a 1, setting cells to 0 as they are absorbed into a rectangle to avoid recounting.
      • After expanding horizontally for a given row, increment endRow and reset endCol to start from the initial j column. Repeat until reaching a row where cells directly below the current endRow are no longer farmland.
    • After determining the extent of the rectangle, store its coordinates [top-left (i, j) and bottom-right (endRow - 1, endCol - 1)] in the farmlands list.
  • Return the completed list of farmland rectangles farmlands.

This approach ensures that each part of the farmland is only visited and counted once, heavily relying on updating the matrix in-place to mark cells that are already included in a farmland group. The end result is an efficient categorization of all farmland areas, allowing for easy identification of their boundaries within the 2D grid.

java
class FarmFinder {
    public int[][] identifyFarms(int[][] field) {
        int rows = field.length, cols = field[0].length;
        List<int[]> results = new ArrayList<>();

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (field[i][j] == 1) {
                    int endRow = i, endCol = j;

                    for (endRow = i; endRow < rows && field[endRow][j] == 1; endRow++) {
                        for (endCol = j; endCol < cols && field[endRow][endCol] == 1; endCol++) {
                            field[endRow][endCol] = 0;
                        }
                    }

                    int[] coordinate = new int[] {i, j, endRow - 1, endCol - 1};
                    results.add(coordinate);
                }
            }
        }
        return results.toArray(new int[results.size()][]);
    }
}

The provided Java program defines a class FarmFinder with a method identifyFarms, which aims to locate continuous groups of farmland on a grid. The grid is represented by a 2D integer array where '1' indicates farmland and '0' denotes an empty plot. The goal is to find all rectangles of continuous farmland and return their coordinates, where each rectangle is defined by top-left and bottom-right corners.

Here's how the method identifyFarms performs this task:

  • Initialize rows and cols to store the dimensions of the input grid (field).
  • Create a list results to keep track of identified farmland coordinates.
  • Loop through each cell of the grid using nested loops.
  • When a cell with value '1' is found:
    • Initialize endRow and endCol at the current indices (i and j).
    • Use nested loops to expand downwards and rightwards to find the boundaries of the farmland block. During this expansion, mark each traversed '1' as '0' to avoid recounting the same cells.
    • After finding the extent of the block, save the coordinates [i, j, endRow - 1, endCol - 1] where i and j are the starting row and column, and endRow - 1 and endCol - 1 represent the ending row and column of the block.
    • Append these coordinates to results.
  • Convert the results list to an array of arrays and return it, providing the list of all found farmland groups as output.

In summary, this method effectively finds and marks each group of connected '1's in the given grid and records their boundaries, making it efficient to determine all distinct groups of farmland.

python
class Solution:
    def locateFarmingArea(self, grid: List[List[int]]) -> List[List[int]]:
        rows, cols = len(grid), len(grid[0])
        farm_areas = []
        
        for i in range(rows):
            for j in range(cols):
                if grid[i][j]:
                    endRow, endCol = i, j
                    
                    while endRow < rows and grid[endRow][j]:
                        endCol = j
                        while endCol < cols and grid[endRow][endCol]:
                            grid[endRow][endCol] = 0
                            endCol += 1
                        endRow += 1
                    
                    farm_areas.append([i, j, endRow - 1, endCol - 1])
        
        return farm_areas

The provided Python solution finds all the contiguous groups of land marked as '1' in a given 2D grid, which represents farmland areas. Below is the step-by-step explanation of the approach used:

  1. Initialize rows and cols to store the dimensions of the input grid.

  2. Create an empty list farm_areas to store the coordinates of each farmland area found.

  3. Iterate through each cell in the grid using a nested loop.

  4. For each cell that contains '1', mark it as the starting point of a new farmland area.

  5. Use two nested while loops to explore the extent of the farmland area horizontally and vertically:

    • Mark visited parts of the farm as '0' to avoid revisiting them.
    • Expand horizontally until a '0' is encountered or the end of the column is reached.
    • Expand vertically until a '0' is encountered or the end of the row is reached.
  6. Once the full extent of the farmland is determined, append the top-left and bottom-right coordinates of the farmland area to farm_areas.

  7. Return the list farm_areas which contains the boundaries for all farmland groups found in the grid.

This method effectively identifies and records each contiguous block of farmland using a modified depth-first search that marks parts of the farm as processed by setting them to '0', preventing redundant processing and capturing the correct dimensions of each farmland area.

Comments

No comments yet.