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.
Java's implementation details the Union-Find to connect and track farmlands, with subsequent evaluation to list rectangular boundaries.