Find All Groups of Farmland

Find All Groups of Farmland

What is this problem about?

The Find All Groups of Farmland interview question provides a 2D binary grid where 1s represent farmland and 0s represent forested land. Farmland is organized into rectangular groups. You are guaranteed that these rectangles are disjoint (they don't touch even diagonally). Your task is to find the coordinates of the top-left and bottom-right corners of every farmland rectangle.

Why is this asked in interviews?

Meta and Google use this problem to evaluate a candidate's ability to navigate 2D matrices and identify connected components. It’s a variation of the "Number of Islands" problem but with stricter geometric constraints (rectangles). It evaluation your proficiency with Graph Traversal interview patterns and your ability to extract bounding box information from a set of connected points.

Algorithmic pattern used

There are two main ways to solve this:

1. DFS/BFS Traversal: When you find a 1, start a traversal. As you visit all cells in the rectangle, keep track of the minimum/maximum row and column indices found.
2. Greedy Linear Scan: Since the groups are guaranteed to be rectangles, the top-left corner is the first 1 you encounter that hasn't been visited. Once you find a top-left corner $(r1, c1)$, you can simply expand right and down to find the boundaries $(r2, c2)$ and mark all cells in between as visited.

Example explanation

Grid:

[1, 1, 0]
[1, 1, 0]
[0, 0, 1]

1. Start at (0,0). It's a 1.
2. Find the rectangle dimensions: moves right to col 1, down to row 1.
3. Top-left: (0,0), Bottom-right: (1,1).
4. Mark all indices in [0...1, 0...1] as visited.
5. Continue scanning. Next unvisited 1 is at (2,2).
6. Top-left: (2,2), Bottom-right: (2,2). Result: [[0,0,1,1], [2,2,2,2]].

Common mistakes candidates make

• Over-traversing: Not marking cells as visited, leading to the same rectangle being reported multiple times.
• Incorrect boundary logic: Failing to find the farthest bottom-right corner.
• Complexity: Writing complex BFS logic when a simple nested loop expansion would suffice given the "rectangular" guarantee.

Interview preparation tip

Always look at the problem constraints. The "guaranteed rectangular" and "disjoint" conditions are massive hints that simplify the connectivity logic. You don't need a full BFS/DFS if you can just follow the edges of the rectangle.