Practice Find All Groups of Farmland
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Find All Groups of Farmland
Problem Statement
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.
Source: Find All Groups of Farmland on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
land = [[1,0,0],[0,1,1],[0,1,1]]
[[0,0,0,0],[1,1,2,2]]
The cell at (0,0) forms a one-cell rectangle, represented by [0,0,0,0]. The other four farmland cells occupy rows 1 through 2 and columns 1 through 2, giving [1,1,2,2]. Although (0,0) touches (1,1) diagonally, diagonal contact does not connect groups: only shared edges count. Each output uses inclusive corner coordinates, so a one-cell group's top-left and bottom-right coordinates are identical. The two rectangles can be returned in either order.
# Example 2
land = [[1,1],[1,1]]
[[0,0,1,1]]
All four cells share edges and fill one rectangle spanning rows 0 through 1 and columns 0 through 1. Its top-left corner is (0,0), its bottom-right corner is (1,1), and the answer is [[0,0,1,1]]. Return one record for the whole connected rectangle, not one per row or per farmland cell. In a row-by-row scan, a farmland cell with no farmland immediately above or to its left identifies the rectangle's top-left corner.
# Example 3
land = [[0]]
[]
The only cell is 0, which represents forest rather than farmland. There is no group to report, so return the empty list []. In particular, do not emit [0,0,0,0] just because those are the grid's corner coordinates: that record would describe a one-cell farmland group, and the input has none.
Constraints
How to solve Find All Groups of Farmland
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
Because every group is a solid rectangle with no neighboring group, a farmland cell with forest or the border directly above it and directly to its left must be a top-left corner, and walking right and down from it until forest or the edge gives the opposite corner with no visited bookkeeping.
Why brute force is not enough
Testing every candidate rectangle for being entirely farmland means O(m^2 n^2) candidates times the check, hopeless at 300 by 300. A generic flood fill works in O(mn) but needs a visited matrix and more code than the structure of the input requires.
Approach
- Scan the grid in row-major order and skip forest cells.
- For a farmland cell, check whether the cell above (if any) and the cell to the left (if any) are forest; only then is it a group's top-left corner, so every group is discovered exactly once.
- From the corner, extend right along the same row while cells are farmland and in bounds to find the right column.
- Extend down along the corner's column the same way to find the bottom row; rectangularity guarantees these two walks determine the whole group.
- Append the four coordinates and continue scanning; return the list, which stays empty when no farmland exists.
Walkthrough of Example 1
land = [[1,0,0],[0,1,1],[0,1,1]] → [[0,0,0,0],[1,1,2,2]]
- Cell (0,0) is farmland with nothing above and nothing to the left, so it is a corner; moving right hits 0 at (0,1) and moving down hits 0 at (1,0), so the group is [0,0,0,0].
- Cells (0,1), (0,2) and (1,0) are forest and are skipped.
- Cell (1,1) is farmland with forest above at (0,1) and forest to the left at (1,0), so it is a corner; moving right reaches (1,2) then the edge, moving down reaches (2,1) then the edge, giving [1,1,2,2].
- Cells (1,2), (2,1) and (2,2) each have farmland above or to the left and are skipped. Output [[0,0,0,0],[1,1,2,2]].
Time and space
Time O(m n) · Space O(1). m and n are the grid dimensions; every cell is examined once in the scan, the corner walks revisit each farmland cell at most twice more along one row and one column, and no memory beyond the output is needed.
Interview pitfalls
- Checking only the cell above or only the cell to the left; both must be forest or out of bounds to identify a corner.
- Walking right or down without a bounds check, running off the grid for groups that touch the border.
- Treating diagonal contact as adjacency; example 1 has two groups touching only at a corner.
- Emitting [0,0,0,0] for an all-forest grid instead of an empty list.
- If flood filling instead, failing to track both the minimum and maximum row and column, or marking cells visited only after duplicates are already queued.
Follow-up questions interviewers ask
- If groups were arbitrary connected shapes, how would you return each one's bounding box?
- How would you verify the input guarantee that groups are rectangular and non-adjacent?
- If the grid streams in one row at a time, can you still emit rectangles with memory proportional to one row?
Related LeetCode Problems
Practice more problems similar to Find All Groups of Farmland.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.