Sponsored
Sponsored
This approach uses a Breadth-First Search (BFS) algorithm to explore each group of farmland on the matrix.
Starting from a farmland cell (1), the BFS can be used to explore all connected cells that belong to the same group, thereby finding the bottom-right corner of that group. Use a queue to facilitate the exploration of individual farmlands.
Mark cells as visited as you explore them to ensure each cell is processed only once.
Time Complexity: O(m * n), as each cell is visited at most once.
Space Complexity: O(m * n) in the worst case due to additional space used for storing visited cells and the queue.
1from collections import deque
2
3def findFarmland(land):
4 m, n = len(land), len(land[0])
5 visited = [[False] * n for _ in range(m)]
6 results = []
7
8 for i in range(m):
9 for j in range(n):
10 if land[i][j] == 1 and not visited[i][j]:
11 queue = deque([(i, j)])
12 visited[i][j] = True
13 max_row, max_col = i, j
14
15 while queue:
16 row, col = queue.popleft()
17 max_row, max_col = max(max_row, row), max(max_col, col)
18
19 for drow, dcol in [(0, 1), (1, 0)]:
20 nrow, ncol = row + drow, col + dcol
21 if nrow < m and ncol < n and land[nrow][ncol] == 1 and not visited[nrow][ncol]:
22 visited[nrow][ncol] = True
23 queue.append((nrow, ncol))
24
25 results.append([i, j, max_row, max_col])
26
27 return resultsPython solution makes use of a deque for the BFS. Each expansion checks two directions to find the maximum row and column for the farm group.
This approach implements a Union-Find (also called Disjoint Set Union) data structure to efficiently group farmland cells together. After processing all connections, each cell will belong to a group denoted by its root, and by traversing all cells, we can identify the top-left and bottom-right corners of each group.
Time Complexity: O(m * n * α(n)), with α being the inverse Ackermann function, which grows very slowly, making this almost O(m * n).
Space Complexity: O(m * n) due to storage for parents and ranks of each cell.
#include <unordered_map>
using namespace std;
class Solution {
public:
vector<int> parent, rank;
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
vector<vector<int>> findFarmland(vector<vector<int>>& land) {
int m = land.size();
int n = land[0].size();
parent.resize(m * n);
rank.resize(m * n, 0);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (land[i][j] == 1) {
int index = i * n + j;
parent[index] = index;
if (i > 0 && land[i-1][j] == 1) {
unionSets(index, (i-1) * n + j);
}
if (j > 0 && land[i][j-1] == 1) {
unionSets(index, i * n + (j-1));
}
}
}
}
unordered_map<int, vector<int>> bounds;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (land[i][j] == 1) {
int root = find(i * n + j);
if (!bounds.count(root)) {
bounds[root] = {i, j, i, j};
} else {
bounds[root][0] = min(bounds[root][0], i);
bounds[root][1] = min(bounds[root][1], j);
bounds[root][2] = max(bounds[root][2], i);
bounds[root][3] = max(bounds[root][3], j);
}
}
}
}
vector<vector<int>> results;
for (auto& bound : bounds) {
results.push_back(bound.second);
}
return results;
}
};This implementation in C++ uses the Union-Find structure to unite connected farmland cells. The results are determined by traversing the parent nodes to derive rectangular coordinates.