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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int[][] FindFarmland(int[][] land) {
6 int m = land.Length;
7 int n = land[0].Length;
8 bool[,] visited = new bool[m, n];
9 var results = new List<int[]>();
10
11 for (int i = 0; i < m; i++) {
12 for (int j = 0; j < n; j++) {
13 if (land[i][j] == 1 && !visited[i, j]) {
14 int maxRow = i, maxCol = j;
15 var queue = new Queue<(int, int)>();
16 queue.Enqueue((i, j));
17 visited[i, j] = true;
18
19 while (queue.Count > 0) {
20 var (row, col) = queue.Dequeue();
21 maxRow = Math.Max(maxRow, row);
22 maxCol = Math.Max(maxCol, col);
23
24 int[,] directions = { {0, 1}, {1, 0} };
25 for (int d = 0; d < directions.GetLength(0); d++) {
26 int newRow = row + directions[d, 0], newCol = col + directions[d, 1];
27 if (newRow < m && newCol < n && land[newRow][newCol] == 1 && !visited[newRow, newCol]) {
28 visited[newRow, newCol] = true;
29 queue.Enqueue((newRow, newCol));
30 }
31 }
32 }
33 results.Add(new int[] { i, j, maxRow, maxCol });
34 }
35 }
36 }
37 return results.ToArray();
38 }
39}The C# approach uses BFS to traverse each group of farmland. It checks cells' unvisited status and '1' value for expansion, determining the farmland's boundaries.
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.
The Union-Find method first connects all farmland cells through union operations to find connected components. Each component is evaluated to find the top-left and bottom-right coordinates.