##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1162.html

# 1162. As Far from Land as Possible (Medium)

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.

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

If no land or water exists in the grid, return -1.

Example 1:

Input: [[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:

Input: [[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.


Note:

1. 1 <= grid.length == grid[0].length <= 100
2. grid[i][j] is 0 or 1

Companies: Uipath

Similar Questions:

## Solution 1. Brute Force

For each water cell, compute its minimal distance to all lands. The maximum of those minimal distances is the answer.

Note that if dist is already smaller than or equal to the current best answer ans, this cell should be skipped because it can’t yield better result (if (dist <= ans) break;).

// OJ: https://leetcode.com/problems/as-far-from-land-as-possible/
// Time: O(MNL) where grid is of size M*N and L is the count of lands.
// Space: O(L)
class Solution {
public:
int maxDistance(vector<vector<int>>& grid) {
vector<pair<int, int>> lands;
int M = grid.size(), N = grid[0].size(), ans = -1;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (grid[i][j] == 1) lands.emplace_back(i, j);
}
}
if (lands.empty() || M * N == lands.size()) return -1;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (grid[i][j] == 1) continue;
int dist = INT_MAX;
for (auto &p : lands) {
int d = abs(p.first - i) + abs(p.second - j);
dist = min(dist, d);
if (dist <= ans) break;
}
ans = max(ans, dist);
}
}
return ans;
}
};


## Solution 2. BFS

Starts from lands, do BFS layer by layer. The maximum layer number you get is the answer.

// OJ: https://leetcode.com/problems/as-far-from-land-as-possible/
// Time: O(MN)
// Space: O(MN)
class Solution {
public:
int maxDistance(vector<vector<int>>& grid) {
queue<pair<int, int>> q;
int M = grid.size(), N = grid[0].size(), ans = -1;
int dirs[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (grid[i][j] == 1) q.emplace(i, j);
}
}
if (q.empty() || M * N == q.size()) return -1;
while (q.size()) {
int cnt = q.size();
while (cnt--) {
auto p = q.front();
q.pop();
for (auto &dir : dirs) {
int x = p.first + dir[0], y = p.second + dir[1];
if (x < 0 || x >= M || y < 0 || y >= N || grid[x][y]) continue;
q.emplace(x, y);
grid[x][y] = 1;
}
}
++ans;
}
return ans;
}
};

• class Solution {
public int maxDistance(int[][] grid) {
final int WHITE = 0;
final int GRAY = 1;
final int BLACK = 2;
int sideLength = grid.length;
int[][] colors = new int[sideLength][sideLength];
int[][] distances = new int[sideLength][sideLength];
for (int i = 0; i < sideLength; i++) {
for (int j = 0; j < sideLength; j++) {
if (grid[i][j] == 1) {
colors[i][j] = GRAY;
distances[i][j] = 0;
queue.offer(new int[]{i, j});
} else {
colors[i][j] = WHITE;
distances[i][j] = Integer.MAX_VALUE;
}
}
}
if (queue.isEmpty() || queue.size() == sideLength * sideLength)
return -1;
int maxDistance = 0;
int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int row = cell[0], column = cell[1];
int distance = distances[row][column];
maxDistance = Math.max(maxDistance, distance);
for (int[] direction : directions) {
int newRow = row + direction[0], newColumn = column + direction[1];
if (newRow >= 0 && newRow < sideLength && newColumn >= 0 && newColumn < sideLength && colors[newRow][newColumn] == WHITE) {
colors[newRow][newColumn] = GRAY;
distances[newRow][newColumn] = Math.min(distances[newRow][newColumn], distance + 1);
queue.offer(new int[]{newRow, newColumn});
}
}
colors[row][column] = BLACK;
}
return maxDistance;
}
}

############

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;
}
}

• // OJ: https://leetcode.com/problems/as-far-from-land-as-possible/
// Time: O(MNL) where grid is of size M*N and L is the count of lands.
// Space: O(L)
class Solution {
public:
int maxDistance(vector<vector<int>>& grid) {
vector<pair<int, int>> lands;
int M = grid.size(), N = grid[0].size(), ans = -1;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (grid[i][j] == 1) lands.emplace_back(i, j);
}
}
if (lands.empty() || M * N == lands.size()) return -1;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (grid[i][j] == 1) continue;
int dist = INT_MAX;
for (auto &p : lands) {
int d = abs(p.first - i) + abs(p.second - j);
dist = min(dist, d);
if (dist <= ans) break;
}
ans = max(ans, dist);
}
}
return ans;
}
};

• 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] == 1])
ans = -1
valid = False
while q:
ans += 1
for _ in range(len(q)):
i, j = q.popleft()
for a, b in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
x, y = i + a, b + j
if 0 <= x < n and 0 <= y < n and grid[x][y] == 0:
valid = True
grid[x][y] = 1
q.append((x, y))
return ans if valid else -1

############

# 1162. As Far from Land as Possible
# https://leetcode.com/problems/as-far-from-land-as-possible/

class Solution:
def maxDistance(self, grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
q = collections.deque()

for i in range(rows):
for j in range(cols):
if grid[i][j] == 1:
for dx, dy in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
q.append((dx, dy))

steps = 0
while q:
steps += 1
n = len(q)

for _ in range(n):
i, j = q.popleft()
if 0 <= i < rows and 0 <= j < cols and grid[i][j] == 0:
grid[i][j] = steps

for dx, dy in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
q.append((dx, dy))

return steps - 1 if steps != 1 else -1


• func maxDistance(grid [][]int) int {
n := len(grid)
q := [][2]int{}
for i, row := range grid {
for j, v := range row {
if v == 1 {
q = append(q, [2]int{i, j})
}
}
}
ans := -1
if len(q) == 0 || len(q) == n*n {
return ans
}
dirs := [5]int{-1, 0, 1, 0, -1}
for len(q) > 0 {
for i := len(q); i > 0; i-- {
p := q[0]
q = q[1:]
for k := 0; k < 4; k++ {
x, y := p[0]+dirs[k], p[1]+dirs[k+1]
if x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 0 {
grid[x][y] = 1
q = append(q, [2]int{x, y})
}
}
}
ans++
}
return ans
}

• function maxDistance(grid: number[][]): number {
const n = grid.length;
const q: [number, number][] = [];
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] === 1) {
q.push([i, j]);
}
}
}
let ans = -1;
if (q.length === 0 || q.length === n * n) {
return ans;
}
const dirs: number[] = [-1, 0, 1, 0, -1];
while (q.length > 0) {
for (let m = q.length; m; --m) {
const [i, j] = q.shift()!;
for (let k = 0; k < 4; ++k) {
const x = i + dirs[k];
const y = j + dirs[k + 1];
if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] === 0) {
grid[x][y] = 1;
q.push([x, y]);
}
}
}
++ans;
}
return ans;
}