NeetCode #581LC-1091MediumGraphs
← Back to All Problems#581 · #1091 · Shortest Path in Binary Matrix(二进制矩阵中的最短路径)
📌 Problem Statement & Constraints
Given an
n x n binary matrix grid, return the length of the shortest clear path from the top-left to the bottom-right, where all cells on the path are 0 and moves are 8-directional. Return -1 if no such path exists. Constraints: 1 <= n <= 100.💡 Core Algorithmic Approaches
- BFS over the grid with 8-directional moves, since every step costs 1.
- The path length counts cells, so the start contributes 1.
- Mark cells visited by setting them to
1when enqueued. - Check the start and end cells for blockage first.
💻 Benchmark Python3 Implementation
class Solution:
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
from collections import deque
n = len(grid)
if grid[0][0] or grid[n - 1][n - 1]:
return -1 # start or end blocked
dirs = [(dr, dc) for dr in (-1, 0, 1) for dc in (-1, 0, 1) if dr or dc]
q = deque([(0, 0, 1)]) # (r, c, path length so far)
grid[0][0] = 1
while q:
r, c, d = q.popleft()
if r == n - 1 and c == n - 1:
return d
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
grid[nr][nc] = 1 # mark when enqueuing
q.append((nr, nc, d + 1))
return -1⚡ 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
- Using 4-directional moves: the problem allows 8.
- Forgetting that the path length counts cells: the start contributes 1, not 0.
- Marking visited when dequeuing: the queue would be bloated with duplicates.
- Not checking the endpoints first: a blocked start or end must return -1 immediately.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.