Algorithm
Problem Name: 1162. As Far from Land as Possible
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:
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:
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.lengthn == grid[i].length1 <= n <= 100grid[i][j]is0or1
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
private final int[][] DIRS = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
public int maxDistance(int[][] grid) {
Queue < int[]> queue = new LinkedList<>();
int numRows = grid.length;
int numCols = grid[0].length;
for (int i = 0; i < numRows; i++) {
for (int j = 0; j < numCols; j++) {
if (grid[i][j] == 1) {
queue.add(new int[]{i, j});
}
}
}
if (queue.isEmpty() || queue.size() == numRows * numCols) {
return -1;
}
int distance = 0;
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
int[] removed = queue.remove();
for (int[] dir : DIRS) {
int x = removed[0] + dir[0];
int y = removed[1] + dir[1];
if (x < 0 || y < 0 || x >= numRows || y >= numCols || grid[x][y] == 1) {
continue;
}
grid[x][y] = 1;
queue.add(new int[]{x, y});
}
}
distance++;
}
return distance - 1;
}
}
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const maxDistance = function(grid) {
let m = grid.length
let n = m === 0 ? 0 : grid[0].length
let dp = new Array(m + 2)
for (let i = 0; i < m + 2; i++) {
dp[i] = new Array(n + 2).fill(Number.POSITIVE_INFINITY)
}
for (let i = 1; i < = m; i++) {
for (let j = 1; j < = n; j++) {
if (grid[i - 1][j - 1] === 0) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1
} else {
dp[i][j] = 0
}
}
}
let res = Number.NEGATIVE_INFINITY
for (let i = m; i >= 1; i--) {
for (let j = n; j >= 1; j--) {
if (grid[i - 1][j - 1] === 0) {
dp[i][j] = Math.min(dp[i][j], Math.min(dp[i + 1][j], dp[i][j + 1]) + 1)
res = Math.max(res, dp[i][j])
}
}
}
return isFinite(res) ? res : -1
}
Input
Output
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def maxDistance(self, grid: List[List[int]]) -> int:
n = len(grid)
q = [[i, j] for i in range(n) for j in range(n) if grid[i][j]]
d = -1
while q and len(q) != n ** 2:
Q = []
for i, j in q:
for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):
if 0 <= x < n > y >= 0 and not grid[x][y]:
grid[x][y] = 1
Q.append([x, y])
q = Q
d += 1
return d
Input
Output