> For the complete documentation index, see [llms.txt](https://joshualbarb.gitbook.io/leetcode-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://joshualbarb.gitbook.io/leetcode-problems/graphs/as-far-from-land-as-possible.md).

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

![](/files/-MRLUCiJX7baEMx87F9-)

### 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