---
description: BFS
---

# As Far from Land as Possible

## Problem

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|`.

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MRLTZvquSgGV3XonOuO%2F-MRLUCiJX7baEMx87F9-%2FScreen%20Shot%202021-01-18%20at%2010.13.31%20AM.png?alt=media\&token=8bf14fc2-960a-456a-98df-da2053cd1a7c)

### Thought Process

*   Question is similar to Rotting Oranges with keeping track of what level we're on


* The farthest 0 (water) is just the deepest level count

## Solution

```
from collections import deque

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        
        hasWater, hasLand = False, False
        q = deque()
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    hasLand = True
                    q.append([i,j])
                elif grid[i][j] == 0:
                    hasWater = True        
                    
        if not hasWater or not hasLand:
            return -1
        
        directions = [[-1,0], [1,0], [0,-1], [0,1]]
        level = 0
        while q:
            levelSize = len(q)
            level+=1
            for _ in range(levelSize):
                coor = q.popleft()
                x, y = coor[0], coor[1]
                for d in directions:
                    newX = x+d[0]
                    newY = y+d[1]
                    
                    if newX < 0 or newX >= len(grid) or newY < 0 or newY >= len(grid[0]):
                        continue
                        
                    if grid[newX][newY] == 0:
                        grid[newX][newY] = 1
                        q.append([newX, newY])
            
                        
        return level-1
    
```

## Time Complexity

* **Time:** O(n\*n) since we're going through the matrix
* **Space:** O(n\*n) because our queue will hold every cell
