We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find All Groups of Farmland

Number: 2103

Difficulty: Medium

Paid? No

Companies: Meta, Citrix

Problem Description

Given an m x n binary matrix land, where 0 represents forest land and 1 represents farmland, find all rectangular groups of farmland. Each group is a contiguous rectangular block of 1's that is not adjacent (four-directionally) to any farmland from a different group. Return the coordinates of the top left and bottom right corners for each group.

Key Insights

  • The farmland groups are rectangular and non-adjacent; hence, once you find a farmland cell that is not visited, you can determine the entire rectangle.
  • Use a double loop to iterate through each cell and when a 1 is encountered, determine the boundaries (bottom and right extents) of its group.
  • Mark the entire rectangle as visited (or modify the matrix) so that overlapping is avoided.
  • The problem can be solved in O(m*n) time since each cell is visited at most once.

Space and Time Complexity

Time Complexity: O(mn)
Space Complexity: O(1) extra space (if modifying the input is allowed) or O(mn) if a separate visited array is used.

Solution

The solution iterates over each cell in the matrix. When an unvisited farmland cell (value 1) is discovered, it is treated as the top left corner of a farmland group. Then, the algorithm expands in both the right and downward directions to determine the bottom right corner of that rectangle. After determining the bounds of the rectangle, all cells within are marked as visited by setting them to 0 (or using a visited marker) to prevent re-visiting. This guarantees that each farmland group is processed exactly once.

Code Solutions

# Python solution for finding all groups of farmland
def findFarmland(land):
    # Get matrix dimensions
    m, n = len(land), len(land[0])
    result = []
    
    # Iterate over each cell in the grid
    for i in range(m):
        for j in range(n):
            # If current cell is farmland (1)
            if land[i][j] == 1:
                # set the top-left corner of the farmland group
                topRow, leftCol = i, j
                
                # Find the bottom boundary (furthest row with 1 in the same column)
                bottomRow = i
                while bottomRow < m and land[bottomRow][j] == 1:
                    bottomRow += 1
                bottomRow -= 1
                
                # Find the right boundary (furthest col with 1 in the same row)
                rightCol = j
                while rightCol < n and land[i][rightCol] == 1:
                    rightCol += 1
                rightCol -= 1
                
                # Mark the entire rectangle as visited by setting cells to 0
                for r in range(i, bottomRow + 1):
                    for c in range(j, rightCol + 1):
                        land[r][c] = 0
                        
                # Add the group's coordinates to the result
                result.append([topRow, leftCol, bottomRow, rightCol])
    return result

# Example usage:
# land = [[1,0,0],[0,1,1],[0,1,1]]
# print(findFarmland(land))
← Back to All Questions