Problem Description
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. Find the coordinates of the top left and bottom right corner of each group of farmland, where a group of farmland consists entirely of adjacent 1s in a rectangular area. Return a 2D array containing the coordinates for each group of farmland.
Key Insights
- Each group of farmland is rectangular and non-adjacent to other groups.
- The top left corner of the rectangle can be identified when we first encounter a 1 that has not been visited.
- The bottom right corner can be determined by expanding right and down until we hit a 0 or the edge of the matrix.
- We need to keep track of visited cells to avoid counting the same group multiple times.
Space and Time Complexity
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix. Each cell is visited at most once. Space Complexity: O(1), not counting the output space, as we only use a few variables for tracking.
Solution
To solve the problem, we will iterate through each cell in the matrix. When we encounter a cell with a value of 1 that has not been visited, we will define it as the top left corner of a new group. We will then expand to find the bottom right corner by moving right and down until we hit a 0 or the end of the matrix. We will store the coordinates of each group in a result list.