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.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.
The solution uses BFS to identify connected farmland cells that form a rectangle. By starting from each unvisited '1' cell, the algorithm explores in the right and downward directions to find the boundaries. Each boundary-found block is recorded.
C++
Java
Python
C#
JavaScript
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.
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.
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.
C++
Java
Python
C#
JavaScript
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.
| Approach | Complexity |
|---|---|
| Approach 1: Breadth-First Search (BFS) to Identify Farmland Groups | 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. |
| Approach 2: Union-Find to Detect Connected Components | 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. |
Find All Groups of Farmland | DFS | BFS | Brute Force | Leetcode 1992 | codestorywithMIK • codestorywithMIK • 5,127 views views
Watch 9 more video solutions →Practice Find All Groups of Farmland with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor