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

  1. BFS over the grid with 8-directional moves, since every step costs 1.
  2. The path length counts cells, so the start contributes 1.
  3. Mark cells visited by setting them to 1 when enqueued.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems