⚡Flashcard Drill➔
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

  1. This is a multi-source BFS from all land cells simultaneously.
  2. Each BFS layer expands one step of distance into water.
  3. The number of layers completed before the queue empties is the maximum distance.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems