Problem Statement
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 = [[0,0,0,0,0],[0,1,1,1,0],[0,1,1,1,0],[0,0,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
Output: [[1,1,2,3],[4,3,5,4]]
Explanation:
The first group has a top left corner at land[1][1] and a bottom right corner at land[2][3].
The second group has a top left corner at land[4][3] and a bottom right corner at land[5][4].
Try here before watching the video.
Video Solution
Code Approach 1 - DFS
Java Code
class Solution {
int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int row2, col2;
private void dfs(int[][] land, int x, int y) {
if(x < 0 || y < 0 || x >= land.length || y >= land[0].length || land[x][y] != 1) {
return;
}
land[x][y] = 0;
row2 = Math.max(row2, x);
col2 = Math.max(col2, y);
for (int[] direction : directions) {
int newX = x + direction[0], newY = y + direction[1];
dfs(land, newX, newY);
}
}
public int[][] findFarmland(int[][] land) {
List<int[]> ans = new ArrayList<>();
for (int row1 = 0; row1 < land.length; row1++) {
for (int col1 = 0; col1 < land[0].length; col1++) {
if (land[row1][col1] == 1) {
row2 = 0; col2 = 0;
dfs(land, row1, col1);
int[] arr = new int[] {row1, col1, row2, col2};
ans.add(arr);
}
}
}
return ans.stream().toArray(int[][] :: new);
}
}
C++ Code
#include <vector>
using namespace std;
class Solution {
private:
vector<vector<int>> directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int row2, col2;
void dfs(vector<vector<int>>& land, int x, int y) {
if(x < 0 || y < 0 || x >= land.size() || y >= land[0].size() || land[x][y] != 1) {
return;
}
land[x][y] = 0;
row2 = max(row2, x);
col2 = max(col2, y);
for (auto direction : directions) {
int newX = x + direction[0], newY = y + direction[1];
dfs(land, newX, newY);
}
}
public:
vector<vector<int>> findFarmland(vector<vector<int>>& land) {
vector<vector<int>> ans;
for (int row1 = 0; row1 < land.size(); row1++) {
for (int col1 = 0; col1 < land[0].size(); col1++) {
if (land[row1][col1] == 1) {
row2 = 0; col2 = 0;
dfs(land, row1, col1);
ans.push_back({row1, col1, row2, col2});
}
}
}
return ans;
}
};
Python Code
from typing import List
class Solution:
def __init__(self):
self.directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]
self.row2 = 0
self.col2 = 0
def dfs(self, land, x, y):
if x < 0 or y < 0 or x >= len(land) or y >= len(land[0]) or land[x][y] != 1:
return
land[x][y] = 0
self.row2 = max(self.row2, x)
self.col2 = max(self.col2, y)
for direction in self.directions:
newX = x + direction[0]
newY = y + direction[1]
self.dfs(land, newX, newY)
def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
ans = []
for row1 in range(len(land)):
for col1 in range(len(land[0])):
if land[row1][col1] == 1:
self.row2 = 0
self.col2 = 0
self.dfs(land, row1, col1)
ans.append([row1, col1, self.row2, self.col2])
return ans
Complexity Analysis
Time Complexity: O(M * N)
Space Complexity: O(M * N)
Code Approach 2 - Greedy
Java Code
class Solution {
public int[][] findFarmland(int[][] land) {
int M = land.length;
int N = land[0].length;
List<int[]> answer = new ArrayList<>();
for(int i = 0; i < M; i++) {
for(int j = 0; j < N; j++) {
if(land[i][j] == 1) {
int x = i, y = j;
for(x = i; x < M && land[x][j] == 1; x++) {
for(y = j; y < N && land[x][y] == 1; y++) {
land[x][y] = 0;
}
}
int arr[] = new int[]{i, j, x - 1, y - 1};
answer.add(arr);
}
}
}
return answer.stream().toArray(int[][] :: new);
}
}
C++ Code
class Solution {
public:
vector<vector<int>> findFarmland(vector<vector<int>>& land) {
int M = land.size();
int N = land[0].size();
vector<vector<int>> answer;
for(int i = 0; i < M; i++) {
for(int j = 0; j < N; j++) {
if(land[i][j] == 1) {
int x = i, y = j;
for(x = i; x < M && land[x][j] == 1; x++) {
for(y = j; y < N && land[x][y] == 1; y++) {
land[x][y] = 0;
}
}
answer.push_back({i, j, x - 1, y - 1});
}
}
}
return answer;
}
};
Complexity Analysis
Time Complexity: O(M * N)
Space Complexity: O(1)