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.
1import java.util.*;
2
3class Solution {
4 public List<int[]> findFarmland(int[][] land) {
5 int m = land.length;
6 int n = land[0].length;
7 boolean[][] visited = new boolean[m][n];
8 List<int[]> results = new ArrayList<>();
9
10 for (int i = 0; i < m; i++) {
11 for (int j = 0; j < n; j++) {
12 if (land[i][j] == 1 && !visited[i][j]) {
13 int maxRow = i, maxCol = j;
14 Queue<int[]> queue = new LinkedList<>();
15 queue.offer(new int[]{i, j});
16 visited[i][j] = true;
17
18 while (!queue.isEmpty()) {
19 int[] coord = queue.poll();
20 int row = coord[0], col = coord[1];
21 maxRow = Math.max(maxRow, row);
22 maxCol = Math.max(maxCol, col);
23
24 int[][] directions = {{0, 1}, {1, 0}};
25 for (int[] dir : directions) {
26 int newRow = row + dir[0], newCol = col + dir[1];
27 if (newRow < m && newCol < n && land[newRow][newCol] == 1 && !visited[newRow][newCol]) {
28 visited[newRow][newCol] = true;
29 queue.offer(new int[]{newRow, newCol});
30 }
31 }
32 }
33 results.add(new int[]{i, j, maxRow, maxCol});
34 }
35 }
36 }
37 return results;
38 }
39}Java implementation uses a similar BFS method where each discovered '1' cell expands the discovery until no more unvisited '1's are reachable. Results collect start and end boundaries for each 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.
using System.Collections.Generic;
public class Solution {
public int[][] FindFarmland(int[][] land) {
int m = land.Length, n = land[0].Length;
int[] parent = new int[m * n];
int[] rank = new int[m * n];
for (int i = 0; i < m * n; i++) {
parent[i] = i;
}
int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]);
}
return parent[x];
}
void Union(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]++;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (land[i][j] == 1) {
int index = i * n + j;
if (i > 0 && land[i-1][j] == 1) {
Union(index, (i-1) * n + j);
}
if (j > 0 && land[i][j-1] == 1) {
Union(index, i * n + (j-1));
}
}
}
}
var bounds = new Dictionary<int, int[]>();
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.ContainsKey(root)) {
bounds[root] = new int[] { i, j, i, j };
} else {
bounds[root][0] = Math.Min(bounds[root][0], i);
bounds[root][1] = Math.Min(bounds[root][1], j);
bounds[root][2] = Math.Max(bounds[root][2], i);
bounds[root][3] = Math.Max(bounds[root][3], j);
}
}
}
}
var result = new List<int[]>(bounds.Values);
return result.ToArray();
}
}This C# solution leverages the efficiency of Union-Find for connecting farmland components: post-processing yields the corners per component for output.