Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1992.html

1992. Find All Groups of Farmland

Level

Medium

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.

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.

Example 1:

Image text

Input: land = [[1,0,0],[0,1,1],[0,1,1]]

Output: [[0,0,0,0],[1,1,2,2]]

Explanation:

The first group has a top left corner at land[0][0] and a bottom right corner at land[0][0].

The second group has a top left corner at land[1][1] and a bottom right corner at land[2][2].

Example 2:

Image text

Input: land = [[1,1],[1,1]]

Output: [[0,0,1,1]]

Explanation:

The first group has a top left corner at land[0][0] and a bottom right corner at land[1][1].

Example 3:

Image text

Input: land = [[0]]

Output: []

Explanation:

There are no groups of farmland.

Constraints:

  • m == land.length
  • n == land[i].length
  • 1 <= m, n <= 300
  • land consists of only 0’s and 1’s.
  • Groups of farmland are rectangular in shape.

Solution

For each farmland, do breadth first search and return the top left corner and the bottom right corner of the farmland. Each farmland will be visited exactly once. Return the corners of the farmlands.

  • class Solution {
    public int[][] findFarmland(int[][] land) {
        List<int[]> farmlandsList = new ArrayList<int[]>();
        int rows = land.length, columns = land[0].length;
        boolean[][] visited = new boolean[rows][columns];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (land[i][j] == 1 && !visited[i][j]) {
                    int[] farmland = breadthFirstSearch(land, visited, i, j);
                    farmlandsList.add(farmland);
                }
            }
        }
        int size = farmlandsList.size();
        int[][] farmlands = new int[size][4];
        for (int i = 0; i < size; i++) {
            int[] farmland = farmlandsList.get(i);
            for (int j = 0; j < 4; j++)
                farmlands[i][j] = farmland[j];
        }
        return farmlands;
    }

    public int[] breadthFirstSearch(int[][] land, boolean[][] visited, int row, int column) {
        int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
        int rows = land.length, columns = land[0].length;
        int[] farmland = {rows, columns, -1, -1};
        visited[row][column] = true;
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[]{row, column});
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int curRow = cell[0], curColumn = cell[1];
            farmland[0] = Math.min(farmland[0], curRow);
            farmland[1] = Math.min(farmland[1], curColumn);
            farmland[2] = Math.max(farmland[2], curRow);
            farmland[3] = Math.max(farmland[3], curColumn);
            for (int[] direction : directions) {
                int newRow = curRow + direction[0], newColumn = curColumn + direction[1];
                if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && land[newRow][newColumn] == 1 && !visited[newRow][newColumn]) {
                    visited[newRow][newColumn] = true;
                    queue.offer(new int[]{newRow, newColumn});
                }
            }
        }
        return farmland;
    }
}

############

class Solution {
    public int[][] findFarmland(int[][] land) {
        List<int[]> ans = new ArrayList<>();
        int m = land.length;
        int n = land[0].length;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (land[i][j] == 0 || (j > 0 && land[i][j - 1] == 1)
                    || (i > 0 && land[i - 1][j] == 1)) {
                    continue;
                }
                int x = i;
                int y = j;
                for (; x + 1 < m && land[x + 1][j] == 1; ++x)
                    ;
                for (; y + 1 < n && land[x][y + 1] == 1; ++y)
                    ;
                ans.add(new int[] {i, j, x, y});
            }
        }
        return ans.toArray(new int[ans.size()][4]);
    }
}

  • // OJ: https://leetcode.com/problems/find-all-groups-of-farmland/
// Time: O(MN)
// Space: O(MN)
class Solution {
    int M, N, dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
    void dfs(vector<vector<int>> &A, int i, int j, int &bottom, int &right) {
        A[i][j] = 0;
        bottom = max(bottom, i);
        right = max(right, j);
        for (auto &[dx, dy] : dirs) {
            int x = i + dx, y = j + dy;
            if (x < 0 || x >= M || y < 0 || y >= N || A[x][y] == 0) continue;
            dfs(A, x, y, bottom, right);
        }
    }
public:
    vector<vector<int>> findFarmland(vector<vector<int>>& A) {
        M = A.size(), N = A[0].size();
        vector<vector<int>> ans;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (A[i][j] == 0) continue;
                int bottom = i, right = j;
                dfs(A, i, j, bottom, right);
                ans.push_back({i, j, bottom, right});
            }
        }
        return ans;
    }
};

  • class Solution:
    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
        m, n = len(land), len(land[0])
        ans = []
        for i in range(m):
            for j in range(n):
                if (
                    land[i][j] == 0
                    or (j > 0 and land[i][j - 1] == 1)
                    or (i > 0 and land[i - 1][j] == 1)
                ):
                    continue
                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
                ans.append([i, j, x, y])
        return ans

############

# 1992. Find All Groups of Farmland
# https://leetcode.com/problems/find-all-groups-of-farmland

class Solution:
    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
        rows, cols = len(land), len(land[0])
        res = []
        
        for r1 in range(rows):
            for c1 in range(cols):
                if land[r1][c1] == 0: continue
                
                r2, c2 = r1, c1
                while c2 < cols and land[r2][c2] == 1:
                    c2 += 1
                
                while r2 < rows and land[r2][c1] == 1:
                    r2 += 1
                
                r2 = r2 if r2 == 0 else r2 - 1
                c2 = c2 if c2 == 0 else c2 - 1
                
                res.append([r1, c1, r2, c2])
                
                for row in range(r1, r2 + 1):
                    for col in range(c1, c2 + 1):
                        land[row][col] = 0
        
        return res


  • func findFarmland(land [][]int) [][]int {
	m, n := len(land), len(land[0])
	var ans [][]int
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if land[i][j] == 0 || (j > 0 && land[i][j-1] == 1) || (i > 0 && land[i-1][j] == 1) {
				continue
			}
			x, y := i, j
			for ; x+1 < m && land[x+1][j] == 1; x++ {
			}
			for ; y+1 < n && land[x][y+1] == 1; y++ {
			}
			ans = append(ans, []int{i, j, x, y})
		}
	}
	return ans
}

All Problems

All Solutions