1992. Find All Groups of Farmland

MediumDepth-First SearchBreadth-First SearchArrayMatrix
Leetcode Link

Problem Description

In this LeetCode problem, we are working with a 2D grid representing a piece of land, where each cell in this grid can either be forested land (denoted by 0s) or farmland (denoted by 1s). The grid is 0-indexed, meaning that the rows and columns are numbered starting from 0. Groups of farmland are rectangles within the grid that are composed entirely of 1s. No two groups are adjacent to each other, which means the sides of the rectangles of farmland don’t touch each other horizontally or vertically.

We are tasked with finding the coordinates of the top-left and bottom-right corners of each group of farmland. The coordinates of a corner are represented as ((r, c)), where (r) and (c) are the row and column indexes of the cell within the grid. The result is expected to be a list of 4-item lists, each containing the coordinates of the top-left and bottom-right corners of a group, denoted as ([r1, c1, r2, c2]).

To summarize, we need to scan the grid, identify the separate rectangular farmland groups, record the coordinates of their top-left and bottom-right corners, and return this information in a 2D list.

Intuition

The intuition behind the solution is based on finding the starting point (the top-left corner) for each group of farmland. We can iterate through the grid cell by cell. When we find a cell with a value of 1 that hasn't been identified as part of a group yet (which means it's neither directly below nor to the right of another farmland cell), we consider it as the top-left corner of a new group.

Once we have identified a top-left corner, we need to find the corresponding bottom-right corner for the group. We do this by scanning downwards from the top-left corner until we reach a row where the farmland ends (the next cell is 0 or we’ve reached the grid boundary). The same approach is used horizontally from the top-left corner to find the end of the farmland in that particular row. The last cell before the farmland ends in both directions will be the bottom-right corner.

The key steps for the algorithm are as follows:

  1. Traverse all cells in the grid row by row and column by column.
  2. Skip the inspection for a cell if:
    • It is forested land (a 0).
    • It is immediately to the right of another farmland cell (as this would be within the same farmland group).
    • It is directly below another farmland cell (also indicating the same group).
  3. Upon finding the starting point of a new group (farmland cell that does not meet the above conditions), mark it and then expand downwards and rightwards to find the bottom right corner.
  4. Once the bottom right corner is identified, append the coordinates to the results list.
  5. After finishing the traversal, return the list of corner coordinates for each group.

Learn more about Depth-First Search and Breadth-First Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which data structure is used to implement priority queue?

Solution Approach

The implementation of the solution uses a straightforward approach to process the land matrix and identify the farmland groups without additional data structures for storing intermediate states. The algorithm relies heavily on the properties of the matrix and the characteristics of the groups.

Here is a step-by-step explanation of the algorithm, referencing the solution code provided:

  1. Initialize a list ans to store the answer.

  2. Start two nested loops to iterate over each cell in the matrix:

    • The outer loop goes through each row i.
    • The inner loop goes through each column j.

  3. Within the inner loop, for each cell check if the cell can be the top-left corner of a new group:

    • Check if the cell is a forested area (land[i][j] == 0); if true, continue to the next iteration.
    • Check if the cell is immediately to the right (j > 0 and land[i][j - 1] == 1) or below (i > 0 and land[i - 1][j] == 1) another farmland cell; if true, this means the cell is part of an existing group, so continue to the next iteration.

  4. If the current cell (land[i][j]) is indeed the top-left corner of a new group, find the corresponding bottom-right corner:

    • Initialize variables x and y with the current coordinates (i, j).
    • Expand downwards from the top-left corner along the column j until reaching a cell where the next cell below is 0 or the boundary of the matrix is reached. Update the x to the row index of the last farmland cell in this column.
    • Expand rightwards from the top-left corner along the row i until reaching a cell where the next cell to the right is 0 or the boundary of the matrix is reached. Update the y to the column index of the last farmland cell in this row.

  5. Append the coordinates i, j, x, y to the ans list. These coordinates represent the top-left (i, j) and bottom-right (x, y) corners of the new farmland group.

  6. After processing all cells, return the ans list containing the 4-length arrays which provide the coordinates for each group of farmland.

The implementation does not require additional data structures and works efficiently due to the constraints put in place, such as non-adjacency of the farmland groups and the binary nature of the land matrix. As the algorithm processes each cell at most twice, once in the overall iteration and once during the expansion to find the bottom-right corner, the time complexity of the algorithm is O(m*n), where m and n are the dimensions of the land matrix. The space complexity is O(1), not counting the input and output, since no extra space is used beyond variables for iteration and expansion.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How many times is a tree node visited in a depth first search?

Example Walkthrough

Let's walk through an example to illustrate the solution approach. Consider a small 2D grid, representing land as follows:

1[
2 [1, 0, 0, 1, 1],
3 [1, 1, 0, 1, 1],
4 [0, 0, 0, 0, 0],
5 [1, 1, 1, 0, 0],
6]

In this grid:

  • 1 represents a farmland cell,
  • 0 represents a forested area.

We want to find the coordinates of the top-left and bottom-right corners of each group of farmland.

Following the steps of the algorithm:

  1. Initialize an empty list ans to store the coordinates of farmland groups.

  2. Starting from the top-left corner of the grid, go row by row and column by column. We initiate an outer loop for rows and an inner loop for columns.

  3. When we reach the first 1 at position (0, 0), we check:

    • It's not forested land.
    • It's not directly to the right or below another farmland cell. Hence, it could be a top-left corner.

  4. From (0, 0), move downwards in the same column until we reach a 0. The last farmland cell is (1, 0), so x = 1.

  5. From (0, 0), move rightwards in the same row until we reach a farmland cell followed by a 0. The last farmland cell is (0, 0), so y = 0.

  6. Append [0, 0, 1, 0] to the ans list, representing the top-left (0, 0) and bottom-right (1, 0) coordinates of this group.

  7. Continue to (0, 3), which again could be a top-left corner. Repeat the expansion process to find the bottom-right corner at (1, 4). Append [0, 3, 1, 4] to the ans.

  8. Skip cells in the middle of groups like (0, 1), (0, 4), (1, 1), and so on.

  9. Finally, the cell (3, 0) is identified as the top-left of the third group, and (3, 2) as its bottom-right corner. Append [3, 0, 3, 2].

  10. Once all cells have been processed, we have ans = [[0, 0, 1, 0], [0, 3, 1, 4], [3, 0, 3, 2]].

The resulting ans list provides the coordinates for each group of farmland in the grid as required.

Solution Implementation

1from typing import List
2
3class Solution:
4    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
5        # Get the dimensions of the input grid.
6        num_rows, num_columns = len(land), len(land[0])
7      
8        # Initialize an output list to store the coordinates of each farmland.
9        farmlands = []
10      
11        # Iterate over each cell in the grid.
12        for row in range(num_rows):
13            for col in range(num_columns):
14                # Skip the cell if it is not part of a farmland, or if it is not the top-left cell 
15                # of a farmland (if it's a continuation of a row or column of a previous farmland).
16                if (land[row][col] == 0 or
17                   (col > 0 and land[row][col - 1] == 1) or
18                   (row > 0 and land[row - 1][col] == 1)):
19                    continue
20
21                # Initialize farmland boundaries with the current cell.
22                farmland_end_row, farmland_end_col = row, col
23
24                # Expand vertically downwards to find the bottom boundary of the farmland.
25                while farmland_end_row + 1 < num_rows and land[farmland_end_row + 1][col] == 1:
26                    farmland_end_row += 1
27
28                # Expand horizontally rightwards to find the right boundary of the farmland.
29                while farmland_end_col + 1 < num_columns and land[farmland_end_row][farmland_end_col + 1] == 1:
30                    farmland_end_col += 1
31
32                # Add the found farmland coordinates to the list.
33                # It includes the top-left and bottom-right coordinates of the rectangle.
34                farmlands.append([row, col, farmland_end_row, farmland_end_col])
35              
36                # Mark the found farmland on the map to not count it again
37                for i in range(row, farmland_end_row + 1):
38                    for j in range(col, farmland_end_col + 1):
39                        land[i][j] = 0
40                      
41        # Return the list of coordinates for all farmlands found.
42        return farmlands
43
1class Solution {
2  
3    // Method to find farmland blocks in a given grid of land.
4    public int[][] findFarmland(int[][] land) {
5        // Initialize a list to store the results.
6        List<int[]> farmlandList = new ArrayList<>();
7      
8        // Get the number of rows and columns in the land grid.
9        int rowCount = land.length;
10        int colCount = land[0].length;
11      
12        // Iterate over each cell in the grid.
13        for (int row = 0; row < rowCount; ++row) {
14            for (int col = 0; col < colCount; ++col) {
15              
16                // Skip the current cell if it is not land (0), or it's not the top-left corner of a farmland block.
17                if (land[row][col] == 0 || (col > 0 && land[row][col - 1] == 1) || (row > 0 && land[row - 1][col] == 1)) {
18                    continue;
19                }
20              
21                // Initialize variables for the bottom-right corner of the farmland block.
22                int bottomRow = row;
23                int rightCol = col;
24              
25                // Extend the farmland block towards the bottom (row-wise).
26                while (bottomRow + 1 < rowCount && land[bottomRow + 1][col] == 1) {
27                    ++bottomRow;
28                }
29              
30                // Extend the farmland block towards the right (column-wise).
31                while (rightCol + 1 < colCount && land[bottomRow][rightCol + 1] == 1) {
32                    ++rightCol;
33                }
34              
35                // Add the top-left and bottom-right corner coordinates of the farmland block to the result list.
36                farmlandList.add(new int[] {row, col, bottomRow, rightCol});
37            }
38        }
39      
40        // Convert the list of farmland blocks to an array and return the array.
41        return farmlandList.toArray(new int[farmlandList.size()][4]);
42    }
43}
44
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6    vector<vector<int>> findFarmland(vector<vector<int>>& land) {
7        vector<vector<int>> farmlands; // Variable to store the list of farmlands found
8        int rows = land.size(); // Number of rows in the input matrix
9        int cols = land[0].size(); // Number of columns in the input matrix
10
11        // Loop through each cell in the matrix
12        for (int i = 0; i < rows; ++i) {
13            for (int j = 0; j < cols; ++j) {
14                // Skip the cell if it is not part of farmland, or if it is already part of an identified farmland
15                if (land[i][j] == 0 || (j > 0 && land[i][j - 1] == 1) || (i > 0 && land[i - 1][j] == 1)) {
16                    continue;
17                }
18
19                // Initialize the top-left corner of the current farmland
20                int topLeftX = i;
21                int topLeftY = j;
22                int bottomRightX = i;
23                int bottomRightY = j;
24              
25                // Expand in the downward direction (increment rows)
26                while (bottomRightX + 1 < rows && land[bottomRightX + 1][j] == 1) {
27                    bottomRightX++;
28                }
29              
30                // Expand in the rightward direction (increment columns)
31                while (bottomRightY + 1 < cols && land[bottomRightX][bottomRightY + 1] == 1) {
32                    bottomRightY++;
33                }
34              
35                // Store the coordinates of the current farmland
36                farmlands.push_back({topLeftX, topLeftY, bottomRightX, bottomRightY});
37            }
38        }
39        // Return the list of farmlands identified in the matrix
40        return farmlands;
41    }
42};
43
1// Type alias for better readability, denotes the matrix of land plots
2type LandMatrix = number[][];
3
4// Defines the signature of a rectangle representing a farmland plot with its top-left and bottom-right coordinates
5type FarmLand = [number, number, number, number];
6
7/**
8 * Finds all rectangular farmlands within a given land matrix.
9 * A farmland is a contiguous rectangular block of land marked with 1s.
10 * 
11 * @param land - A matrix of numbers representing plots, where 1 is a farmland plot and 0 is not part of a farmland.
12 * @returns farmlands - An array of rectangles representing distinct farmlands.
13 */
14function findFarmland(land: LandMatrix): FarmLand[] {
15  const farmlands: FarmLand[] = []; // Variable to store the list of farmlands found
16  const rows: number = land.length; // Number of rows in the input matrix
17  const cols: number = land[0].length; // Number of columns in the input matrix
18
19  // Loop through each cell in the matrix
20  for (let i = 0; i < rows; ++i) {
21    for (let j = 0; j < cols; ++j) {
22      // Skip the cell if it:
23      // is not part of farmland (0),
24      // or if it is to the right of a farmland plot in the same row (already part of an identified farmland),
25      // or if it is below a farmland plot in the same column (already part of an identified farmland)
26      if (land[i][j] === 0 || (j > 0 && land[i][j - 1] === 1) || (i > 0 && land[i - 1][j] === 1)) {
27        continue;
28      }
29
30      // Initialize the top-left corner of the current farmland with the coordinates (i, j)
31      let topLeftX: number = i;
32      let topLeftY: number = j;
33      let bottomRightX: number = i;
34      let bottomRightY: number = j;
35
36      // Expand in the downward direction (increment rows)
37      while (bottomRightX + 1 < rows && land[bottomRightX + 1][j] === 1) {
38        bottomRightX++;
39      }
40
41      // Expand in the rightward direction (increment columns)
42      while (bottomRightY + 1 < cols && land[i][bottomRightY + 1] === 1) {
43        bottomRightY++;
44      }
45
46      // Store the coordinates of the current farmland as a tuple [topLeftX, topLeftY, bottomRightX, bottomRightY]
47      farmlands.push([topLeftX, topLeftY, bottomRightX, bottomRightY]);
48
49      // Mark the identified farmland in the matrix to ensure it is not processed again
50      for (let x = topLeftX; x <= bottomRightX; x++) {
51        for (let y = topLeftY; y <= bottomRightY; y++) {
52          land[x][y] = 0;
53        }
54      }
55    }
56  }
57  // Return the list of farmlands identified in the matrix
58  return farmlands;
59}
60
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is a good use case for backtracking?

Time and Space Complexity

The time complexity of the provided code is O(m * n) where m is the number of rows and n is the number of columns in the grid. This is because in the worst-case scenario, you have to visit each cell once to check if it's the start of a new farmland and then possibly extend the search downwards and to the right to find the extent of that farmland. However, since an extension in one direction for one farm doesn't check cells belonging to another potential farm, each cell is visited at most twice (once in the main iteration and once when expanding downwards or rightwards).

The space complexity of the code is O(1) if we don't count the output space. The algorithm creates only a few variables to keep track of the current rectangle (farmland) being discovered (x, y, i, j). It does not use any additional data structure that grows with the input size. The ans list is the output and typically isn't counted in space complexity calculations. However, in the context where the space used by the output is taken into consideration, the space complexity would be O(f) where f is the number of farmlands discovered, since this is the size of the ans list that is being returned.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Recommended Readings

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫