Introduction

In this blog post, we will explore how to solve the LeetCode problem "1020" 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, where 0 represents a sea cell and 1 represents a land cell. A move consists of walking from one land cell to another adjacent (4-directionally) land cell or walking off the boundary of the grid. Return the number of land cells in grid for which we cannot walk off the boundary of the grid in any number of moves. Example 1: Input: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]] Output: 3 Explanation: There are three 1s that are enclosed by 0s, and one 1 that is not enclosed because its on the boundary. Example 2: Input: grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]] Output: 0 Explanation: All 1s are either on the boundary or can reach the boundary. Constraints: m == grid.length n == grid[i].length 1 <= m, n <= 500 grid[i][j] is either 0 or 1.

Explanation

Here's the approach:

• Identify Boundary-Connected Land Cells: Use Depth-First Search (DFS) or Breadth-First Search (BFS) starting from land cells on the boundary of the grid to mark all land cells that are connected to the boundary.

• Count Enclosed Land Cells: Iterate through the grid and count the land cells that were not marked as boundary-connected. These are the enclosed land cells.

• 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) due to the visited set in the worst-case scenario (when all cells are land).

Code

    def num_enclaves(grid: list[list[int]]) -> int:
    """
    Given an m x n binary matrix grid, return the number of land cells in grid for which we cannot walk off the boundary of the grid in any number of moves.
    """
    rows, cols = len(grid), len(grid[0])
    visited = set()

    def dfs(row, col):
        if (
            row < 0
            or row >= rows
            or col < 0
            or col >= cols
            or grid[row][col] == 0
            or (row, col) in visited
        ):
            return

        visited.add((row, col))
        dfs(row + 1, col)
        dfs(row - 1, col)
        dfs(row, col + 1)
        dfs(row, col - 1)

    # Iterate along the grid border and start DFS from land cells on the border.
    for row in range(rows):
        if grid[row][0] == 1:
            dfs(row, 0)
        if grid[row][cols - 1] == 1:
            dfs(row, cols - 1)

    for col in range(cols):
        if grid[0][col] == 1:
            dfs(0, col)
        if grid[rows - 1][col] == 1:
            dfs(rows - 1, col)

    # Count the number of land cells that are NOT in the visited set.
    enclave_count = 0
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == 1 and (row, col) not in visited:
                enclave_count += 1

    return enclave_count