1162. As Far from Land as Possible - Explanation

1. Brute Force (BFS)

Intuition

For each water cell, we want to find the distance to the nearest land cell. The simplest approach is to run a separate BFS from each water cell, expanding outward until we hit land. We track the maximum of all these minimum distances. This gives the correct answer but is slow because we repeat similar work for each water cell.

Algorithm

For each water cell (value 0) in the grid, run a BFS to find the nearest land cell.
The BFS expands level by level, incrementing the distance at each level.
When the BFS reaches a land cell, return that distance.
Track the maximum distance found across all water cells.
If no water cells exist or no land cells exist, return -1.

class Solution:
    def maxDistance(self, grid: list[list[int]]) -> int:
        N = len(grid)
        direct = [[0, 1], [0, -1], [1, 0], [-1, 0]]

        def bfs(row, col):
            q = deque([(row, col)])
            visit = [[False] * N for _ in range(N)]
            dist, visit[row][col] = 0, True

            while q:
                dist += 1
                for _ in range(len(q)):
                    r, c = q.popleft()
                    for dx, dy in direct:
                        newR, newC = r + dx, c + dy
                        if min(newR, newC) < 0 or max(newR, newC) >= N or visit[newR][newC]:
                            continue
                        if grid[newR][newC] == 1:
                            return dist
                        visit[newR][newC] = True
                        q.append((newR, newC))
            return -1

        res = -1
        for r in range(N):
            for c in range(N):
                if grid[r][c] == 0:
                    res = max(res, bfs(r, c))
                    if res == -1:
                        return res

        return res

Time & Space Complexity

Time complexity: $O(n ^ 4)$
Space complexity: $O(n ^ 2)$

2. Multi Source BFS (Overwriting Input)

Intuition

Instead of searching from each water cell, we can flip the problem: start from all land cells simultaneously and expand outward. This multi-source BFS finds the shortest distance from any land cell to each water cell in a single traversal. The last water cell we reach has the maximum distance. We use the grid itself to store distances, avoiding extra space.

Algorithm

Add all land cells (value 1) to the queue as starting points.
Process the queue level by level. For each cell, check its unvisited water neighbors.
Mark each water neighbor with its distance from land (current cell's value + 1) and add it to the queue.
The value in the last processed cell is the maximum distance.
Return max distance minus 1 (since land starts at 1), or -1 if there's only land or only water.

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        N = len(grid)
        q = deque()

        for r in range(N):
            for c in range(N):
                if grid[r][c]:
                    q.append([r, c])

        res = -1
        direct = [[0, 1], [1, 0], [0, -1], [-1, 0]]

        while q:
            r, c = q.popleft()
            res = grid[r][c]

            for dr, dc in direct:
                newR, newC = r + dr, c + dc
                if min(newR, newC) >= 0 and max(newR, newC) < N and grid[newR][newC] == 0:
                    q.append([newR, newC])
                    grid[newR][newC] = grid[r][c] + 1

        return res - 1 if res > 1 else -1

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

3. Multi Source BFS

Intuition

This is similar to the previous approach but uses a separate visited array instead of modifying the input grid. We still start BFS from all land cells at once and expand outward. The number of BFS levels we complete before the queue empties tells us the maximum distance from any water cell to its nearest land.

Algorithm

Create a visited array and a queue. Mark all land cells as visited and add them to the queue.
Track the number of BFS levels processed (starting at 0).
Process the queue level by level. For each cell, add unvisited neighbors to the queue and mark them visited.
Increment the level counter after each complete level.
Return level - 1 as the answer, or -1 if there's only land or only water.

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        N = len(grid)
        direct = [0, 1, 0, -1, 0]
        visit = [[False] * N for _ in range(N)]
        q = deque()

        for r in range(N):
            for c in range(N):
                if grid[r][c] == 1:
                    visit[r][c] = True
                    q.append((r, c))

        res = 0
        while q:
            res += 1
            for _ in range(len(q)):
                r, c = q.popleft()
                for d in range(4):
                    newR, newC = r + direct[d], c + direct[d + 1]
                    if 0 <= newR < N and 0 <= newC < N and not visit[newR][newC]:
                        q.append((newR, newC))
                        visit[newR][newC] = True

        return res - 1 if res > 1 else -1

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

4. Dynamic Programming (Overwriting the Input)

Intuition

Distance to the nearest land can propagate from multiple directions. If we make two passes, one from top-left to bottom-right and another from bottom-right to top-left, we cover all four directions. In the first pass, each cell gets the minimum distance considering paths from above and left. In the second pass, we also consider paths from below and right. The maximum value after both passes is our answer.

Algorithm

In the forward pass (top-left to bottom-right), for each water cell, set its value to the minimum of its top and left neighbors plus 1.
In the backward pass (bottom-right to top-left), update each water cell with the minimum of its current value and (bottom or right neighbor + 1).
Track the maximum value seen during the backward pass.
Return max - 1 if valid, otherwise -1.

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        N, INF = len(grid), 10**6

        for r in range(N):
            for c in range(N):
                if grid[r][c] == 1:
                    continue
                grid[r][c] = INF
                if r > 0:
                    grid[r][c] = min(grid[r][c], grid[r - 1][c] + 1)
                if c > 0:
                    grid[r][c] = min(grid[r][c], grid[r][c - 1] + 1)

        res = 0
        for r in range(N - 1, -1, -1):
            for c in range(N - 1, -1, -1):
                if grid[r][c] == 1:
                    continue
                if r < N - 1:
                    grid[r][c] = min(grid[r][c], grid[r + 1][c] + 1)
                if c < N - 1:
                    grid[r][c] = min(grid[r][c], grid[r][c + 1] + 1)
                res = max(res, grid[r][c])

        return res - 1 if res < INF else -1

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$ extra space.

5. Dynamic Programming

Intuition

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.

Algorithm

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.

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

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

Common Pitfalls

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.

# Wrong: doesn't check if there's no water or no land
# BFS from land will never find water, or vice versa

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

# Wrong: starting from water cells
for r in range(N):
    for c in range(N):
        if grid[r][c] == 0:  # Should be == 1
            queue.append((r, c))

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.

# Wrong: land cells marked as 1, so final answer needs adjustment
grid[newR][newC] = grid[r][c] + 1
return res  # Should be res - 1 if land started at 1