As Far from Land as Possible — Editorial

Opening the reading…

Intuitionthe nearest-land definition becomes a wave from every shore

For one water cell, the answer is its distance to the nearest land, not its distance to a particular land cell. If you start a search from that water cell, the first land you encounter gives its nearest-land distance, but repeating that search for every water cell wastes work and repeats the same paths.

Reverse the search. Put every land cell into one BFS queue at distance 0 and let all of them expand together. BFS reaches a cell through the shortest number of four-direction moves, and the first wave to reach a water cell must come from its nearest land. Therefore, the furthest water cell is the last water cell reached, or equivalently the one with the largest assigned distance.

All land cells start the same BFS, so distance labels measure distance to the nearest source.

Approachone queue, one visit per cell, and the final layer is the answer

Create a distance grid filled with -1 and enqueue every land cell with distance 0, because all land cells are valid BFS sources and must expand simultaneously rather than one after another.

Return -1 if the queue is empty or if every cell is land, because in the first case no source exists and in the second case no water cell can receive an answer.

Repeatedly remove the front cell and inspect its four orthogonal neighbors, because diagonal movement is not allowed by Manhattan distance on the grid.

Skip a neighbor that is outside the grid or already has a distance, because it is either invalid or has already been reached by an equal-or-shorter BFS path.

Assign an unvisited neighbor distance one greater than the current cell and enqueue it, because the queue processes layers in increasing distance order and this is the first shortest path to that neighbor.

Update the maximum when a water cell is assigned a distance, because the largest such label is the distance of the water cell farthest from every land source.

Return the recorded maximum after the queue is empty, because every reachable cell has then been assigned its nearest-land distance and no later layer can be larger.

Complexitythe grid is traversed by the BFS wave

MEASURE	BOUND	WHY
Time	O(n^2)	Each cell enters the queue at most once, and each removal checks exactly four directions. The constant four does not grow with n, so the total work counts a constant amount per one of the n^2 cells.
Space	O(n^2) extra	The distance grid stores one value for every cell, and the queue can contain a whole frontier; in the worst input shape both are proportional to n^2. The returned distance is a scalar output, so it is not counted as working memory.

Here n is the side length of the n x n grid.

Annotated solutionC++ · multi-source BFS · complete judge-ready implementation

CPPInitialize all land as distance 0, then expand one shortest-path layer at a time.

#include <vector>
#include <queue>
#include <utility>

using namespace std;

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size();
        if (n == 0) return -1;

        vector<vector<int>> dist(n, vector<int>(n, -1));
        queue<pair<int, int>> q;

        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                if (grid[r][c] == 1) {
                    dist[r][c] = 0;
                    q.push({r, c});
                }
            }
        }

        if (q.empty() || static_cast<int>(q.size()) == n * n) {
            return -1;
        }

        int directions[4][2] = {
            {-1, 0}, {1, 0}, {0, -1}, {0, 1}
        };
        int best = 0;

        while (!q.empty()) {
            auto [r, c] = q.front();
            q.pop();

            for (auto& direction : directions) {
                int nr = r + direction[0];
                int nc = c + direction[1];

                if (nr < 0 || nr >= n || nc < 0 || nc >= n) {
                    continue;
                }
                if (dist[nr][nc] != -1) {
                    continue;
                }

                dist[nr][nc] = dist[r][c] + 1;
                best = max(best, dist[nr][nc]);
                q.push({nr, nc});
            }
        }

        return best;
    }
};

The distance grid serves two roles: it records the answer for each cell and marks whether that cell has already entered the BFS. Checking dist[nr][nc] != -1 prevents a cell from being enqueued again. That single guard is what preserves both the shortest-distance guarantee and the linear visit count.