Introduction

In this blog post, we will explore how to solve the LeetCode problem "695" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

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 (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water. The area of an island is the number of cells with a value 1 in the island. Return the maximum area of an island in grid. If there is no island, return 0. 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.

Explanation

• Depth-First Search (DFS): Traverse the grid. When a land cell (1) is found, initiate a DFS to explore the connected island.
  • Island Area Calculation: During the DFS, count the number of cells belonging to the island.
  • Maximization: Keep track of the maximum island area encountered so far and update it as needed.

• Runtime Complexity: O(m * n), where m is the number of rows and n is the number of columns in the grid.
• Storage Complexity: O(m * n) in the worst case, due to the recursion stack in DFS (when the entire grid is an island).

Code

    class Solution:
    def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
        """
        Finds the maximum area of an island in a grid.

        Args:
            grid: A 2D list of integers representing the grid.

        Returns:
            The maximum area of an island in the grid.
        """

        def dfs(row: int, col: int) -> int:
            """
            Performs Depth-First Search to explore an island.

            Args:
                row: The row index of the current cell.
                col: The column index of the current cell.

            Returns:
                The area of the explored island.
            """
            if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]) or grid[row][col] == 0:
                return 0

            grid[row][col] = 0  # Mark the cell as visited (water)
            area = 1  # Start with the current cell

            # Explore adjacent cells
            area += dfs(row + 1, col)
            area += dfs(row - 1, col)
            area += dfs(row, col + 1)
            area += dfs(row, col - 1)

            return area

        max_area = 0
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if grid[row][col] == 1:
                    max_area = max(max_area, dfs(row, col))

        return max_area