Introduction

In this blog post, we will explore how to solve the LeetCode problem "200" 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

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. Example 1: Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1 Example 2: Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Output: 3 Constraints: m == grid.length n == grid[i].length 1 <= m, n <= 300 grid[i][j] is '0' or '1'.

Explanation

Here's an efficient solution to count the number of islands in a 2D grid:

• Depth-First Search (DFS): Traverse the grid. When a '1' (land) is found, increment the island count and use DFS to explore all connected land cells, marking them as visited (e.g., changing them to '0') to avoid recounting.

• In-place Modification: Modify the grid directly to mark visited cells, eliminating the need for a separate visited matrix, optimizing space.

• 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 recursion depth of DFS (if the entire grid is land). In practice, the stack depth will often be much smaller.

Code

    class Solution:
    def numIslands(self, grid: list[list[str]]) -> int:
        """
        Counts the number of islands in a 2D grid.

        Args:
            grid: A 2D list of strings representing the grid. '1' represents land, and '0' represents water.

        Returns:
            The number of islands in the grid.
        """

        if not grid:
            return 0

        rows, cols = len(grid), len(grid[0])
        num_islands = 0

        def dfs(row, col):
            """
            Performs Depth-First Search to explore and mark an island.
            """
            if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] == '0':
                return

            # Mark the current cell as visited (water)
            grid[row][col] = '0'

            # Explore adjacent cells
            dfs(row + 1, col)  # Down
            dfs(row - 1, col)  # Up
            dfs(row, col + 1)  # Right
            dfs(row, col - 1)  # Left

        # Iterate through the grid
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == '1':
                    num_islands += 1
                    dfs(i, j)  # Explore the island

        return num_islands