Log inSign up
mediumLeetCodeNot Started

Shortest Path in Binary Matrix

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that: - All the visited cells of the path are 0. - All the adjacent cells of the path are 8-directionally connected (i.e., they share an edge or a corner).

The length of a clear path is the number of visited cells of this path.

Example 1:

Input: grid = [[0,1],[1,0]]
Output: 2
Explanation: Path: (0,0) -> (1,1). Total 2 cells visited.

Example 2:

Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4
Explanation: Path: (0,0) -> (0,1) -> (1,2) -> (2,2). Total 4 cells visited.

Example 3:

Input: grid = [[1,0,0],[1,1,0],[1,1,0]]
Output: -1
Explanation: Starting cell (0,0) is blocked with 1, so no path exists.

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Queue data structure operations (enqueue, dequeue)
  • Breadth-First Search (BFS) for shortest paths in unweighted graphs
  • 8-directional neighbor exploration in 2D matrices

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Differentiate BFS vs DFS applicability for shortest path queries in unweighted grids.
  • Implement 8-directional coordinate offsets with strict boundary and obstacle validation.
  • Master visited timing: understand why marking on push avoids catastrophic duplicate queue inflation.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Shortest path in unweighted 2D grid where all steps have identical weight (cost = 1).
  • 8-directional neighbor connectivity (including diagonals).
  • Obstacle grid where non-traversable cells are marked with 1.

Algorithmic Decision Tree:

  • Always select Breadth-First Search (BFS) over DFS for shortest path in unweighted graphs.
  • Mark cells as visited immediately when pushing to the queue to prevent exponential duplicate state growth.

Connected Patterns:

01 MatrixRotting OrangesWord LadderShortest Bridge

1. Exhaustive DFS Backtracking

Intuition

Recursively try every valid unvisited neighbor. Since DFS does not explore level-by-level, it must traverse all non-cyclic paths to verify the minimum.

Algorithm

  1. Step 1: If grid[0][0] == 1 or grid[n-1][n-1] == 1, return -1.
  2. Step 2: Define recursive dfs(r, c, currentLength, visited).
  3. Step 3: Base case: if (r, c) == (n-1, n-1), update minLength = min(minLength, currentLength).
  4. Step 4: For each of the 8 directions, if neighbor is in bounds, == 0, and not visited, mark visited, recurse, and unmark on backtrack.
  5. Step 5: Return minLength if found, else -1.

Exhaustive DFS Backtracking Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [(0,0)=0, (0,1)=0, (0,2)=0, (1,0)=1, (1,1)=1, (1,2)=0, (2,0)=1, (2,1)=1, (2,2)=0]
Current operationSTEP 1 OF 6
Start DFS at root cell (0,0)
Visual state
Values and pointers at this exact step
pointers
S
0
0
0
0
↑ DFS len=1
1
2
Variables at this step
curr
(0,0)
length
1
visited
["(0,0)"]
Check / comparison
grid[0][0] == 0 (open)
Decision / next transition
Explore 8 adjacent neighbor directions.
Why this step matters

Start DFS at root cell (0,0). Valid open cell (val 0). Mark visited, path length = 1.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6 int minLen = 1e9;
7 int n;
8 int directions[8][2] = {
9 {-1, -1}, {-1, 0}, {-1, 1},
10 {0, -1}, {0, 1},
11 {1, -1}, {1, 0}, {1, 1}
12 };
13
14 void dfs(int r, int c, int len, std::vector<std::vector<int>>& grid, std::vector<std::vector<bool>>& visited) {
15 if (len >= minLen) return; // Prune longer paths
16 if (r == n - 1 && c == n - 1) {
17 minLen = std::min(minLen, len);
18 return;
19 }
20
21 visited[r][c] = true;
22 for (auto& dir : directions) {
23 int nr = r + dir[0];
24 int nc = c + dir[1];
25 if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0 && !visited[nr][nc]) {
26 dfs(nr, nc, len + 1, grid, visited);
27 }
28 }
29 visited[r][c] = false; // Backtrack
30 }
31
32public:
33 int shortestPathBinaryMatrix(std::vector<std::vector<int>>& grid) {
34 n = grid.size();
35 if (grid[0][0] != 0 || grid[n - 1][n - 1] != 0) return -1;
36 std::vector<std::vector<bool>> visited(n, std::vector<bool>(n, false));
37 minLen = 1e9;
38 dfs(0, 0, 1, grid, visited);
39 return minLen == 1e9 ? -1 : minLen;
40 }
41};
42
43int main() {
44 Solution solver;
45 std::vector<std::vector<int>> g1 = {{0, 1}, {1, 0}};
46 std::cout << solver.shortestPathBinaryMatrix(g1) << std::endl; // 2
47
48 std::vector<std::vector<int>> g2 = {{0, 0, 0}, {1, 1, 0}, {1, 1, 0}};
49 std::cout << solver.shortestPathBinaryMatrix(g2) << std::endl; // 4
50 return 0;
51}

Time & Space Complexity

  • Time complexity: O(8^(N^2)) — Time complexity for Exhaustive DFS Backtracking.
  • Space complexity: O(N^2) — Space complexity for Exhaustive DFS Backtracking.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Standard BFS with Visited 2D Array

Intuition

In unweighted graphs, BFS expands outwardly like concentric ripples. The first time the destination is popped/visited, that path is proven minimal.

Algorithm

  1. Step 1: Check if grid[0][0] != 0 or grid[n-1][n-1] != 0; return -1 if so.
  2. Step 2: Initialize queue with (0, 0, 1) and create visited[n][n] matrix. Mark visited[0][0] = true.
  3. Step 3: While queue is not empty, pop (r, c, dist).
  4. Step 4: If (r, c) == (n-1, n-1), return dist.
  5. Step 5: For all 8 neighbor offsets, if valid, grid cell == 0, and not visited: mark visited[nr][nc] = true and push (nr, nc, dist + 1) to queue.
  6. Step 6: If queue empties without reaching end, return -1.

Standard BFS with Visited 2D Array Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [(0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)]
Current operationSTEP 1 OF 6
Initialize Queue with [(0,0, dist=1)]
Visual state
Values and pointers at this exact step
pointers
S
0
0
0
0
↑ dist=1
1
2
Variables at this step
queue
["(0,0)"]
dist
1
Check / comparison
grid[0][0] == 0 && grid[2][2] == 0
Decision / next transition
Enqueue start cell with distance 1.
Why this step matters

Initialize Queue with [(0,0, dist=1)]. Mark visited[0][0] = true.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <tuple>
5
6class Solution {
7public:
8 int shortestPathBinaryMatrix(const std::vector<std::vector<int>>& grid) {
9 int n = grid.size();
10 if (grid[0][0] != 0 || grid[n - 1][n - 1] != 0) return -1;
11 if (n == 1) return 1;
12
13 std::vector<std::vector<bool>> visited(n, std::vector<bool>(n, false));
14 std::queue<std::tuple<int, int, int>> q; // (r, c, dist)
15
16 q.push({0, 0, 1});
17 visited[0][0] = true;
18
19 int dirs[8][2] = {
20 {-1, -1}, {-1, 0}, {-1, 1},
21 {0, -1}, {0, 1},
22 {1, -1}, {1, 0}, {1, 1}
23 };
24
25 while (!q.empty()) {
26 auto [r, c, dist] = q.front();
27 q.pop();
28
29 if (r == n - 1 && c == n - 1) return dist;
30
31 for (auto& d : dirs) {
32 int nr = r + d[0];
33 int nc = c + d[1];
34 if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0 && !visited[nr][nc]) {
35 visited[nr][nc] = true;
36 q.push({nr, nc, dist + 1});
37 }
38 }
39 }
40
41 return -1;
42 }
43};
44
45int main() {
46 Solution solver;
47 std::vector<std::vector<int>> g = {{0, 0, 0}, {1, 1, 0}, {1, 1, 0}};
48 std::cout << solver.shortestPathBinaryMatrix(g) << std::endl; // 4
49 return 0;
50}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Standard BFS with Visited 2D Array.
  • Space complexity: O(N^2) — Space complexity for Standard BFS with Visited 2D Array.

3. In-Place Mutated BFS (Zero Extra Visited Matrix)

Intuition

Instead of allocating an N x N boolean matrix, write directly to grid[r][c] = 1 immediately upon pushing each cell to the queue.

Algorithm

  1. Step 1: Check initial barriers: if grid[0][0] != 0 or grid[n-1][n-1] != 0, return -1.
  2. Step 2: If n == 1, return 1.
  3. Step 3: Create BFS queue containing [0, 0, 1] and immediately overwrite grid[0][0] = 1.
  4. Step 4: While queue has elements, pop [r, c, dist].
  5. Step 5: For all 8 offsets (dr, dc): calculate nr = r + dr, nc = c + dc.
  6. Step 6: If nr == n-1 and nc == n-1, return dist + 1 immediately.
  7. Step 7: If in-bounds and grid[nr][nc] == 0, mark grid[nr][nc] = 1 and enqueue [nr, nc, dist + 1].
  8. Step 8: If queue empties without reaching goal, return -1.

In-Place Mutated BFS Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [(0,0):1, (0,1):2, (0,2):3, (1,0):wall, (1,1):wall, (1,2):3, (2,0):wall, (2,1):wall, (2,2):4]
Current operationSTEP 1 OF 6
In-place setup: set grid[0][0] = 1 (marks visited and distance 1)
Visual state
Values and pointers at this exact step
pointers
S
1
0
0
↑ head
1
Variables at this step
queue
["[0,0]"]
grid00
1
Check / comparison
grid[0][0] = 1
Decision / next transition
Enqueue [0,0].
Why this step matters

In-place setup: set grid[0][0] = 1 (marks visited and distance 1). Push [0,0] to queue.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <tuple>
5
6class Solution {
7public:
8 int shortestPathBinaryMatrix(std::vector<std::vector<int>>& grid) {
9 int n = grid.size();
10 if (grid[0][0] != 0 || grid[n - 1][n - 1] != 0) return -1;
11 if (n == 1) return 1;
12
13 // Queue storing (row, col, distance)
14 std::queue<std::tuple<int, int, int>> q;
15 q.push({0, 0, 1});
16 grid[0][0] = 1; // Mark visited in-place
17
18 int dirs[8][2] = {
19 {-1, -1}, {-1, 0}, {-1, 1},
20 {0, -1}, {0, 1},
21 {1, -1}, {1, 0}, {1, 1}
22 };
23
24 while (!q.empty()) {
25 auto [r, c, dist] = q.front();
26 q.pop();
27
28 for (auto& d : dirs) {
29 int nr = r + d[0];
30 int nc = c + d[1];
31
32 if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0) {
33 if (nr == n - 1 && nc == n - 1) {
34 return dist + 1; // Early exit upon reaching target
35 }
36 grid[nr][nc] = 1; // Mark visited
37 q.push({nr, nc, dist + 1});
38 }
39 }
40 }
41
42 return -1;
43 }
44};
45
46int main() {
47 Solution solver;
48 std::vector<std::vector<int>> g1 = {{0, 1}, {1, 0}};
49 std::cout << "Test 1: " << solver.shortestPathBinaryMatrix(g1) << std::endl; // 2
50
51 std::vector<std::vector<int>> g2 = {{0, 0, 0}, {1, 1, 0}, {1, 1, 0}};
52 std::cout << "Test 2: " << solver.shortestPathBinaryMatrix(g2) << std::endl; // 4
53
54 std::vector<std::vector<int>> g3 = {{1, 0, 0}, {1, 1, 0}, {1, 1, 0}};
55 std::cout << "Test 3: " << solver.shortestPathBinaryMatrix(g3) << std::endl; // -1
56 return 0;
57}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for In-Place Mutated BFS (Zero Extra Visited Matrix).
  • Space complexity: O(N^2) — Space complexity for In-Place Mutated BFS (Zero Extra Visited Matrix).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — DFS BacktrackingO(8^(N^2))O(N^2)Recursively explore all non-cyclic paths from start to destination, tracking global minimum.Re-explores identical coordinates across numerous permutations.
2.Better — Standard BFS with Visited TableO(N^2)O(N^2)Level-order traversal using an external boolean visited table.Auxiliary visited matrix memory.
3.Optimal — In-Place Mutated BFSOptimalO(N^2)O(N^2)Mutate grid cells in-place (grid[nr][nc] = 1) directly upon enqueuing to eliminate extra matrix allocation.Queue memory footprint.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Edge Case — Input: `, Expected: ` —
  • Edge Case — Input: `, Expected: ` —
  • Edge Case — Input: `, Expected: ` —

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Emphasize why BFS is chosen over DFS: BFS guarantees finding the shortest path first in an unweighted graph.
  2. Highlight early exit optimization: check if neighbor is target before pushing to queue to save one level of loop iterations.
  3. Mention A* search with Euclidean / Chebyshev distance heuristic as an advanced follow-up for large sparse grids.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Shortest Path in Binary Matrix?

2.Why is the brute force approach suboptimal for large inputs in Shortest Path in Binary Matrix?

3.Which data structure or technique enables the optimal solution for Shortest Path in Binary Matrix?

Back to DSA Sheet