# As Far from Land as Possible
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/as-far-from-land-as-possible)
Canonical: https://scaleengineer.com/dsa/problems/as-far-from-land-as-possible
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Matrix
**Companies:** [Wix](https://scaleengineer.com/companies/wix), [UiPath](https://scaleengineer.com/companies/uipath)
---
## 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|`.

**Example 1:**

![](https://assets.glich.co/dsa/as-far-from-land-as-possible/image0.JPG) 

**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:**

![](https://assets.glich.co/dsa/as-far-from-land-as-possible/image1.JPG) 

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

# Approaches
## Brute Force Iteration
This approach iterates through every water cell in the grid. For each water cell, it then calculates the Manhattan distance to every land cell to find the nearest one. The maximum of these nearest distances is the result.
**Time:** O(N^4), where N is the side length of the grid. Let L be the number of land cells and W be the number of water cells. The complexity is O(L * W). In the worst case, L and W can both be on the order of O(N^2), leading to an overall complexity of O(N^4). This is too slow for the given constraints. · **Space:** O(N^2), to store the coordinates of all land and water cells.
**Pros:** Conceptually simple and easy to follow.
**Cons:** Extremely inefficient, leading to a 'Time Limit Exceeded' error on larger grids.
### Explanation
First, we collect the coordinates of all land cells and all water cells into two separate lists. We handle the edge cases where there are no land cells or no water cells, returning -1 as required. We then iterate through each water cell. For each water cell, we initialize its minimum distance to a land cell to infinity. Inside this loop, we have another loop that iterates through all land cells. We calculate the Manhattan distance between the current water cell and the current land cell. We update the minimum distance for the current water cell if the newly calculated distance is smaller. After checking all land cells, we have the shortest distance from the current water cell to any land. We then update our overall maximum distance found so far. After iterating through all water cells, the overall maximum distance is our answer.

```java
class Solution {
    public int maxDistance(int[][] grid) {
        int n = grid.length;
        java.util.List<int[]> landCells = new java.util.ArrayList<>();
        java.util.List<int[]> waterCells = new java.util.ArrayList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    landCells.add(new int[]{i, j});
                } else {
                    waterCells.add(new int[]{i, j});
                }
            }
        }

        if (landCells.isEmpty() || waterCells.isEmpty()) {
            return -1;
        }

        int maxDist = 0;
        for (int[] water : waterCells) {
            int minDist = Integer.MAX_VALUE;
            for (int[] land : landCells) {
                int dist = Math.abs(water[0] - land[0]) + Math.abs(water[1] - land[1]);
                minDist = Math.min(minDist, dist);
            }
            maxDist = Math.max(maxDist, minDist);
        }

        return maxDist;
    }
}
```
### Algorithm
- Create a list `landCells` and a list `waterCells`.
- Iterate through the `grid` from `(0,0)` to `(n-1, n-1)`:
    - If `grid[i][j] == 1`, add `(i, j)` to `landCells`.
    - Else, add `(i, j)` to `waterCells`.
- If `landCells` or `waterCells` is empty, return -1.
- Initialize `maxDist = 0`.
- For each `water` cell in `waterCells`:
    - Initialize `minDist = Integer.MAX_VALUE`.
    - For each `land` cell in `landCells`:
        - Calculate `dist = |water.x - land.x| + |water.y - land.y|`.
        - Update `minDist = min(minDist, dist)`.
    - Update `maxDist = max(maxDist, minDist)`.
- Return `maxDist`.

## Multi-Source Breadth-First Search (BFS)
A much more efficient approach is to rephrase the problem. Instead of finding the nearest land for each water cell, we can find the nearest water cell for each land cell. By starting a single BFS simultaneously from all land cells, we can explore the grid in layers. The distance of the last visited water cell will be the maximum distance we are looking for.
**Time:** O(N^2), where N is the side length of the grid. Each cell is enqueued and dequeued at most once. The initial scan to find land cells also takes O(N^2). · **Space:** O(N^2), for the queue. In the worst-case scenario (e.g., a checkerboard pattern), the queue could hold up to half of the grid's cells.
**Pros:** Optimal time complexity.; Efficiently solves the problem by reversing the perspective.
**Cons:** Modifies the input grid. A copy of the grid or a separate `visited` matrix could be used to avoid this, at the cost of extra space.
### Explanation
This method is known as a Multi-Source BFS. We treat all land cells as the initial sources for our search. First, we iterate through the grid and add the coordinates of all land cells (`1`s) to a queue. These cells are at distance 0 from the nearest land (themselves). We handle the edge cases: if there are no land cells (queue is empty) or no water cells (all cells are land), we return -1. We then start the BFS process. The search proceeds in levels. In each level, we process all the cells currently in the queue. For each cell we dequeue, we explore its four neighbors (up, down, left, right). If a neighbor is a water cell (`0`) and has not been visited yet, we mark it as visited (e.g., by changing its value in the grid to `1`) and add it to the queue for the next level's processing. The distance is tracked by the levels of the BFS. We start with a distance of -1 and increment it for each level we process. The final distance value after the BFS completes is the maximum distance from any water cell to the nearest land. The BFS guarantees that we find the shortest path from any source. Since we start from all land cells, the distance at which we reach a water cell `(r, c)` is its shortest distance to *any* of the land cells. The last cell to be visited is, by definition, the farthest one.

```java
class Solution {
    public int maxDistance(int[][] grid) {
        int n = grid.length;
        java.util.Queue<int[]> queue = new java.util.LinkedList<>();
        
        // Add all land cells to the queue
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                }
            }
        }
        
        // Edge cases: no land or all land
        if (queue.isEmpty() || queue.size() == n * n) {
            return -1;
        }
        
        int distance = -1;
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        
        while (!queue.isEmpty()) {
            distance++;
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                int[] cell = queue.poll();
                int r = cell[0];
                int c = cell[1];
                
                for (int[] dir : directions) {
                    int newR = r + dir[0];
                    int newC = c + dir[1];
                    
                    if (newR >= 0 && newR < n && newC >= 0 && newC < n && grid[newR][newC] == 0) {
                        grid[newR][newC] = 1; // Mark as visited
                        queue.offer(new int[]{newR, newC});
                    }
                }
            }
        }
        
        return distance;
    }
}
```
### Algorithm
- Initialize a queue and add the coordinates of all land cells (`1`) from the grid.
- Check for edge cases: if the queue is empty (no land) or its size is `n*n` (all land), return -1.
- Initialize `distance = -1`.
- While the queue is not empty:
    - Increment `distance`.
    - Get the number of nodes at the current level, `levelSize = queue.size()`.
    - For `i` from `0` to `levelSize - 1`:
        - Dequeue a cell `(r, c)`.
        - For each of its four neighbors `(nr, nc)`:
            - If the neighbor is within bounds and is a water cell (`grid[nr][nc] == 0`):
                - Mark the neighbor as visited by setting `grid[nr][nc] = 1`.
                - Enqueue the neighbor `(nr, nc)`.
- Return `distance`.

# Solutions
### Java

```java
class Solution {
public
  int maxDistance(int[][] grid) {
    int n = grid.length;
    Deque<int[]> q = new ArrayDeque<>();
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 1) {
          q.offer(new int[]{i, j});
        }
      }
    }
    int ans = -1;
    if (q.isEmpty() || q.size() == n * n) {
      return ans;
    }
    int[] dirs = {-1, 0, 1, 0, -1};
    while (!q.isEmpty()) {
      for (int i = q.size(); i > 0; --i) {
        int[] p = q.poll();
        for (int k = 0; k < 4; ++k) {
          int x = p[0] + dirs[k], y = p[1] + dirs[k + 1];
          if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 0) {
            grid[x][y] = 1;
            q.offer(new int[]{x, y});
          }
        }
      }
      ++ans;
    }
    return ans;
  }
}

```

### Python

```python
class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int: n = len(grid) q = deque((i, j) for i in range(n) for j in range(n) if grid[i][j]) ans = - 1 if len(q) in (0, n * n): return ans dirs = (- 1, 0, 1, 0, - 1) while q: for _ in range(len(q)): i, j = q . popleft() for a, b in pairwise(dirs): x, y = i + a, j + b if 0 <= x < n and 0 <= y < n and grid[x][y] == 0: grid[x][y] = 1 q . append((x, y)) ans += 1 return ans

```

### CPP

```cpp
class Solution {
public:
  int maxDistance(vector<vector<int>> &grid) {
    int n = grid.size();
    queue<pair<int, int>> q;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j]) {
          q.emplace(i, j);
        }
      }
    }
    int ans = -1;
    if (q.empty() || q.size() == n * n) {
      return ans;
    }
    int dirs[5] = {-1, 0, 1, 0, -1};
    while (!q.empty()) {
      for (int m = q.size(); m; --m) {
        auto [i, j] = q.front();
        q.pop();
        for (int k = 0; k < 4; ++k) {
          int x = i + dirs[k], y = j + dirs[k + 1];
          if (x >= 0 && x < n && y >= 0 && y < n && !grid[x][y]) {
            grid[x][y] = 1;
            q.emplace(x, y);
          }
        }
      }
      ++ans;
    }
    return ans;
  }
};

```