As Far from Land as Possible — Problem & Solution
As Far from Land as Possible solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
As Far from Land as Possible is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon, Google and Uber interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Matrix, Breadth-First Search
- Asked at: Amazon, Google, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an n x n grid where 0 is water and 1 is land, find the water cell whose Manhattan distance to the nearest land cell is largest, and return that distance.
If the grid is all land or all water, return -1.
Example 1
Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: The centre is two steps from any land.
Example 2
Input: grid = [[1,0,0],[0,0,0],[0,0,0]]
Output: 4
Example 3
Input: grid = [[1,1],[1,1]]
Output: -1
Constraints
1 <= grid.length <= 12grid[i].length == grid.lengthgrid[i][j] is 0 or 1.
Hints for As Far from Land as Possible
Hint 1
Running a BFS from every water cell is wasteful — run one BFS from all land cells at once.
Hint 2
Seed the queue with every land cell at distance 0 and expand outward.
Hint 3
The last distance assigned is the answer; handle the all-land and all-water cases separately.
How to solve As Far from Land as Possible
Multi-source BFS from every land cell at once; the last distance assigned is the maximum distance from any water cell to its nearest land.
Approach
- Seed the queue with all land cells at distance 0.
- Return -1 if the grid is all land or all water.
- BFS outward; track the largest distance assigned.
Why it works
Seeding every source simultaneously makes each cell's BFS distance equal its distance to the nearest source, so one pass computes all nearest-land distances.
Complexity
- Time —
O(n²) - Space —
O(n²)
Pitfalls
- One BFS per water cell is
O(n⁴).
Reference solution
Python
from collections import deque
def maxDistance(grid) -> int:
n = len(grid)
dist = [[-1] * n for _ in range(n)]
queue = deque()
for r in range(n):
for c in range(n):
if grid[r][c] == 1:
dist[r][c] = 0
queue.append((r, c))
if not queue or len(queue) == n * n:
return -1
best = 0
while queue:
r, c = queue.popleft()
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < n and 0 <= nc < n and dist[nr][nc] == -1:
dist[nr][nc] = dist[r][c] + 1
best = max(best, dist[nr][nc])
queue.append((nr, nc))
return bestJava
public static int maxDistance(int[][] grid) {
int n = grid.length;
int[][] dist = new int[n][n];
for (int[] row : dist) Arrays.fill(row, -1);
List<int[]> queue = new ArrayList<>();
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 1) {
dist[r][c] = 0;
queue.add(new int[]{r, c});
}
}
}
if (queue.isEmpty() || queue.size() == n * n) return -1;
int[] dr = {1, -1, 0, 0};
int[] dc = {0, 0, 1, -1};
int head = 0, best = 0;
while (head < queue.size()) {
int[] cell = queue.get(head++);
for (int d = 0; d < 4; d++) {
int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
if (dist[nr][nc] != -1) continue;
dist[nr][nc] = dist[cell[0]][cell[1]] + 1;
best = Math.max(best, dist[nr][nc]);
queue.add(new int[]{nr, nc});
}
}
return best;
}C++
int maxDistance(vector<vector<int>>& grid) {
int n = (int) grid.size();
vector<vector<int>> dist(n, vector<int>(n, -1));
vector<pair<int,int>> queue;
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 1) {
dist[r][c] = 0;
queue.push_back(make_pair(r, c));
}
}
}
if (queue.empty() || (int) queue.size() == n * n) return -1;
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};
size_t head = 0;
int best = 0;
while (head < queue.size()) {
pair<int,int> cell = queue[head++];
for (int d = 0; d < 4; d++) {
int nr = cell.first + dr[d], nc = cell.second + dc[d];
if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
if (dist[nr][nc] != -1) continue;
dist[nr][nc] = dist[cell.first][cell.second] + 1;
best = max(best, dist[nr][nc]);
queue.push_back(make_pair(nr, nc));
}
}
return best;
}JavaScript
var maxDistance = function(grid) {
const n = grid.length;
const dist = [];
for (let r = 0; r < n; r++) {
const row = [];
for (let c = 0; c < n; c++) row.push(-1);
dist.push(row);
}
const queue = [];
for (let r = 0; r < n; r++) {
for (let c = 0; c < n; c++) {
if (grid[r][c] === 1) {
dist[r][c] = 0;
queue.push([r, c]);
}
}
}
if (queue.length === 0 || queue.length === n * n) return -1;
const dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
let head = 0, best = 0;
while (head < queue.length) {
const cell = queue[head++];
for (let d = 0; d < 4; d++) {
const nr = cell[0] + dr[d], nc = cell[1] + dc[d];
if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
if (dist[nr][nc] !== -1) continue;
dist[nr][nc] = dist[cell[0]][cell[1]] + 1;
if (dist[nr][nc] > best) best = dist[nr][nc];
queue.push([nr, nc]);
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming