Introduction

In this blog post, we will explore how to solve the LeetCode problem "1162" 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 n x n grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance. If no land or water exists in the grid, return -1. The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|. Example 1: Input: grid = [[1,0,1],[0,0,0],[1,0,1]] Output: 2 Explanation: The cell (1, 1) is as far as possible from all the land with distance 2. Example 2: Input: grid = [[1,0,0],[0,0,0],[0,0,0]] Output: 4 Explanation: The cell (2, 2) is as far as possible from all the land with distance 4. Constraints: n == grid.length n == grid[i].length 1 <= n <= 100 grid[i][j] is 0 or 1

Explanation

Here's the solution to find the water cell farthest from land in a grid, explained and implemented in Python:

• Multi-Source BFS: Treat all land cells as starting points for a Breadth-First Search (BFS). This allows us to simultaneously explore outwards from all land locations.
• Distance Layering: During the BFS, each water cell will be assigned a distance value representing its shortest Manhattan distance to any land cell. We increment the distance for each "layer" of the BFS.

• Maximization: After the BFS, the maximum distance encountered during the traversal represents the farthest water cell.

• Runtime Complexity: O(n^2), where n is the size of the grid.

• Storage Complexity: O(n^2) in the worst case, for the queue and the distance grid.

Code

    from collections import deque

def maxDistance(grid):
    n = len(grid)
    q = deque()
    distance = [[-1] * n for _ in range(n)]
    land_count = 0
    water_count = 0

    for i in range(n):
        for j in range(n):
            if grid[i][j] == 1:
                q.append((i, j))
                distance[i][j] = 0
                land_count += 1
            else:
                water_count += 1

    if land_count == 0 or water_count == 0:
        return -1

    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    max_dist = -1

    while q:
        row, col = q.popleft()

        for dr, dc in directions:
            new_row = row + dr
            new_col = col + dc

            if 0 <= new_row < n and 0 <= new_col < n and distance[new_row][new_col] == -1:
                distance[new_row][new_col] = distance[row][col] + 1
                max_dist = max(max_dist, distance[new_row][new_col])
                q.append((new_row, new_col))

    return max_dist