Watch 10 video solutions for Find All Groups of Farmland, a medium level problem involving Array, Depth-First Search, Breadth-First Search. This walkthrough by codestorywithMIK has 5,913 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed m x n binary matrix land where a 0 represents a hectare of forested land and a 1 represents a hectare of farmland.
To keep the land organized, there are designated rectangular areas of hectares that consist entirely of farmland. These rectangular areas are called groups. No two groups are adjacent, meaning farmland in one group is not four-directionally adjacent to another farmland in a different group.
land can be represented by a coordinate system where the top left corner of land is (0, 0) and the bottom right corner of land is (m-1, n-1). Find the coordinates of the top left and bottom right corner of each group of farmland. A group of farmland with a top left corner at (r1, c1) and a bottom right corner at (r2, c2) is represented by the 4-length array [r1, c1, r2, c2].
Return a 2D array containing the 4-length arrays described above for each group of farmland in land. If there are no groups of farmland, return an empty array. You may return the answer in any order.
Example 1:
Input: land = [[1,0,0],[0,1,1],[0,1,1]] Output: [[0,0,0,0],[1,1,2,2]] Explanation: The first group has a top left corner at land[0][0] and a bottom right corner at land[0][0]. The second group has a top left corner at land[1][1] and a bottom right corner at land[2][2].
Example 2:
Input: land = [[1,1],[1,1]] Output: [[0,0,1,1]] Explanation: The first group has a top left corner at land[0][0] and a bottom right corner at land[1][1].
Example 3:
Input: land = [[0]] Output: [] Explanation: There are no groups of farmland.
Constraints:
m == land.lengthn == land[i].length1 <= m, n <= 300land consists of only 0's and 1's.Problem Overview: You are given a binary matrix where 1 represents farmland and 0 represents forest. Each farmland group forms a rectangular region of connected 1s. The task is to identify every group and return the coordinates of its top-left and bottom-right corners.
Approach 1: Breadth-First Search (BFS) to Identify Farmland Groups (Time: O(m*n), Space: O(m*n))
Scan the grid cell by cell. When you encounter an unvisited farmland cell (1), start a BFS from that position to explore the entire connected component. Use a queue and expand in four directions (up, down, left, right). While traversing, track the minimum and maximum row/column indices visited. These boundaries define the rectangle for that farmland group. Mark cells as visited to avoid processing them again.
This works because each farmland region is a connected block in the grid. BFS guarantees that all adjacent farmland cells are explored in one traversal. The algorithm touches every cell at most once, giving O(m*n) time complexity and O(m*n) space in the worst case for the visited structure and queue. This technique is a classic application of Breadth-First Search on a matrix grid.
Approach 2: Union-Find to Detect Connected Components (Time: O(m*n Îą(m*n)), Space: O(m*n))
Another option treats each farmland cell as a node in a disjoint-set structure. Iterate through the grid and union adjacent farmland cells (typically right and down neighbors to avoid duplicates). After building the sets, each root represents one connected farmland component. For every component, compute the bounding rectangle by tracking the minimum and maximum row and column indices among all cells belonging to that root.
The Union-Find data structure performs near-constant-time merges and finds due to path compression and union by rank. The total complexity becomes O(m*n Îą(m*n)), where Îą is the inverse Ackermann function. This approach is useful if you already use array-based disjoint sets or when solving multiple connectivity queries on the same grid.
Recommended for interviews: The BFS/DFS grid traversal is the approach most interviewers expect. It is simple, linear in time, and directly models the problem as a connected-component search. Implementing BFS or Depth-First Search shows strong understanding of graph traversal on matrices. Union-Find works as well but adds extra implementation overhead unless the problem explicitly requires dynamic connectivity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (BFS) Grid Traversal | O(m*n) | O(m*n) | Best general solution for detecting connected farmland regions in a matrix. |
| Union-Find (Disjoint Set) | O(m*n Îą(m*n)) | O(m*n) | Useful when solving multiple connectivity problems or when components must be merged dynamically. |