1992. Find All Groups of Farmland LeetCode Solution
In this guide, you will get 1992. Find All Groups of Farmland LeetCode Solution with the best time and space complexity. The solution to Find All Groups of Farmland problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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.
Complexity Analysis
Time Complexity: O(mn)
Space Complexity: O(mn)
1992. Find All Groups of Farmland LeetCode Solution in C++
class Solution {
public:
vector<vector<int>> findFarmland(vector<vector<int>>& land) {
vector<vector<int>> ans;
for (int i = 0; i < land.size(); ++i)
for (int j = 0; j < land[0].size(); ++j)
if (land[i][j] == 1) {
int x = i;
int y = j;
dfs(land, i, j, x, y);
ans.push_back({i, j, x, y});
}
return ans;
}
private:
void dfs(vector<vector<int>>& land, int i, int j, int& x, int& y) {
if (i < 0 || i == land.size() || j < 0 || j == land[0].size())
return;
if (land[i][j] != 1)
return;
land[i][j] = 2; // Mark as visited.
x = max(x, i);
y = max(y, j);
dfs(land, i + 1, j, x, y);
dfs(land, i, j + 1, x, y);
}
}; /* code provided by PROGIEZ */
1992. Find All Groups of Farmland LeetCode Solution in Java
class Solution {
public int[][] findFarmland(int[][] land) {
List<int[]> ans = new ArrayList<>();
for (int i = 0; i < land.length; ++i)
for (int j = 0; j < land[0].length; ++j)
if (land[i][j] == 1) {
int[] cell = new int[] {i, j};
dfs(land, i, j, cell);
ans.add(new int[] {i, j, cell[0], cell[1]});
}
return ans.stream().toArray(int[][] ::new);
}
private void dfs(int[][] land, int i, int j, int[] cell) {
if (i < 0 || i == land.length || j < 0 || j == land[0].length)
return;
if (land[i][j] != 1)
return;
land[i][j] = 2; // Mark as visited.
cell[0] = Math.max(cell[0], i);
cell[1] = Math.max(cell[1], j);
dfs(land, i + 1, j, cell);
dfs(land, i, j + 1, cell);
}
} // code provided by PROGIEZ
1992. Find All Groups of Farmland LeetCode Solution in Python
class Solution:
def findFarmland(self, land: list[list[int]]) -> list[list[int]]:
ans = []
def dfs(i: int, j: int, cell: list[int]) -> None:
if i < 0 or i == len(land) or j < 0 or j == len(land[0]):
return
if land[i][j] != 1:
return
land[i][j] = 2 # Mark as visited.
cell[0] = max(cell[0], i)
cell[1] = max(cell[1], j)
dfs(i + 1, j, cell)
dfs(i, j + 1, cell)
for i in range(len(land)):
for j in range(len(land[0])):
if land[i][j] == 1:
cell = [i, j]
dfs(i, j, cell)
ans.append([i, j, *cell])
return ans # code by PROGIEZ
