Max Area Of Island Leetcode Problem 695 [Python Solution]

Welcome back!

Today, we're going to tackle the Max Area Of Island problem.

This problem falls under the category of graphs and is considered to have a medium difficulty level.

It's a great exercise to enhance your understanding of depth-first search (DFS) algorithms.

Let's dive into it.

Problem Overview

Problem Statement: You are given an m x n binary matrix grid.

An island is a group of 1's (representing land) connected 4-directionally (horizontally or vertically).

You may assume that all four edges of the grid are surrounded by water.

The area of an island is defined as the number of cells with a value of 1 in the island.

Your task is to return the maximum area of an island in the grid.

If there is no island, you should return 0. To illustrate, consider the following example:

Example 1:

Input:

grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]


Output: 6

Explanation: The answer is not 11, because the island must be connected 4-directionally.

Example 2:

Input:

grid = [[0,0,0,0,0,0,0,0]]


Output: 0

Constraints:
– m == grid.length
– n == grid[i].length
– 1 <= m, n <= 50
– grid[i][j] is either 0 or 1. Now that we understand the problem, let's proceed to solve it efficiently using Python.

Efficient Python Code Solution

def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
    # Get the number of rows and columns in the grid.

ROWS, COLS = len(grid), len(grid[0])

    # Create a set to keep track of visited cells.

visit = set()

    def dfs(r, c):
        # Base cases:
        # If we go out of bounds, return 0. if (
            r < 0
            or r == ROWS
            or c < 0
            or c == COLS
            or grid[r][c] == 0
            or (r, c) in visit
        ):
            return 0

        # Mark the cell as visited.

visit.add((r, c))

        # Recursively explore all four directions.

return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)

    # Initialize the maximum area to 0. area = 0

    # Iterate through the entire grid to find the maximum area.

for r in range(ROWS):
        for c in range(COLS):
            if grid[r][c] == 1:
                area = max(area, dfs(r, c))

    # Return the maximum island area.

return area

In this solution, we define a maxAreaOfIsland function that takes the grid as input and returns the maximum area of an island.

Let's break down the code step by step:

1. We begin by calculating the number of rows and columns in the grid, which will help us in various parts of the algorithm.

2. We create a visit set to keep track of visited cells.

This set will help us avoid revisiting the same cell multiple times and optimize the algorithm.

1. The core of the solution is the dfs function, which performs a depth-first search to calculate the area of an island.

We pass the current row (r) and column (c) as parameters to the function.

1. In the dfs function, we handle several base cases:

   • If we go out of bounds (i.e., r is less than 0, equal to the number of rows, c is less than 0, or equal to the number of columns), we return 0.
   • If the current cell is water (grid value is 0), we return 0.
   • If the current cell has already been visited, we return 0.

2. If none of the base cases apply, we mark the current cell as visited by adding the (r, c) pair to the visit set.

3. We then recursively explore all four directions (up, down, left, and right) by calling the dfs function with the updated coordinates.

We increment the area by 1 for the current cell and add the results from the recursive calls.

1. The main function initializes the area variable to 0, which will store the maximum island area found.

2. We iterate through the entire grid using nested loops.

If we encounter a land cell (grid value is 1), we call the dfs function to calculate the area of the island starting from that cell.

We update the area with the maximum of the current area and the result of the dfs call.

1. Finally, we return the maximum island area, which is stored in the area variable.

Now that we have a clear understanding of the code, let's move on to discussing the time and space complexity of this solution.

Time and Space Complexity

Time Complexity: The time complexity of this solution is determined by the number of cells in the grid, which is m x n, where m is the number of rows and n is the number of columns.

In the worst case, we will visit each cell a constant number of times.

Therefore, the time complexity is O(m x n).

Space Complexity: The space complexity is primarily determined by the memory used by the visit set.

In the worst case, this set may contain every cell in the grid, which would result in a space complexity of O(m x n).

Additionally, the recursive calls in the dfs function will use a call stack, but it's not the dominant factor in space complexity.

This efficient solution should work well within the problem's constraints.

Now that we've successfully implemented the code and analyzed its complexity, you're well-equipped to solve the Max Area Of Island problem on LeetCode.

Reasoning Behind Our Approach

The key idea behind our approach is to use depth-first search (DFS) to explore and calculate the area of each island in the grid efficiently.

By tracking visited cells and recursing in all four directions, we can find the maximum area of an island.

1. We start by defining the dimensions of the grid (number of rows and columns) and a visit set to prevent revisiting cells.

2. The dfs function is the heart of our algorithm.

It's a recursive function that explores an island, keeping track of the visited cells.

1. We handle base cases in the dfs function to avoid going out of bounds, visiting water cells, or revisiting the same cell.

2. For each cell, if it's land, we initiate a DFS to explore the island and calculate its area.

We update the maximum area if a larger island is found.

1. Finally, we return the maximum island area.

Our approach efficiently explores the grid, ensures no island is counted twice, and calculates the area of each island.

This allows us to find and return the maximum area.

Related Interview Questions By Company:

• Best Time To Buy And Sell Stock II LeetCode
• Validate Binary Search Tree LeetCode
• Edit Distance LeetCode

Related Interview Questions By Difficulty:

• Pacific Atlantic Water Flow LeetCode
• Graph Valid Tree LeetCode
• Word Ladder LeetCode

Conclusion

In this blog post, we've tackled the Max Area Of Island problem, a fascinating challenge in the realm of graphs.

We've provided a Python solution that efficiently finds the maximum area of an island in a binary matrix grid.

Our approach leverages depth-first search (DFS) to explore and calculate island areas while avoiding revisiting cells.

We've also discussed the problem statement, provided Python code with explanations, and analyzed the time and space complexity of our solution.

If you found this blog post helpful, please consider liking and subscribing to our our platform to support our content.

Feel free to comment, ask questions, make suggestions, and share this content with others.

Learning and problem-solving are best when shared and discussed!

To further practice and test your skills, don't forget to visit the Max Area of Island problem on LeetCode.

Happy coding!