How do you approach Shortest Path in Binary Matrix?

BFS gives the shortest path in an unweighted grid.

What are common mistakes on Shortest Path in Binary Matrix?

Building the adjacency list in one direction on an undirected graph. Assuming the graph is connected. Most inputs allow several components, and one traversal from node 0 misses the rest. Ignoring self-loops and parallel edges when the constraints allow them.

Sitelet https://gitgood.dev/coding/shortest-path-binary-matrix

gitGood.dev

← Back to problems

Shortest Path in Binary Matrix

MediumAlgorithms

Description

Given an n x n binary matrix grid, return the length of the shortest clear path from the top-left cell to the bottom-right cell, or -1 if none exists.

A clear path visits only cells with value 0 and may move in any of the 8 directions. Path length counts the number of visited cells.

Example 1

Input: grid = [[0,1],[1,0]]

Output: 2

Explanation: Diagonal move from (0,0) to (1,1).

Example 2

Input: grid = [[0,0,0],[1,1,0],[1,1,0]]

Output: 4

Explanation: A 4-cell path reaches the corner.

Constraints

- n == grid.length == grid[i].length - 1 <= n <= 100 - grid[i][j] is 0 or 1

Shortest Path in Binary Matrix: approach, complexity and pitfalls

A medium graphs problem, graded against 7 test cases (5 of them hidden).

The pattern: Graphs

Nodes and edges - traversal, connectivity, cycles, and shortest paths.

Reach for it when you see: Explicit edges, a grid treated as a graph, or dependencies between items.

If you are stuck

Show the 3-step hint ladder

BFS gives the shortest path in an unweighted grid.
Allow all 8 directions and reject blocked or out-of-bounds cells.
Return -1 immediately if the start or end cell is blocked.

The optimal approach

Show the approach: The approach

8-directional BFS. If the start or end is blocked, return -1. Otherwise BFS level by level from (0,0); the level at which you reach the bottom-right corner is the path length.

Time: O(n²). Space: O(n²).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Graphs mistakes

These apply to the pattern as a whole, not just this problem.

Building the adjacency list in one direction on an undirected graph.
Assuming the graph is connected. Most inputs allow several components, and one traversal from node 0 misses the rest.
Ignoring self-loops and parallel edges when the constraints allow them.