Max Area of Island | LeetCode 695 | Python

‘Max Area of Island’ is a graph problem. I assume you already have a basic understanding of Graph and DFS algorithms. This problem is almost similar to the number of islands problem. I wrote about it in my blog.

LeetCode 695

Problem Overview (Max Area of Island)

Before getting into the problem, read the description and try to understand the problem.

From a binary matrix (m * n), we have to find the island of the maximum area. In the binary matrix, 0 represents water, and 1 is the island. As per the problem’s description, “An island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.)”.

So, we will search for the largest group of 1’s. That is the ‘area‘ of the island. If there are no islands found, we will return 0.

Solution

This problem’s solution is not only limited to this solution. There are many solutions. But here, let’s see the following approach.

We start to search from the beginning of the matrix. And we will go through each row and column by searching each cell of the grid. Each time, we will check the cell. And if it’s 0 or already visited, skip to the next.

Otherwise, run the DFS algorithm to find how many 1’s are connected vertically and horizontally. And mark each explored cell as visited. In case we don’t have to visit the same cell of the grid more than once and avoid an infinite loop. Keep in mind that in this DFS, all four edges of the graph are stopping points. That is, we are not allowed to go further for water.

So the steps are simple.

Search every cell of the matrix (grid).
If the value of the cell is 0 or already visited, skip to the next.
If the value is 1, run the DFS algorithm. It gives us the area of the island.
If it’s the maximum till now, we will keep it (max_area).
Otherwise, we will continue to search for the next max island.
This process will continue till we visit all the matrix cells.
At the end of the search, we will return the maximum area (max_area).

Let’s see the solution in python.

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        
        max_area = 0
        rows, cols = len(grid), len(grid[0])
        visited = set()

        def dfs(r, c):
            
            if (r < 0) or (c < 0) or (r >= rows) or (c >= cols) or ((r, c) in visited) or (grid[r][c] == 0):
                return 0
            
            visited.add((r, c))
            
            return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)
        
        
        # Looping through all the cells
        for r in range(rows):
            for c in range(cols):
                
                if grid[r][c] == 1 and (r, c) not in visited:
                    
                    res = dfs(r, c)
                    max_area = max(max_area, res)
        
        return max_area

As we explore each row and column, that means every cell of the given matrix. So the time complexity of this solution will be O(m*n).

I hope you got the idea about this problem and solution overview.

Problem Overview (Max Area of Island)

Solution

Related Posts