Leetcode | Find All Groups of Farmland | Java

devstromo · devstromo · commit 9f9964137b62 · 2025-04-18T22:56:22.000-03:00
diff --git a/leetcode/src/main/java/com/devstromo/medium/p1992/DESCRIPTION.md b/leetcode/src/main/java/com/devstromo/medium/p1992/DESCRIPTION.md
@@ -0,0 +1,39 @@
+# 1992. Find All Groups of Farmland
+
+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:
+
+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:
+
+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:
+
+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.
diff --git a/leetcode/src/main/java/com/devstromo/medium/p1992/Solution.java b/leetcode/src/main/java/com/devstromo/medium/p1992/Solution.java
@@ -0,0 +1,48 @@
+package com.devstromo.medium.p1992;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class Solution {
+    public int[][] findFarmland(int[][] land) {
+        if (land.length == 0 || land[0].length == 0) {
+            return new int[][]{
+                    {0}
+            };
+        }
+        int m = land.length, n = land[0].length;
+        List<int[]> result = new ArrayList<>();
+
+        // Visit all unvisited farmland cells (value == 1)
+        for (int r = 0; r < m; r++) {
+            for (int c = 0; c < n; c++) {
+                if (land[r][c] == 1) {
+                    int[] bounds = new int[]{r, c, r, c};
+                    dfs(land, r, c, bounds);
+                    result.add(bounds);
+                }
+            }
+        }
+
+        return result.toArray(new int[result.size()][]);
+    }
+
+    private void dfs(int[][] land, int r, int c, int[] bounds) {
+        int m = land.length, n = land[0].length;
+        // Base case: out of bounds or not farmland
+        if (r < 0 || r >= m || c < 0 || c >= n || land[r][c] != 1) return;
+
+        // Mark as visited
+        land[r][c] = -1;
+
+        // Update the bottom-right corner
+        bounds[2] = Math.max(bounds[2], r);
+        bounds[3] = Math.max(bounds[3], c);
+
+        // Explore 4 directions
+        dfs(land, r + 1, c, bounds);
+        dfs(land, r - 1, c, bounds);
+        dfs(land, r, c + 1, bounds);
+        dfs(land, r, c - 1, bounds);
+    }
+}
diff --git a/leetcode/src/test/java/com/devstromo/medium/p1992/SolutionUnitTest.java b/leetcode/src/test/java/com/devstromo/medium/p1992/SolutionUnitTest.java
@@ -0,0 +1,42 @@
+package com.devstromo.medium.p1992;
+
+import org.junit.jupiter.api.DisplayName;
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class SolutionUnitTest {
+    private final Solution solution = new Solution();
+
+    @Test
+    @DisplayName("Test  Find All Groups of Farmland")
+    void testFindAllGroupsOfFarmland() {
+        assertArrayEquals(
+                new int[][]{
+                        {0, 0, 0, 0},
+                        {1, 1, 2, 2},
+                },
+                solution.findFarmland(new int[][]{
+                        {1, 0, 0},
+                        {0, 1, 1},
+                        {0, 1, 1}
+                })
+        );
+        assertArrayEquals(
+                new int[][]{
+                        {0, 0, 1, 1}
+                },
+                solution.findFarmland(new int[][]{
+                        {1, 1},
+                        {1, 1}
+                })
+        );
+        assertArrayEquals(
+                new int[][]{
+                        {0}
+                },
+                solution.findFarmland(new int[][]{})
+        );
+    }
+
+}
