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.
JavaScript implements union-find to handle connected farmland components by linking and managing ranks. The boundaries are computed based on the connected components.