Find All Groups Of Farmland - Leetcode Solution

The problem statement for "Find All Groups of Farmland" on LeetCode is as follows:

You are given a 2D integer array land representing a piece of land where the value of each cell represents the height of the terrain. The integer height denotes the height of the cell and is guaranteed to be unique.

A group of cells is a collection of cells that share the same height. Two cells are considered to be connected if they are adjacent cells with the same height.

Return a list of all groups of farmland, where a farmland is a group of connected cells with the same height and four-directionally adjacent.

A group of farmland is considered to be distinct if there is no group with the same set of cells.

Solution:

The problem can be solved using the concept of Connected Components of a graph. Each cell in the 2D grid can be considered as a node in a graph where edges connect nodes if their corresponding cells have the same height and are adjacent.

We need to find all connected components of this graph, i.e., all groups of cells that share the same height and are connected.

We can use the DFS (Depth First Search) algorithm to find all connected components in the graph. For this, we can start from any cell that has not been visited yet and perform a DFS search to explore all the neighbor cells that have the same height. We mark all these visited cells as a part of one group of farmland.

We repeat the process for all unvisited nodes, and we obtain all the groups of farmland. The cells belonging to each group can be stored in a list, and finally, we return the list of lists of cells, one list for each group of connected cells.

Here is the Python code implementing the above approach:

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

        def DFS(i, j, start_i, start_j):
            visited[i][j] = True
            end_i, end_j = i, j
            for (r, c) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                ni, nj = i + r, j + c
                if ni >= 0 and ni < n and nj >= 0 and nj < m and not visited[ni][nj] and land[ni][nj] == land[i][j]:
                    end_i, end_j = DFS(ni, nj, start_i, start_j)
            return end_i, end_j
        
        n, m = len(land), len(land[0])
        visited = [[False]*m for _ in range(n)]
        
        farmlands = []
        for i in range(n):
            for j in range(m):
                if not visited[i][j] and land[i][j]:
                    end_i, end_j = DFS(i, j, i, j)
                    farmlands.append([i, j, end_i, end_j])
        
        return farmlands

Time Complexity: The time complexity of this approach is O(n * m), where n and m are the dimensions of the 2D grid. The DFS function is called once for each connected component, and each cell is visited only once, leading to a linear time complexity.

Space Complexity: The space complexity of this approach is also O(n * m) since we use a visited array of size n * m, equal to the number of cells in the grid. Additionally, we store the result in a list of lists, which has a maximum size of n * m, as there can be at most n * m distinct groups of cells.

1