As Far From Land As Possible - Leetcode Solution

As Far From Land As Possible is a question on LeetCode, which is a platform that provides coding challenges to software developers. The problem statement is quite straightforward:

Given an n x n grid containing only 0s and 1s, where 0 represents water and 1 represents land, find the distance of the nearest land cell from each water cell. The distance between two adjacent land cells is 1 unit. You can assume that there is at least one land cell.

In other words, we need to find the distance of the nearest land cell for each water cell. We can use breadth-first search (BFS) to solve this problem efficiently.

Here's the step-by-step solution to this problem:

Step 1: Create a queue to store the position of all the water cells in the grid.

Step 2: Initialize a visited matrix of the same size as the grid and mark all the land cells as visited.

Step 3: For all the water cells in the queue, perform a BFS operation and find the distance to each land cell. We start from each water cell and visit all its neighbors (up, down, left, right) one by one. If a neighbor cell is a land cell, we mark it as visited, and the distance to it is 1. If a neighbor cell is a water cell and not yet visited, we mark it as visited and add it to the queue along with its distance.

Step 4: Repeat step 3 until the queue becomes empty. At the end of each BFS operation, we update the minimum distance from the water cell to any land cell.

Step 5: Once all the BFS operations are complete, return the maximum distance found in the visited matrix. The result will be the answer to the problem.

Here's the Python code for the same:

from collections import deque
def maxDistance(grid):
    q = deque([])
    visited = [[0 for j in range(len(grid))] for i in range(len(grid))]
    # loop through the grid, starting from every land cells
    for i in range(len(grid)):
        for j in range(len(grid)):
            if grid[i][j] == 1:
                visited[i][j] = 1
                q.append((i,j,0))
    # handle case if there were no land cells
    if not q or len(q) == len(grid)**2:
        return -1
    # perform BFS
    while q:
        i, j, dis = q.popleft()
        # check all neighbors of current cell
        for x, y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if x<0 or y<0 or x>=len(grid) or y>=len(grid):
                continue
            if not visited[x][y]:
                visited[x][y] = 1 
                q.append((x,y,dis+1))
                # update the grid with the distance to the nearest land
                grid[x][y] = min(grid[x][y], dis+1)
    # find the maximum distance
    maxDis = 0
    for i in range(len(grid)):
        for j in range(len(grid)):
            # if there is a water cell
            if grid[i][j] == 0:
                maxDis = max(maxDis, visited[i][j])
    return maxDis

This solution has a time complexity of O(n^2), where n is the size of the grid.

Overall, this is an effective solution to the As Far From Land As Possible problem on LeetCode.

1