Problem Description

You have a 2D binary matrix called land where:

• 0 represents forested land (trees)
• 1 represents farmland

The farmland is organized into rectangular groups where:

• Each group is a rectangle consisting entirely of 1s (farmland)
• No two groups are adjacent to each other (they don't touch horizontally or vertically)

Your task is to find all these rectangular groups of farmland and return their coordinates.

For each group, you need to identify:

• The top-left corner coordinates (r1, c1)
• The bottom-right corner coordinates (r2, c2)

Each group should be represented as a 4-element array: [r1, c1, r2, c2]

The coordinate system works as follows:

• (0, 0) is the top-left corner of the entire matrix
• (m-1, n-1) is the bottom-right corner of the entire matrix

Return a 2D array containing all the groups found. If there are no farmland groups, return an empty array. The groups can be returned in any order.

Example: If you have a farmland rectangle from position (1, 2) to (3, 4), it would be represented as [1, 2, 3, 4].

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: While the problem presents itself as a 2D matrix, we can view it as a graph problem where each cell is a node and adjacent cells (up, down, left, right) form edges. We need to explore connected components of farmland (cells with value 1).

Is it a tree?

• No: The structure is not a tree. We have a 2D grid where cells can be connected in multiple ways, and we're looking for rectangular regions rather than hierarchical relationships.

Is the problem related to directed acyclic graphs?

• No: The problem doesn't involve directed edges or acyclic properties. We're dealing with an undirected grid where we explore connected farmland cells.

Is the problem related to shortest paths?

• No: We're not finding shortest paths between points. Instead, we're identifying and delimiting rectangular regions of connected farmland.

Does the problem involve connectivity?

• Yes: The core of the problem is finding connected components of farmland (1s) that form rectangular shapes. We need to explore each connected region to find its boundaries.

Does the problem have small constraints?

• Yes: While not explicitly stated in the problem, grid problems typically have reasonable constraints that allow for DFS/BFS traversal without timeout issues.

DFS/backtracking?

• Yes: DFS is perfect for this problem. When we find an unvisited farmland cell that starts a new group (top-left corner), we can use DFS to explore the entire rectangular region and find its bottom-right corner.

Conclusion: The flowchart suggests using DFS to explore each farmland group. The solution uses a modified DFS approach where, upon finding a new group's top-left corner, it extends downward and rightward to find the rectangular boundary, effectively exploring the connected component.

Intuition

The key insight is recognizing that each farmland group forms a perfect rectangle. This means once we find the top-left corner of a group, we can determine its full extent by simply expanding downward and rightward until we hit the boundaries.

Think about how you would manually identify rectangles on a grid:

1. You'd scan from top to bottom, left to right
2. When you find a 1 that hasn't been part of a previous rectangle, you know it must be a top-left corner of a new group
3. From that corner, you'd trace how far the rectangle extends

The clever part of this solution is identifying when we've found a new top-left corner. A cell with value 1 is a top-left corner of a new group only if:

• It doesn't have a 1 above it (otherwise it would be part of a rectangle that started earlier)
• It doesn't have a 1 to its left (for the same reason)

Once we identify a top-left corner at position (i, j), finding the bottom-right corner is straightforward:

• Keep moving down (increasing row) while we still see 1s to find the bottom boundary
• Keep moving right (increasing column) while we still see 1s to find the right boundary

This approach works because the problem guarantees that farmland groups are perfect rectangles with no adjacent groups. We don't need complex DFS traversal or marking visited cells because:

• Each rectangle is processed exactly once (when we find its top-left corner)
• We skip cells that are part of already-identified rectangles (they have a 1 above or to the left)

The algorithm essentially performs a single pass through the matrix, making it efficient with O(m*n) time complexity where each cell is examined once.

Learn more about Depth-First Search and Breadth-First Search patterns.

Solution Approach

The implementation follows a systematic scanning approach to identify and process each farmland group:

1. Matrix Traversal: We iterate through each cell of the matrix using nested loops:

for i in range(m):
    for j in range(n):

2. Skip Non-Corner Cells: For each cell at position (i, j), we check if it's a valid top-left corner of a new group. We skip the cell if:

• It contains 0 (forested land, not farmland)
• It has a 1 to its left: j > 0 and land[i][j - 1] == 1
• It has a 1 above it: i > 0 and land[i - 1][j] == 1

These conditions ensure we only process cells that are true top-left corners of farmland groups.

3. Find Bottom-Right Corner: Once we identify a top-left corner at (i, j), we need to find the corresponding bottom-right corner:

x, y = i, j
while x + 1 < m and land[x + 1][j] == 1:
    x += 1
while y + 1 < n and land[x][y + 1] == 1:
    y += 1

• First, we extend downward from column j: Keep incrementing x while the cell below is still farmland (1)
• Then, we extend rightward from the bottom row x: Keep incrementing y while the cell to the right is still farmland (1)

Note: The order matters here. We first find the bottom boundary, then use that row to find the right boundary. This works because farmland groups are guaranteed to be perfect rectangles.

4. Record the Group: After finding both corners, we add the group's coordinates to our result:

ans.append([i, j, x, y])

Data Structures Used:

• 2D List (Matrix): The input land matrix
• Result List: ans stores the coordinates of all farmland groups as [r1, c1, r2, c2] arrays

Time Complexity: O(m × n) where m and n are the dimensions of the matrix. Each cell is visited once during the main traversal.

Space Complexity: O(1) extra space (not counting the output array), as we only use a few variables to track positions.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach:

land = [[1, 1, 0, 0],
        [1, 1, 0, 1],
        [0, 0, 1, 1]]

Step 1: Start scanning from (0,0)

• Cell (0,0) contains 1
• No cell above (i=0), no cell to the left (j=0)
• This is a top-left corner of a new group!

Step 2: Find bottom-right corner from (0,0)

• Extend downward from column 0:
  • (1,0) has 1, so x becomes 1
  • (2,0) has 0, stop extending down
  • Bottom boundary is at row 1
• Extend rightward from row 1:
  • (1,1) has 1, so y becomes 1
  • (1,2) has 0, stop extending right
  • Right boundary is at column 1
• Bottom-right corner is (1,1)
• Add [0, 0, 1, 1] to result

Step 3: Continue scanning

• (0,1): Contains 1 but has a 1 to its left → skip
• (0,2): Contains 0 → skip
• (0,3): Contains 0 → skip
• (1,0): Contains 1 but has a 1 above it → skip
• (1,1): Contains 1 but has both 1 above and to the left → skip
• (1,2): Contains 0 → skip
• (1,3): Contains 1, no 1 above, no 1 to the left → new top-left corner!

Step 4: Find bottom-right corner from (1,3)

• Extend downward from column 3:
  • (2,3) has 1, so x becomes 2
  • No more rows, stop
  • Bottom boundary is at row 2
• Extend rightward from row 2:
  • No more columns, stop
  • Right boundary is at column 3
• Bottom-right corner is (2,3)
• Add [1, 3, 2, 3] to result

Step 5: Continue scanning remaining cells

• (2,0): Contains 0 → skip
• (2,1): Contains 0 → skip
• (2,2): Contains 1, no 1 above, no 1 to the left → new top-left corner!

Step 6: Find bottom-right corner from (2,2)

• Extend downward from column 2:
  • No more rows, stop at row 2
• Extend rightward from row 2:
  • (2,3) has 1, so y becomes 3
  • No more columns, stop
• Bottom-right corner is (2,3)
• Add [2, 2, 2, 3] to result

Step 7: Final cell

• (2,3): Contains 1 but has a 1 to its left → skip

Final Result: [[0, 0, 1, 1], [1, 3, 2, 3], [2, 2, 2, 3]]

Wait, there's an issue here. Let me reconsider the last group.

Actually, looking at (2,2) and (2,3), they should form a single rectangle. When we process (2,2):

• It has no 1 above or to the left, so it's a valid top-left corner
• Extending right from (2,2): (2,3) has 1, so the rectangle extends to column 3
• The group is [2, 2, 2, 3]

Then when we reach (2,3), it has a 1 to its left (at position (2,2)), so we skip it.

Corrected Final Result: [[0, 0, 1, 1], [1, 3, 1, 3], [2, 2, 2, 3]]

The three rectangular farmland groups are:

1. A 2×2 rectangle from (0,0) to (1,1)
2. A 1×1 rectangle at (1,3)
3. A 1×2 rectangle from (2,2) to (2,3)

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the land matrix.

The algorithm iterates through each cell in the matrix once with the nested loops, which gives us O(m * n) for the main traversal. For each farmland group found (when we encounter a top-left corner), we perform two while loops to find the bottom-right corner. However, each cell is only visited at most twice in total throughout the entire algorithm:

• Once during the main iteration
• At most once during the expansion (either horizontal or vertical)

The key optimization is the condition (j > 0 and land[i][j - 1] == 1) or (i > 0 and land[i - 1][j] == 1) which ensures we only process top-left corners of farmland rectangles. This means the while loops only execute for top-left corners, and each cell within a farmland is checked at most once during expansion. Therefore, the overall time complexity remains O(m * n).

Space Complexity: O(1) excluding the output array, or O(k) including the output array where k is the number of farmland groups.

The algorithm uses only a constant amount of extra space for variables i, j, x, and y. The space used by the answer list ans depends on the number of farmland groups in the input, which in the worst case could be O(m * n / 4) if the farmland forms a checkerboard pattern of 1x1 rectangles. However, if we don't count the output space (which is often the convention), the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Boundary Detection Order

The Problem: A common mistake is trying to find the right boundary first, then the bottom boundary:

# INCORRECT approach
right_col = col
while right_col + 1 < cols and land[row][right_col + 1] == 1:
    right_col += 1

bottom_row = row  
while bottom_row + 1 < rows and land[bottom_row + 1][right_col] == 1:
    bottom_row += 1

This fails because when extending downward, you're checking along the rightmost column instead of the leftmost column. This could miss part of the rectangle or incorrectly identify the boundary.

Why It Fails: Consider this farmland:

1 1 1
1 1 0
1 0 0

Starting at (0,0), if you extend right first to column 2, then try to extend down from column 2, you'll stop at row 0 (since land[1][2] = 0), missing the full rectangle.

The Solution: Always extend downward first using the leftmost column, then extend rightward using the bottom row:

# CORRECT approach
bottom_row = row
while bottom_row + 1 < rows and land[bottom_row + 1][col] == 1:
    bottom_row += 1
  
right_col = col
while right_col + 1 < cols and land[bottom_row][right_col + 1] == 1:
    right_col += 1

Pitfall 2: Not Properly Identifying Top-Left Corners

The Problem: Forgetting to check both left and upper neighbors can lead to processing the same farmland multiple times:

# INCORRECT - only checking one direction
if col > 0 and land[row][col - 1] == 1:
    continue

Why It Fails: A cell could have no farmland to its left but still have farmland above it, meaning it's not a true top-left corner. This results in identifying overlapping or duplicate rectangles.

The Solution: Always check both the left and upper neighbors to ensure you're at a true top-left corner:

# CORRECT - checking both directions
if (col > 0 and land[row][col - 1] == 1) or \
   (row > 0 and land[row - 1][col] == 1):
    continue

Pitfall 3: Off-by-One Errors in Boundary Checking

The Problem: Using incorrect boundary conditions when extending the rectangle:

# INCORRECT - using <= instead of <
while bottom_row + 1 <= rows and land[bottom_row + 1][col] == 1:
    bottom_row += 1

Why It Fails: This causes an index out of bounds error when bottom_row + 1 equals rows, as you'd be trying to access land[rows][col] which doesn't exist.

The Solution: Use strict inequality (<) to ensure you stay within bounds:

# CORRECT - proper boundary checking
while bottom_row + 1 < rows and land[bottom_row + 1][col] == 1:
    bottom_row += 1