NeetCode #586LC-1162MediumGraphs
← Back to All Problems#586 · #1162 · As Far from Land as Possible(地图分析)
📌 Problem Statement & Constraints
Given an
n x n grid containing only 0 (water) and 1 (land), return the maximum Manhattan distance from a water cell to its nearest land cell, or -1 if no water or no land exists. Constraints: 1 <= n <= 100.💡 Core Algorithmic Approaches
- This is a multi-source BFS from all land cells simultaneously.
- Each BFS layer expands one step of distance into water.
- The number of layers completed before the queue empties is the maximum distance.
- If the grid is all land or all water, return -1.
💻 Benchmark Python3 Implementation
class Solution:
def maxDistance(self, grid: List[List[int]]) -> int:
from collections import deque
n = len(grid)
q = deque()
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
q.append((i, j)) # every land cell is a source
if not q or len(q) == n * n:
return -1 # all water or all land
dist = -1
while q:
dist += 1 # one more BFS layer
for _ in range(len(q)):
r, c = q.popleft()
for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
grid[nr][nc] = 1
q.append((nr, nc))
return dist⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2): each cell is enqueued at most once.
💾 Space Complexity
O(n^2) for the queue.
⚠️ Interview Pitfalls & Follow-ups
- Running a BFS from each water cell: O(n^4).
- Returning
dist + 1: the counter is incremented before processing each layer, so the final value is correct. - Forgetting the all-land or all-water case: both must return -1.
- Marking water as land when enqueuing: required, otherwise cells are enqueued repeatedly.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.