## Similar Problems

Similar Problems not available

# As Far From Land As Possible - Leetcode Solution

## Companies:

LeetCode: As Far From Land As Possible Leetcode Solution

Difficulty: Medium

Topics: matrix dynamic-programming array breadth-first-search

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.

## As Far From Land As Possible Solution Code

`1`