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.
1var findFarmland = function(land) {
2 const m = land.length;
3 const n = land[0].length;
4 const visited = Array.from({ length: m }, () => Array(n).fill(false));
5 const results = [];
6
7 function bfs(row, col) {
8 const queue = [[row, col]];
9 let maxRow = row, maxCol = col;
10 visited[row][col] = true;
11
12 while (queue.length) {
13 const [r, c] = queue.shift();
14 maxRow = Math.max(maxRow, r);
15 maxCol = Math.max(maxCol, c);
16
17 const directions = [[0, 1], [1, 0]];
18 for (const [dr, dc] of directions) {
19 const newRow = r + dr, newCol = c + dc;
20 if (newRow < m && newCol < n && land[newRow][newCol] === 1 && !visited[newRow][newCol]) {
21 visited[newRow][newCol] = true;
22 queue.push([newRow, newCol]);
23 }
24 }
25 }
26 results.push([row, col, maxRow, maxCol]);
27 }
28
29 for (let i = 0; i < m; i++) {
30 for (let j = 0; j < n; j++) {
31 if (land[i][j] === 1 && !visited[i][j]) {
32 bfs(i, j);
33 }
34 }
35 }
36
37 return results;
38};
JavaScript version applies BFS similarly, using a queue to handle the traversal. It explores right and downward neighbors to extend the range of farmland.
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.
Java's implementation details the Union-Find to connect and track farmlands, with subsequent evaluation to list rectangular boundaries.