As Far from Land as Possible
Medium · Graphs · Explanation and code example
Dynamic Programming
How it works
This approach is identical to the previous one but uses a separate DP array instead of modifying the input. We pad the array with an extra row and column on each side (filled with infinity) to avoid boundary checks. Land cells get distance 0, and water cells accumulate distances from their neighbors across two passes.
Steps
- Create a DP array of size
(n+2) x (n+2), initialized with infinity. - In the forward pass, set land cells to 0. For water cells, take the minimum of top and left neighbors plus 1.
- In the backward pass, update water cells with the minimum of current value and (bottom or right neighbor + 1).
- Track the maximum distance during the backward pass.
- Return the maximum if it's less than infinity, otherwise
-1.
Complexity
- Time complexity:
O(n ^ 2) - Space complexity:
O(n ^ 2)
Things to watch for
Not Handling Edge Cases (All Land or All Water)
The problem requires returning -1 if the grid contains only land cells or only water cells. Forgetting this check leads to incorrect results or infinite loops.
Starting BFS from Water Instead of Land
For multi-source BFS, the sources should be all land cells (value 1), not water cells. Starting from water cells would require running separate BFS from each water cell, which is O(n^4) instead of O(n^2).
Off-by-One Error in Distance Calculation
When using multi-source BFS, land cells start with distance 0 (or 1 in some implementations). A common mistake is mishandling the initial distance, leading to results that are off by one.
Python code example
from typing import List
class Solution:
def maxDistance(self, grid: List[List[int]]) -> int:
N = len(grid)
res, INF = -1, 10**6
dp = [[INF] * (N + 2) for _ in range(N + 2)]
for r in range(1, N + 1):
for c in range(1, N + 1):
if grid[r - 1][c - 1] == 1:
dp[r][c] = 0
else:
dp[r][c] = min(dp[r - 1][c], dp[r][c - 1]) + 1
for r in range(N, 0, -1):
for c in range(N, 0, -1):
if grid[r - 1][c - 1] == 0:
dp[r][c] = min(dp[r][c], min(dp[r + 1][c], dp[r][c + 1]) + 1)
res = max(res, dp[r][c])
return res if res < INF else -1
C++ code example
class Solution {
public:
int maxDistance(vector<vector<int>>& grid) {
int N = grid.size();
int INF = 1000000, res = -1;
vector<vector<int>> dp(N + 2, vector<int>(N + 2, INF));
for (int r = 1; r <= N; r++) {
for (int c = 1; c <= N; c++) {
if (grid[r - 1][c - 1] == 1) {
dp[r][c] = 0;
} else {
dp[r][c] = min(dp[r - 1][c], dp[r][c - 1]) + 1;
}
}
}
for (int r = N; r > 0; r--) {
for (int c = N; c > 0; c--) {
if (grid[r - 1][c - 1] == 0) {
dp[r][c] = min(dp[r][c], min(dp[r + 1][c], dp[r][c + 1]) + 1);
res = max(res, dp[r][c]);
}
}
}
return res < INF ? res : -1;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.