Approach: Multi-source BFS

BFS outward from all land cells at once; the last layer reached is the farthest distance

Complexity: O(n^2) time, O(n^2) space.

Full Solution — all languages

class Solution:
    def maxDistance(self, grid):
        R, C = len(grid), len(grid[0])
        q = [(r, c) for r in range(R) for c in range(C) if grid[r][c] == 1]
        if len(q) == 0 or len(q) == R * C:
            return -1
        dist = 0
        dirs = [(1,0),(-1,0),(0,1),(0,-1)]
        while q:
            nq = []
            for r, c in q:
                for dr, dc in dirs:
                    nr, nc = r+dr, c+dc
                    if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 0:
                        grid[nr][nc] = 1
                        nq.append((nr, nc))
            if nq:
                dist += 1
            q = nq
        return dist

import java.util.*;
class Solution {
    public int maxDistance(int[][] grid) {
        int R = grid.length, C = grid[0].length;
        ArrayDeque<int[]> q = new ArrayDeque<>();
        for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) if (grid[r][c] == 1) q.add(new int[]{r, c});
        if (q.isEmpty() || q.size() == R * C) return -1;
        int dist = 0;
        int[][] dirs = { {
            1,0
        },
        {
            -1,0
        },
        {
            0,1
        },
        {
            0,-1
        }
        };
        while (!q.isEmpty()) {
            ArrayDeque<int[]> nq = new ArrayDeque<>();
            for (int[] cur : q) {
                for (int[] d : dirs) {
                    int nr = cur[0] + d[0], nc = cur[1] + d[1];
                    if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] == 0) {
                        grid[nr][nc] = 1;
                        nq.add(new int[]{nr, nc});
                    }
                }
            }
            if (!nq.isEmpty()) dist++;
            q = nq;
        }
        return dist;
    }
}

#include <bits/stdc++.h> using namespace std;
class Solution {
    public: int maxDistance(vector<vector<int>>& grid) {
        int R = grid.size(), C = grid[0].size();
        vector<pair<int,int>> q;
        for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) if (grid[r][c] == 1) q.push_back({r, c});
        if (q.empty() || (int)q.size() == R * C) return -1;
        int dist = 0;
        int dirs[4][2] = { {
            1,0
        },
        {
            -1,0
        },
        {
            0,1
        },
        {
            0,-1
        }
        };
        while (!q.empty()) {
            vector<pair<int,int>> nq;
            for (auto& cur : q) {
                for (int d = 0; d < 4; d++) {
                    int nr = cur.first + dirs[d][0], nc = cur.second + dirs[d][1];
                    if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] == 0) {
                        grid[nr][nc] = 1;
                        nq.push_back({nr, nc});
                    }
                }
            }
            if (!nq.empty()) dist++;
            q = nq;
        }
        return dist;
    }
};

/**
 * @param {number[][]} grid
 * @return {number}
 */ var maxDistance = function(grid) {
    const R = grid.length, C = grid[0].length;
    let q = [];
    for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) if (grid[r][c] === 1) q.push([r, c]);
    if (q.length === 0 || q.length === R * C) return -1;
    let dist = 0;
    const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
    while (q.length) {
        const nq = [];
        for (const [r, c] of q) {
            for (const [dr, dc] of dirs) {
                const nr = r + dr, nc = c + dc;
                if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] === 0) {
                    grid[nr][nc] = 1;
                    nq.push([nr, nc]);
                }
            }
        }
        if (nq.length) dist++;
        q = nq;
    }
    return dist;
};

As Far from Land as Possible

Example 1

Example 2

Constraints