1992. Find All Groups of Farmland
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.
Flowchart Walkthrough
Let's analyze Leetcode problem 1992. Find All Groups of Farmland by using the Flowchart. Here's the step-by-step analysis to determine the algorithm to use:
Is it a graph?
- Yes: The grid can be viewed as a graph where each cell is a node, and adjacent land cells (1s) are connected by edges.
Is it a tree?
- No: This graph isn't necessarily a tree as it can contain multiple separate areas of farmland, each representing a different graph component without having a single root node or hierarchy.
Is the problem related to directed acyclic graphs (DAGs)?
- No: The problem focuses on contiguous blocks of farmland, not on directionality or dependencies which characterize DAGs.
Is the problem related to shortest paths?
- No: The main requirement is to identify distinct groups of connected cells (farmlands), not to find a shortest path between nodes.
Does the problem involve connectivity?
- Yes: The solution requires identifying all connected components where each component represents a contiguous farmland.
Since we identify "Yes" to connectivity and it involves non-weighted connections (as thereās no cost or weight difference in moving between adjacent land cells):
Is the graph weighted?
- No: Each connection between adjacent land (1s) cells is uniform, meaning the grid can be treated as unweighted.
Given that the graph is non-weighted and involves solving for connectivity, one effective classic approach, according to our flowchart, should involve Depth-First Search (DFS) to explore and mark all cells connected from a starting land cell, thereby finding all groups of connected farmland.
Conclusion: The flowchart guides using a DFS approach for this unweighted, connectivity-based problem in order to effectively find all groups of farmland.
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:
- Traverse all cells in the grid row by row and column by column.
- 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).
- 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.
- Once the bottom right corner is identified, append the coordinates to the results list.
- After finishing the traversal, return the list of corner coordinates for each group.
Learn more about Depth-First Search and Breadth-First Search patterns.
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:
-
Initialize a list
ans
to store the answer. -
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
.
- The outer loop goes through each row
-
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.
- Check if the cell is a forested area (
-
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
andy
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 thex
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 they
to the column index of the last farmland cell in this row.
- Initialize variables
-
Append the coordinates
i, j, x, y
to theans
list. These coordinates represent the top-left (i, j
) and bottom-right (x, y
) corners of the new farmland group. -
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through an example to illustrate the solution approach. Consider a small 2D grid, representing land as follows:
[ [1, 0, 0, 1, 1], [1, 1, 0, 1, 1], [0, 0, 0, 0, 0], [1, 1, 1, 0, 0], ]
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:
-
Initialize an empty list
ans
to store the coordinates of farmland groups. -
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.
-
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.
-
From
(0, 0)
, move downwards in the same column until we reach a0
. The last farmland cell is(1, 0)
, sox = 1
. -
From
(0, 0)
, move rightwards in the same row until we reach a farmland cell followed by a0
. The last farmland cell is(0, 0)
, soy = 0
. -
Append
[0, 0, 1, 0]
to theans
list, representing the top-left(0, 0)
and bottom-right(1, 0)
coordinates of this group. -
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 theans
. -
Skip cells in the middle of groups like
(0, 1)
,(0, 4)
,(1, 1)
, and so on. -
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]
. -
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
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.
Which of the following array represent a max heap?
Recommended Readings
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
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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!