As Far from Land as Possible

Medium
451.

As Far from Land as Possible

As Far from Land as Possible is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon, Google and Uber interviews.

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 <= 12
  • grid[i].length == grid.length
  • grid[i][j] is 0 or 1.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxDistance = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 12
  • grid[i].length == grid.length
  • grid[i][j] is 0 or 1.

Hints for As Far from Land as Possible

  1. Hint 1

    Running a BFS from every water cell is wasteful — run one BFS from all land cells at once.

  2. Hint 2

    Seed the queue with every land cell at distance 0 and expand outward.

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

  1. Seed the queue with all land cells at distance 0.
  2. Return -1 if the grid is all land or all water.
  3. 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 best

Java

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