Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Shortest Path in Binary Matrix

MEDIUMProblemSolveExternal Links

Description

You are given an n × n binary grid where each cell contains either a 0 (empty/open) or a 1 (blocked). Your goal is to find the shortest clear path from the top-left corner (0, 0) to the bottom-right corner (n - 1, n - 1).

A clear path is a sequence of connected cells C_1, C_2, ..., C_k such that:

  • C_1 is at (0, 0) and C_k is at (n - 1, n - 1).
  • Every cell in the path has value 0 (it is open).
  • Consecutive cells in the path are 8-directionally connected — meaning they differ by at most 1 in both their row and column indices. This includes horizontal, vertical, and diagonal neighbors.

The length of the path equals the number of cells visited (counting both the starting and ending cells). Return the length of the shortest such clear path. If no clear path exists, return -1.

3x3 grid showing 8-directional movement from the start cell and a highlighted shortest path from top-left to bottom-right
3x3 grid showing 8-directional movement from the start cell and a highlighted shortest path from top-left to bottom-right

Examples

Example 1

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

Output: 2

Explanation: The grid is 2×2. Cell (0,0) = 0 and cell (1,1) = 0, while cells (0,1) and (1,0) are blocked. The only open path is the diagonal move from (0,0) directly to (1,1). This path contains 2 cells, so the answer is 2.

Example 2

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

Output: 4

Explanation: The open cells form a path along the top row and the right column. One shortest path is (0,0) → (0,1) → (1,2) → (2,2), which visits 4 cells. Other routes through open cells are longer. For instance, (0,0) → (0,1) → (0,2) → (1,2) → (2,2) visits 5 cells. The shortest length is 4.

Example 3

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

Output: -1

Explanation: The starting cell (0,0) has value 1 (blocked). No clear path can begin at a blocked cell, so it is impossible to reach (2,2). The answer is -1.

Constraints

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

Editorial

Brute Force

Intuition

The most direct way to find the shortest path is to simply try every possible route from the top-left corner to the bottom-right corner and keep track of the shortest one.

Imagine you are in a maze and have unlimited time. At each open cell, you look in all 8 directions. Whenever you see an open cell you have not visited yet, you walk there, explore all further routes from that cell, then backtrack and try the next direction. Eventually you will have explored every possible path through the maze, and you pick the one with the fewest steps.

This is a classic Depth-First Search (DFS) with backtracking approach. We recursively explore every open neighbor, and when we reach the destination we record the path length. After all recursive calls complete, the smallest recorded length is our answer.

Step-by-Step Explanation

Let's trace through with grid = [[0,0,0],[1,1,0],[1,1,0]]:

We start at (0,0) with path_length = 1 and min_path = ∞.

Step 1: At (0,0), mark visited. Check 8 neighbors:

  • (0,1) = 0 and unvisited → explore
  • (1,0) = 1, blocked → skip
  • (1,1) = 1, blocked → skip
  • All other neighbors are out of bounds.
  • visited = {(0,0)}

Step 2: Recurse to (0,1), path_length = 2. Mark visited.

  • Check neighbors: (0,0) visited → skip; (0,2) = 0 → explore first; (1,0) = 1 → skip; (1,1) = 1 → skip; (1,2) = 0 → explore later.
  • visited = {(0,0), (0,1)}

Step 3: Recurse to (0,2), path_length = 3. Mark visited.

  • Check neighbors: (0,1) visited; (1,1) = 1; (1,2) = 0 → explore.
  • visited = {(0,0), (0,1), (0,2)}

Step 4: Recurse to (1,2), path_length = 4. Mark visited.

  • Check neighbors: (0,1) visited; (0,2) visited; (1,1) = 1; (2,1) = 1; (2,2) = 0 → explore.
  • visited = {(0,0), (0,1), (0,2), (1,2)}

Step 5: Recurse to (2,2), path_length = 5. This is the destination!

  • Record min_path = min(∞, 5) = 5.
  • Backtrack from (2,2), then from (1,2), then from (0,2).

Step 6: Back at (0,1). Now explore (1,2) directly (not through (0,2)).

  • Recurse to (1,2), path_length = 3. Mark visited.
  • visited = {(0,0), (0,1), (1,2)}

Step 7: From (1,2), explore (0,2) = 0 → recurse. path_length = 4.

  • (0,2) has no unvisited open neighbors leading to (2,2). Dead end. Backtrack.

Step 8: From (1,2), explore (2,2) = 0 → recurse, path_length = 4.

  • Destination reached! min_path = min(5, 4) = 4.
  • Backtrack all the way.

Step 9: All branches from (0,0) explored. No path shorter than 4 found.

  • Return min_path = 4.

The DFS had to explore multiple complete paths and backtrack repeatedly to discover the shortest.

Algorithm

  1. If grid[0][0] == 1 or grid[n-1][n-1] == 1, return -1 (start or end is blocked).
  2. If n == 1, return 1 (single cell, already at destination).
  3. Initialize min_path = ∞ and a visited matrix.
  4. Mark (0, 0) as visited and call DFS with (0, 0) and path_length = 1.
  5. In DFS:
    a. If current cell is (n-1, n-1), update min_path = min(min_path, path_length).
    b. For each of the 8 directions, if the neighbor is in bounds, unvisited, and open:
    • Mark neighbor as visited.
    • Recurse with path_length + 1.
    • Unmark neighbor (backtrack).
  6. Return min_path if it was updated, otherwise return -1.

Code

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return -1;
        if (n == 1) return 1;

        int minPath = INT_MAX;
        vector<vector<bool>> visited(n, vector<bool>(n, false));
        visited[0][0] = true;
        dfs(grid, visited, 0, 0, 1, minPath, n);
        return minPath == INT_MAX ? -1 : minPath;
    }

    void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited,
             int r, int c, int pathLen, int& minPath, int n) {
        if (r == n - 1 && c == n - 1) {
            minPath = min(minPath, pathLen);
            return;
        }
        int dirs[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
        for (auto& d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n
                && !visited[nr][nc] && grid[nr][nc] == 0) {
                visited[nr][nc] = true;
                dfs(grid, visited, nr, nc, pathLen + 1, minPath, n);
                visited[nr][nc] = false;
            }
        }
    }
};
class Solution:
    def shortestPathBinaryMatrix(self, grid: list[list[int]]) -> int:
        n = len(grid)
        if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
            return -1
        if n == 1:
            return 1

        self.min_path = float('inf')
        visited = [[False] * n for _ in range(n)]
        visited[0][0] = True
        self._dfs(grid, visited, 0, 0, 1, n)
        return self.min_path if self.min_path != float('inf') else -1

    def _dfs(self, grid, visited, r, c, path_len, n):
        if r == n - 1 and c == n - 1:
            self.min_path = min(self.min_path, path_len)
            return

        dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc] == 0:
                visited[nr][nc] = True
                self._dfs(grid, visited, nr, nc, path_len + 1, n)
                visited[nr][nc] = False
class Solution {
    private int minPath = Integer.MAX_VALUE;

    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return -1;
        if (n == 1) return 1;

        boolean[][] visited = new boolean[n][n];
        visited[0][0] = true;
        dfs(grid, visited, 0, 0, 1, n);
        return minPath == Integer.MAX_VALUE ? -1 : minPath;
    }

    private void dfs(int[][] grid, boolean[][] visited,
                     int r, int c, int pathLen, int n) {
        if (r == n - 1 && c == n - 1) {
            minPath = Math.min(minPath, pathLen);
            return;
        }
        int[][] dirs = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n
                && !visited[nr][nc] && grid[nr][nc] == 0) {
                visited[nr][nc] = true;
                dfs(grid, visited, nr, nc, pathLen + 1, n);
                visited[nr][nc] = false;
            }
        }
    }
}

Complexity Analysis

Time Complexity: O(8^(n²))

In the worst case, the grid is entirely open (all zeros). From every cell, we may branch into up to 8 directions. With n² cells in total, the DFS tree can have up to 8 branches at each of the n² levels. This exponential blowup makes the approach impractical for even moderate grid sizes. For n = 100, n² = 10000 cells — the number of potential paths is astronomically large.

Space Complexity: O(n²)

The visited matrix uses O(n²) space. The recursion stack can go as deep as n² in the worst case (visiting every cell in a single path), adding another O(n²) for stack frames. Overall: O(n²).

Why This Approach Is Not Efficient

The DFS brute force explores an exponential number of paths. For a 100×100 grid with many open cells, the number of distinct routes from corner to corner is enormous — potentially billions or more. The algorithm wastes massive effort because it does not exploit a fundamental property of shortest-path problems on unweighted graphs:

Key Insight: In an unweighted grid (every step costs 1), the first time any search method reaches a cell via the shortest route, that cell's distance is finalized. DFS does not guarantee this — it may reach cells via long detours first. BFS, by contrast, explores cells in order of increasing distance. So the very first time BFS reaches the bottom-right corner, it has found the shortest path. No backtracking, no repeated work.

With n up to 100, the grid has up to 10000 cells. BFS visits each cell at most once — O(n²) = O(10⁴) operations, well within time limits. DFS with backtracking could take O(8^(n²)) operations, which is computationally infeasible.

Optimal Approach - BFS (Breadth-First Search)

Intuition

When every move in a grid costs the same (1 step), BFS is the natural choice for finding the shortest path. Think of BFS as dropping a stone into a pond at the starting cell — ripples spread outward one level at a time. Level 1 contains just the start. Level 2 contains all cells one step away. Level 3 has cells two steps away, and so on.

Because BFS visits cells in strict order of their distance from the source, the first time it reaches the destination is guaranteed to be via the shortest route. There is no need to explore further or backtrack.

We use a queue. Start by placing (0, 0) in the queue with a path length of 1 (we count the starting cell). Then, in each round, we process all cells at the current distance and add their unvisited open neighbors to the queue for the next round. When we dequeue the destination cell (n-1, n-1), we immediately return the current path length.

Step-by-Step Explanation

Let's trace BFS on grid = [[0,0,0],[1,1,0],[1,1,0]]:

Step 1: Initialize. Place (0,0) in the queue, mark it visited. path_length = 1.

  • Queue: [(0,0)]. Visited: {(0,0)}.

Step 2: Dequeue (0,0). Is it (2,2)? No. Check 8 neighbors.

  • (0,1) = 0, unvisited → add to queue, mark visited.
  • (1,0) = 1 → blocked, skip. (1,1) = 1 → blocked, skip.
  • All other neighbors out of bounds.
  • Queue: [(0,1)]. Visited: {(0,0), (0,1)}.

Step 3: Level 1 complete. Increment path_length to 2. Process level 2.

  • Dequeue (0,1). Is it (2,2)? No. Check neighbors.

Step 4: From (0,1): (0,2) = 0, unvisited → add. (1,2) = 0, unvisited → add.

  • (0,0) already visited. (1,0), (1,1) blocked. Others out of bounds.
  • Queue: [(0,2), (1,2)]. Visited: {(0,0), (0,1), (0,2), (1,2)}.

Step 5: Level 2 complete. Increment path_length to 3. Process level 3.

  • Dequeue (0,2). Is it (2,2)? No. Check neighbors.

Step 6: From (0,2): (0,1) visited, (1,1) blocked, (1,2) already visited. No new cells added.

  • Dequeue (1,2). Is it (2,2)? No. Check neighbors.

Step 7: From (1,2): (2,2) = 0, unvisited → add to queue!

  • (0,1), (0,2) visited. (1,1), (2,1) blocked.
  • Queue: [(2,2)]. Visited: {(0,0),(0,1),(0,2),(1,2),(2,2)}.

Step 8: Level 3 complete. Increment path_length to 4. Process level 4.

  • Dequeue (2,2). Is it (2,2)? YES! Return path_length = 4.

Result: The shortest path has length 4, following (0,0)→(0,1)→(1,2)→(2,2).

BFS Shortest Path — Level-by-Level Exploration — Watch BFS explore the grid level by level. Each level adds exactly 1 to the path length. The first time BFS reaches the destination is the shortest path.

Algorithm

  1. If grid[0][0] == 1 or grid[n-1][n-1] == 1, return -1.
  2. If n == 1, return 1 (start equals destination).
  3. Create a queue and enqueue (0, 0). Initialize a visited matrix, marking (0, 0) as visited. Set path_length = 1.
  4. While the queue is not empty:
    a. Process all cells at the current level (use the current queue size as the level size).
    b. For each dequeued cell (r, c):
    • If (r, c) is (n-1, n-1), return path_length.
    • For each of the 8 directions, if the neighbor (nr, nc) is in bounds, unvisited, and grid[nr][nc] == 0:
      • Mark (nr, nc) as visited.
      • Enqueue (nr, nc).
        c. After processing the entire level, increment path_length.
  5. If the queue empties without reaching (n-1, n-1), return -1.

Code

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return -1;
        if (n == 1) return 1;

        int dirs[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
        queue<pair<int, int>> q;
        q.push({0, 0});
        vector<vector<bool>> visited(n, vector<bool>(n, false));
        visited[0][0] = true;
        int pathLen = 1;

        while (!q.empty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                auto [r, c] = q.front();
                q.pop();
                if (r == n - 1 && c == n - 1) return pathLen;
                for (auto& d : dirs) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < n
                        && !visited[nr][nc] && grid[nr][nc] == 0) {
                        visited[nr][nc] = true;
                        q.push({nr, nc});
                    }
                }
            }
            pathLen++;
        }
        return -1;
    }
};
from collections import deque

class Solution:
    def shortestPathBinaryMatrix(self, grid: list[list[int]]) -> int:
        n = len(grid)
        if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
            return -1
        if n == 1:
            return 1

        dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
        queue = deque([(0, 0)])
        visited = [[False] * n for _ in range(n)]
        visited[0][0] = True
        path_len = 1

        while queue:
            for _ in range(len(queue)):
                r, c = queue.popleft()
                if r == n - 1 and c == n - 1:
                    return path_len
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc] == 0:
                        visited[nr][nc] = True
                        queue.append((nr, nc))
            path_len += 1

        return -1
class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return -1;
        if (n == 1) return 1;

        int[][] dirs = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        boolean[][] visited = new boolean[n][n];
        visited[0][0] = true;
        int pathLen = 1;

        while (!queue.isEmpty()) {
            int sz = queue.size();
            for (int i = 0; i < sz; i++) {
                int[] cell = queue.poll();
                int r = cell[0], c = cell[1];
                if (r == n - 1 && c == n - 1) return pathLen;
                for (int[] d : dirs) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < n
                        && !visited[nr][nc] && grid[nr][nc] == 0) {
                        visited[nr][nc] = true;
                        queue.offer(new int[]{nr, nc});
                    }
                }
            }
            pathLen++;
        }
        return -1;
    }
}

Complexity Analysis

Time Complexity: O(n²)

Each cell in the n×n grid is visited at most once. When we process a cell, we check its 8 neighbors — a constant-time operation per cell. Therefore, the total work is proportional to the number of cells: O(n²). For the maximum constraint of n = 100, this is just 10,000 operations — extremely fast.

Space Complexity: O(n²)

The visited matrix uses O(n²) space. The queue can hold at most O(n²) cells in the worst case (if the entire grid is open and BFS visits every cell). Combined: O(n²).