_1992. Find All Groups of Farmland.md

1992. Find All Groups of Farmland

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 24, 2024

Last updated : June 24, 2024

---

Related Topics : Array, Depth-First Search, Breadth-First Search, Matrix

Acceptance Rate : 75.814 %

---

Solutions

• m1992.java
• m1992.py

Java

m1992.java

class Solution {
    public int[][] findFarmland(int[][] land) {
        ArrayList<int[]> output = new ArrayList<>();

        for (int r = 0; r < land.length; r++) {
            for (int c = 0; c < land[0].length; c++) {
                if (land[r][c] == 1                         // Corner found
                    && (r == 0 || land[r - 1][c] == 0)
                    && (c == 0 || land[r][c - 1] == 0)) {
                    int[] group = new int[4];
                    group[0] = r;
                    group[1] = c;

                    for (int i = r + 1;; i++) {
                        if (i >= land.length || land[i][c] == 0) {
                            group[2] = i - 1;
                            break;
                        }
                    }
                    for (int i = c + 1;; i++) {
                        if (i >= land[0].length || land[r][i] == 0) {
                            group[3] = i - 1;
                            break;
                        }
                    }

                    output.add(group);
                }
            }
        }

        int[][] actualOutput = new int[output.size()][];
        for (int i = 0; i < output.size(); i++) {
            actualOutput[i] = output.get(i);
        }

        return actualOutput;
    }
}

Python

m1992.py

class Solution:
    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
        output:List[List[int]] = []

        for r in range(len(land)) :
            for c in range(len(land[0])) :
                if land[r][c] \
                    and (r == 0 or not land[r - 1][c]) \
                    and (c == 0 or not land[r][c - 1]) :
                    output.append([r, c, r, c])
                    
                    rRight, cRight = r, c
                    while True :
                        if rRight >= len(land) or land[rRight][c] == 0 :
                            output[-1][2] = rRight - 1
                            break
                        rRight += 1
                    while True :
                        if cRight >= len(land[0]) or land[r][cRight] == 0 :
                            output[-1][3] = cRight - 1
                            break
                        cRight += 1
        
        return output