Course4all
Join us on telegram
Home/dsa/Graphs/Shortest Path in Binary Matrix

Shortest Path in Binary Matrix

Master this topic with zero to advance depth.

Shortest Path in Binary Matrix

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.
  • The length of a clear path is the number of visited cells of this path.

Visual Representation

Grid: 0 0 0 1 1 0 1 1 0 Path: (0,0) -> (0,1) -> (1,2) -> (2,2) Length: 4
Medium

Examples

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

Clear path found with 4 units length.

Approach 1

Level II: Intermediate (BFS without In-place Modification)

Intuition

A standard BFS using a visited set instead of modifying the input grid. This is often preferred in production code to avoid side effects.

Thought Process

  1. Check starting and ending cells.
  2. Use a visited set to store (r, c).
  3. Queue stores (r, c, distance).
  4. Standard 8-directional exploration.

Pattern: BFS with Visited Set

⏱ O(N^2) - Same as optimal but with higher constant factor due to hashing.💾 O(N^2) - For the visited set.

Detailed Dry Run

3x3 grid, (0,0) is clear.

  1. Queue: [(0,0,1)], Visited: {(0,0)}
  2. Pop (0,0,1). Neighbors: (0,1), (1,1), (1,0). Add all to Visited and Queue.
  3. Continue until (n-1, n-1) is reached.
java
class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0, 1});
        Set<String> vis = new HashSet<>();
        vis.add("0,0");
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int r = curr[0], c = curr[1], d = curr[2];
            if (r == n - 1 && c == n - 1) return d;
            for (int[] dr : dirs) {
                int nr = r + dr[0], nc = c + dr[1];
                String key = nr + "," + nc;
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0 && !vis.contains(key)) {
                    vis.add(key); q.add(new int[]{nr, nc, d + 1});
                }
            }
        }
        return -1;
    }
}
Approach 2

Level III: Optimal (BFS with In-place Marking)

Intuition

To optimize space and constant time, we can mark visited cells directly in the grid (e.g., set grid[r][c] = 1). BFS finds the shortest path in an unweighted grid.

Thought Process

  1. Early exits for blocked start/end.
  2. Queue for BFS starting at (0, 0, 1).
  3. Mark grid[0][0] = 1.
  4. Explore all 8 neighbors using a predefined directions array.
  5. If neighbor is 0, mark as 1 and queue it.

Pattern: 8-Direction BFS

⏱ O(N^2) - Every cell visited once.💾 O(N^2) - Worst case queue size (perimeter of search).

Detailed Dry Run

2x2 grid [[0,1],[1,0]]

  • (0,0) Start. Mark grid[0][0]=1.
  • Neighbors: (0,1)-X, (1,0)-X, (1,1)-OK.
  • (1,1) reached. Return 2.
java
class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0, 1});
        grid[0][0] = 1;
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            if (curr[0] == n - 1 && curr[1] == n - 1) return curr[2];
            for (int[] d : dirs) {
                int nr = curr[0] + d[0], nc = curr[1] + d[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0) {
                    grid[nr][nc] = 1;
                    q.add(new int[]{nr, nc, curr[2] + 1});
                }
            }
        }
        return -1;
    }
}
← Previous QuestionWord Ladder
Next Question →Alien Dictionary