Shortest Path in Binary Matrix

🎯

Shortest Path in Binary Matrix

mediumGRAPHAmazonGoogleFacebook

Imagine navigating a drone through a grid of obstacles where each cell is either blocked or free, and you want to find the shortest safe path from start to finish.

💡 This problem is a classic shortest path search on a grid with obstacles. Beginners often struggle because they try to use DFS or complicated algorithms instead of BFS, which naturally finds shortest paths in unweighted graphs.

📋

Problem Statement

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. A clear path is a path from the top-left cell (0, 0) to the bottom-right cell (n-1, n-1) such that all the visited cells are 0 (free). You can move in 8 directions (horizontal, vertical, diagonal) to adjacent cells. If no such path exists, return -1.

1 ≤ n ≤ 100grid[i][j] is 0 or 1Start and end cells may be blocked

💡

Example

Input"[[0,1],[1,0]]"

Output2

The shortest path is (0,0) → (1,1) diagonally, length 2.

Input"[[0,0,0],[1,1,0],[1,1,0]]"

Output4

One shortest path is (0,0) → (0,1) → (0,2) → (1,2) → (2,2).

Input"[[1,0,0],[1,1,0],[1,1,0]]"

Output-1

Start cell is blocked, no path exists.

• Single cell grid with 0 → output 1
• Single cell grid with 1 → output -1
• Grid where start or end cell is blocked → output -1
• Grid full of zeros → shortest path is minimum steps diagonally

⚠️

Common Mistakes

Using DFS instead of BFS for shortest path

Returns incorrect longer paths or TLE

✅ Use BFS to guarantee shortest path in unweighted graphs

Not marking visited when enqueuing neighbors

Leads to revisiting cells multiple times, causing TLE or infinite loops

✅ Mark cells visited immediately when adding to queue

Ignoring diagonal moves or only using 4 directions

Returns longer path length or no path found when one exists

✅ Include all 8 directions in movement

Not checking if start or end cell is blocked before processing

Unnecessary computation or incorrect results

✅ Return -1 immediately if start or end cell is blocked

Using queue.shift() in JavaScript without considering performance

Slower runtime due to O(n) shift operations

✅ Use a proper queue implementation or maintain indices for O(1) dequeue

🧠

Brute Force (DFS with Backtracking)

💡 This approach tries every possible path recursively to find the shortest one. It is very slow but helps understand the problem deeply and why BFS is better.

Intuition

Try all paths from start to end using DFS, track the path length, and update the minimum length found. Backtrack to explore other paths.

Algorithm

1. Start DFS from (0,0) if it is free.
2. Mark the current cell as visited to avoid cycles.
3. Explore all 8 directions recursively if the next cell is free and not visited.
4. Keep track of the path length and update the minimum when reaching the end.
5. Backtrack by unmarking the current cell before returning.

💡 The recursion and backtracking make it hard to see the shortest path immediately because it explores all paths fully.

</>

Code

from typing import List

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if grid[0][0] != 0 or grid[n-1][n-1] != 0:
            return -1
        self.min_path = float('inf')
        visited = [[False]*n for _ in range(n)]
        directions = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]

        def dfs(r, c, length):
            if r == n-1 and c == n-1:
                self.min_path = min(self.min_path, length)
                return
            if length >= self.min_path:
                return
            visited[r][c] = True
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc] == 0:
                    dfs(nr, nc, length + 1)
            visited[r][c] = False

        dfs(0, 0, 1)
        return self.min_path if self.min_path != float('inf') else -1

# Driver code
if __name__ == '__main__':
    sol = Solution()
    print(sol.shortestPathBinaryMatrix([[0,1],[1,0]]))  # Output: 2

Line Notes

if grid[0][0] != 0 or grid[n-1][n-1] != 0:Check if start or end is blocked early to avoid unnecessary work

self.min_path = float('inf')Initialize minimum path length to infinity to find minimum

visited = [[False]*n for _ in range(n)]Track visited cells to avoid cycles in DFS

if r == n-1 and c == n-1:Base case: reached destination, update minimum path length

if length >= self.min_path:Prune paths longer than current minimum to reduce search

visited[r][c] = TrueMark current cell visited before exploring neighbors

for dr, dc in directions:Explore all 8 possible directions from current cell

visited[r][c] = FalseBacktrack: unmark current cell to allow other paths

import java.util.*;

public class Solution {
    private int minPath = Integer.MAX_VALUE;
    private int n;
    private int[][] directions = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1}};
    private boolean[][] visited;

    public int shortestPathBinaryMatrix(int[][] grid) {
        n = grid.length;
        if(grid[0][0] != 0 || grid[n-1][n-1] != 0) return -1;
        visited = new boolean[n][n];
        dfs(grid, 0, 0, 1);
        return minPath == Integer.MAX_VALUE ? -1 : minPath;
    }

    private void dfs(int[][] grid, int r, int c, int length) {
        if(r == n-1 && c == n-1) {
            minPath = Math.min(minPath, length);
            return;
        }
        if(length >= minPath) return;
        visited[r][c] = true;
        for(int[] d : directions) {
            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) {
                dfs(grid, nr, nc, length + 1);
            }
        }
        visited[r][c] = false;
    }

    // Main method for testing
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.shortestPathBinaryMatrix(new int[][]{{0,1},{1,0}})); // Output: 2
    }
}

Line Notes

if(grid[0][0] != 0 || grid[n-1][n-1] != 0) return -1;Early exit if start or end blocked

visited = new boolean[n][n];Initialize visited matrix to track explored cells

if(r == n-1 && c == n-1)Check if destination reached to update minPath

if(length >= minPath) return;Prune longer paths to optimize search

visited[r][c] = true;Mark current cell visited before recursion

for(int[] d : directions)Iterate over all 8 possible moves

visited[r][c] = false;Backtrack to allow other paths to use this cell

System.out.println(sol.shortestPathBinaryMatrix(...));Test the solution with example input

#include <bits/stdc++.h>
using namespace std;

class Solution {
    int n;
    int minPath = INT_MAX;
    vector<vector<int>> directions = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1}};
    vector<vector<bool>> visited;

    void dfs(vector<vector<int>>& grid, int r, int c, int length) {
        if(r == n-1 && c == n-1) {
            minPath = min(minPath, length);
            return;
        }
        if(length >= minPath) return;
        visited[r][c] = true;
        for(auto &d : directions) {
            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) {
                dfs(grid, nr, nc, length + 1);
            }
        }
        visited[r][c] = false;
    }

public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        n = grid.size();
        if(grid[0][0] != 0 || grid[n-1][n-1] != 0) return -1;
        visited.assign(n, vector<bool>(n, false));
        dfs(grid, 0, 0, 1);
        return minPath == INT_MAX ? -1 : minPath;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> grid = {{0,1},{1,0}};
    cout << sol.shortestPathBinaryMatrix(grid) << "\n"; // Output: 2
    return 0;
}

Line Notes

if(grid[0][0] != 0 || grid[n-1][n-1] != 0) return -1;Check if start or end blocked to avoid useless search

visited.assign(n, vector<bool>(n, false));Initialize visited matrix for DFS

if(r == n-1 && c == n-1)Base case: reached destination, update minPath

if(length >= minPath) return;Prune paths longer than current best

visited[r][c] = true;Mark cell visited before exploring neighbors

for(auto &d : directions)Try all 8 directions from current cell

visited[r][c] = false;Backtrack to allow other paths to use this cell

cout << sol.shortestPathBinaryMatrix(grid)Test the solution with example input

var shortestPathBinaryMatrix = function(grid) {
    const n = grid.length;
    if(grid[0][0] !== 0 || grid[n-1][n-1] !== 0) return -1;
    let minPath = Infinity;
    const visited = Array.from({length: n}, () => Array(n).fill(false));
    const directions = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];

    function dfs(r, c, length) {
        if(r === n-1 && c === n-1) {
            minPath = Math.min(minPath, length);
            return;
        }
        if(length >= minPath) return;
        visited[r][c] = true;
        for(const [dr, dc] of directions) {
            const nr = r + dr, nc = c + dc;
            if(nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] === 0) {
                dfs(nr, nc, length + 1);
            }
        }
        visited[r][c] = false;
    }

    dfs(0, 0, 1);
    return minPath === Infinity ? -1 : minPath;
};

// Test
console.log(shortestPathBinaryMatrix([[0,1],[1,0]])); // Output: 2

Line Notes

if(grid[0][0] !== 0 || grid[n-1][n-1] !== 0) return -1;Quickly reject if start or end blocked

const visited = Array.from({length: n}, () => Array(n).fill(false));Create visited matrix to avoid cycles

if(r === n-1 && c === n-1)Check if destination reached to update minPath

if(length >= minPath) return;Stop exploring longer paths to optimize

visited[r][c] = true;Mark current cell visited before recursion

for(const [dr, dc] of directions)Try all 8 directions from current position

visited[r][c] = false;Backtrack to allow other paths to reuse this cell

console.log(shortestPathBinaryMatrix(...))Run example test to verify correctness

⏱

Complexity

TimeO(8^(n*n))

SpaceO(n*n)

DFS explores all possible paths in worst case, each cell can branch to up to 8 neighbors, leading to exponential complexity.

💡 For n=3, this means up to 8^(9)=134 million paths, which is impractical even for small grids.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and why BFS is needed.

🧠

Breadth-First Search (BFS) - Level Order Traversal

💡 BFS naturally finds the shortest path in an unweighted graph by exploring neighbors level by level, making it ideal for this problem.

Intuition

Start from the top-left cell and explore all reachable neighbors in all 8 directions simultaneously, increasing path length by 1 each level until reaching the bottom-right cell.

Algorithm

1. Check if start or end cell is blocked; if yes, return -1.
2. Initialize a queue and add the start cell with path length 1.
3. While queue is not empty, pop the front cell and explore all 8 neighbors.
4. If a neighbor is valid and free, add it to the queue and mark visited.
5. If the destination is reached, return the current path length.
6. If queue empties without reaching destination, return -1.

💡 BFS explores all nodes at the current distance before moving to nodes at the next distance, guaranteeing shortest path discovery.

</>

Code

from collections import deque
from typing import List

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if grid[0][0] != 0 or grid[n-1][n-1] != 0:
            return -1
        directions = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
        queue = deque([(0, 0, 1)])  # (row, col, path_length)
        visited = [[False]*n for _ in range(n)]
        visited[0][0] = True

        while queue:
            r, c, length = queue.popleft()
            if r == n-1 and c == n-1:
                return length
            for dr, dc in directions:
                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, length + 1))
        return -1

# Driver code
if __name__ == '__main__':
    sol = Solution()
    print(sol.shortestPathBinaryMatrix([[0,1],[1,0]]))  # Output: 2

Line Notes

if grid[0][0] != 0 or grid[n-1][n-1] != 0:Reject if start or end blocked

queue = deque([(0, 0, 1)])Initialize queue with start cell and path length 1

visited = [[False]*n for _ in range(n)]Track visited cells to avoid revisiting

visited[0][0] = TrueMark start cell visited

while queue:Process cells level by level

r, c, length = queue.popleft()Get current cell and path length

if r == n-1 and c == n-1:If destination reached, return path length

visited[nr][nc] = TrueMark neighbor visited when enqueued to prevent duplicates

import java.util.*;

public class Solution {
    private int[][] directions = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1}};

    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if(grid[0][0] != 0 || grid[n-1][n-1] != 0) return -1;
        boolean[][] visited = new boolean[n][n];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0,0,1});
        visited[0][0] = true;

        while(!queue.isEmpty()) {
            int[] curr = queue.poll();
            int r = curr[0], c = curr[1], length = curr[2];
            if(r == n-1 && c == n-1) return length;
            for(int[] d : directions) {
                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, length + 1});
                }
            }
        }
        return -1;
    }

    // Main method for testing
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.shortestPathBinaryMatrix(new int[][]{{0,1},{1,0}})); // Output: 2
    }
}

Line Notes

if(grid[0][0] != 0 || grid[n-1][n-1] != 0) return -1;Early exit if start or end blocked

Queue<int[]> queue = new LinkedList<>();Use queue for BFS traversal

queue.offer(new int[]{0,0,1});Add start cell with path length 1

visited[0][0] = true;Mark start visited

while(!queue.isEmpty())Process nodes level by level

int[] curr = queue.poll();Get current cell and path length

if(r == n-1 && c == n-1) return length;Return path length if destination reached

visited[nr][nc] = true;Mark neighbor visited when enqueued

#include <bits/stdc++.h>
using namespace std;

class Solution {
    vector<vector<int>> directions = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1}};
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        if(grid[0][0] != 0 || grid[n-1][n-1] != 0) return -1;
        vector<vector<bool>> visited(n, vector<bool>(n, false));
        queue<tuple<int,int,int>> q;
        q.emplace(0, 0, 1);
        visited[0][0] = true;

        while(!q.empty()) {
            auto [r, c, length] = q.front(); q.pop();
            if(r == n-1 && c == n-1) return length;
            for(auto &d : directions) {
                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.emplace(nr, nc, length + 1);
                }
            }
        }
        return -1;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> grid = {{0,1},{1,0}};
    cout << sol.shortestPathBinaryMatrix(grid) << "\n"; // Output: 2
    return 0;
}

Line Notes

if(grid[0][0] != 0 || grid[n-1][n-1] != 0) return -1;Reject if start or end blocked

queue<tuple<int,int,int>> q;Queue stores cell coordinates and path length

q.emplace(0, 0, 1);Start BFS from (0,0) with path length 1

visited[0][0] = true;Mark start visited

while(!q.empty())Process cells level by level

auto [r, c, length] = q.front(); q.pop();Get current cell and path length

if(r == n-1 && c == n-1) return length;Return path length if destination reached

visited[nr][nc] = true;Mark neighbor visited when enqueued

var shortestPathBinaryMatrix = function(grid) {
    const n = grid.length;
    if(grid[0][0] !== 0 || grid[n-1][n-1] !== 0) return -1;
    const directions = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];
    const visited = Array.from({length: n}, () => Array(n).fill(false));
    const queue = [[0, 0, 1]]; // row, col, path length
    visited[0][0] = true;

    while(queue.length > 0) {
        const [r, c, length] = queue.shift();
        if(r === n-1 && c === n-1) return length;
        for(const [dr, dc] of directions) {
            const nr = r + dr, nc = c + dc;
            if(nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] === 0) {
                visited[nr][nc] = true;
                queue.push([nr, nc, length + 1]);
            }
        }
    }
    return -1;
};

// Test
console.log(shortestPathBinaryMatrix([[0,1],[1,0]])); // Output: 2

Line Notes

if(grid[0][0] !== 0 || grid[n-1][n-1] !== 0) return -1;Reject if start or end blocked

const queue = [[0, 0, 1]];Initialize queue with start cell and path length

visited[0][0] = true;Mark start visited

while(queue.length > 0)Process cells in BFS order

const [r, c, length] = queue.shift();Dequeue current cell and path length

if(r === n-1 && c === n-1) return length;Return path length if destination reached

visited[nr][nc] = true;Mark neighbor visited when enqueued

queue.push([nr, nc, length + 1]);Enqueue neighbor with incremented path length

⏱

Complexity

TimeO(n^2)

SpaceO(n^2)

Each cell is visited at most once, and each has up to 8 neighbors, so BFS runs in O(n^2) for an n x n grid.

💡 For n=100, BFS explores up to 10,000 cells, which is efficient and feasible.

Interview Verdict: Accepted

This is the standard and optimal approach for shortest path in unweighted grids.

🧠

Bidirectional BFS

💡 Bidirectional BFS runs two simultaneous BFS traversals from start and end, meeting in the middle to reduce search space and improve efficiency.

Intuition

Instead of searching from start to end only, search from both ends simultaneously and stop when the two searches meet.

Algorithm

1. Check if start or end cell is blocked; if yes, return -1.
2. Initialize two queues and two visited sets for start and end.
3. Alternate expanding the smaller queue by one level.
4. If any cell is found in both visited sets, return sum of path lengths.
5. If queues empty without meeting, return -1.

💡 By searching from both ends, we reduce the maximum depth each BFS explores, improving runtime.

</>

Code

from collections import deque
from typing import List

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

        start_queue = deque([(0, 0)])
        end_queue = deque([(n-1, n-1)])
        start_visited = {(0, 0): 1}
        end_visited = {(n-1, n-1): 1}

        def visit(queue, visited, other_visited):
            r, c = queue.popleft()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                    if (nr, nc) in other_visited:
                        return visited[(r, c)] + other_visited[(nr, nc)]
                    if (nr, nc) not in visited:
                        visited[(nr, nc)] = visited[(r, c)] + 1
                        queue.append((nr, nc))
            return None

        while start_queue and end_queue:
            if len(start_queue) <= len(end_queue):
                res = visit(start_queue, start_visited, end_visited)
            else:
                res = visit(end_queue, end_visited, start_visited)
            if res is not None:
                return res
        return -1

# Driver code
if __name__ == '__main__':
    sol = Solution()
    print(sol.shortestPathBinaryMatrix([[0,1],[1,0]]))  # Output: 2

Line Notes

if grid[0][0] != 0 or grid[n-1][n-1] != 0:Reject if start or end blocked

start_queue = deque([(0, 0)])Initialize BFS queue from start

end_queue = deque([(n-1, n-1)])Initialize BFS queue from end

start_visited = {(0, 0): 1}Track distances from start

end_visited = {(n-1, n-1): 1}Track distances from end

def visit(queue, visited, other_visited):Expand one level from one side

if (nr, nc) in other_visited:If node visited from other side, paths meet

visited[(nr, nc)] = visited[(r, c)] + 1Record distance for new node

while start_queue and end_queue:Alternate expansions until queues empty or meet

import java.util.*;

public class Solution {
    private int[][] directions = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1}};

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

        Map<Integer, Integer> startVisited = new HashMap<>();
        Map<Integer, Integer> endVisited = new HashMap<>();
        Queue<int[]> startQueue = new LinkedList<>();
        Queue<int[]> endQueue = new LinkedList<>();

        startQueue.offer(new int[]{0,0});
        startVisited.put(0 * n + 0, 1);
        endQueue.offer(new int[]{n-1,n-1});
        endVisited.put((n-1) * n + (n-1), 1);

        while(!startQueue.isEmpty() && !endQueue.isEmpty()) {
            int res = -1;
            if(startQueue.size() <= endQueue.size()) {
                res = visit(grid, startQueue, startVisited, endVisited, n);
            } else {
                res = visit(grid, endQueue, endVisited, startVisited, n);
            }
            if(res != -1) return res;
        }
        return -1;
    }

    private int visit(int[][] grid, Queue<int[]> queue, Map<Integer,Integer> visited, Map<Integer,Integer> otherVisited, int n) {
        int[] cell = queue.poll();
        int r = cell[0], c = cell[1];
        int dist = visited.get(r * n + c);
        for(int[] d : directions) {
            int nr = r + d[0], nc = c + d[1];
            int key = nr * n + nc;
            if(nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0) {
                if(otherVisited.containsKey(key)) {
                    return dist + otherVisited.get(key);
                }
                if(!visited.containsKey(key)) {
                    visited.put(key, dist + 1);
                    queue.offer(new int[]{nr, nc});
                }
            }
        }
        return -1;
    }

    // Main method for testing
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.shortestPathBinaryMatrix(new int[][]{{0,1},{1,0}})); // Output: 2
    }
}

Line Notes

if(grid[0][0] != 0 || grid[n-1][n-1] != 0) return -1;Reject if start or end blocked

Map<Integer, Integer> startVisited = new HashMap<>();Track distances from start using hash map

Map<Integer, Integer> endVisited = new HashMap<>();Track distances from end

startQueue.offer(new int[]{0,0});Initialize start BFS queue

endQueue.offer(new int[]{n-1,n-1});Initialize end BFS queue

if(startQueue.size() <= endQueue.size())Expand smaller queue for efficiency

if(otherVisited.containsKey(key))If node visited from other side, paths meet

visited.put(key, dist + 1);Record distance for new node

#include <bits/stdc++.h>
using namespace std;

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

        unordered_map<int,int> startVisited, endVisited;
        queue<pair<int,int>> startQueue, endQueue;

        startQueue.emplace(0,0);
        startVisited[0] = 1;
        endQueue.emplace(n-1,n-1);
        endVisited[n*n - 1] = 1;

        while(!startQueue.empty() && !endQueue.empty()) {
            int res = -1;
            if(startQueue.size() <= endQueue.size()) {
                res = visit(grid, startQueue, startVisited, endVisited, n);
            } else {
                res = visit(grid, endQueue, endVisited, startVisited, n);
            }
            if(res != -1) return res;
        }
        return -1;
    }

private:
    int visit(vector<vector<int>>& grid, queue<pair<int,int>>& q, unordered_map<int,int>& visited, unordered_map<int,int>& otherVisited, int n) {
        auto [r, c] = q.front(); q.pop();
        int dist = visited[r * n + c];
        for(auto &d : directions) {
            int nr = r + d[0], nc = c + d[1];
            int key = nr * n + nc;
            if(nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0) {
                if(otherVisited.count(key)) {
                    return dist + otherVisited[key];
                }
                if(!visited.count(key)) {
                    visited[key] = dist + 1;
                    q.emplace(nr, nc);
                }
            }
        }
        return -1;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> grid = {{0,1},{1,0}};
    cout << sol.shortestPathBinaryMatrix(grid) << "\n"; // Output: 2
    return 0;
}

Line Notes

if(grid[0][0] != 0 || grid[n-1][n-1] != 0) return -1;Reject if start or end blocked

unordered_map<int,int> startVisited, endVisited;Track distances from both ends

queue<pair<int,int>> startQueue, endQueue;Queues for BFS from start and end

startQueue.emplace(0,0);Initialize start BFS queue

endQueue.emplace(n-1,n-1);Initialize end BFS queue

if(startQueue.size() <= endQueue.size())Expand smaller queue for efficiency

if(otherVisited.count(key))If node visited from other side, paths meet

visited[key] = dist + 1;Record distance for new node

var shortestPathBinaryMatrix = function(grid) {
    const n = grid.length;
    if(grid[0][0] !== 0 || grid[n-1][n-1] !== 0) return -1;
    const directions = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];

    let startQueue = [[0, 0]];
    let endQueue = [[n-1, n-1]];
    let startVisited = new Map([[0, 1]]);
    let endVisited = new Map([[n * n - 1, 1]]);

    function visit(queue, visited, otherVisited) {
        const [r, c] = queue.shift();
        const dist = visited.get(r * n + c);
        for(const [dr, dc] of directions) {
            const nr = r + dr, nc = c + dc;
            const key = nr * n + nc;
            if(nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] === 0) {
                if(otherVisited.has(key)) {
                    return dist + otherVisited.get(key);
                }
                if(!visited.has(key)) {
                    visited.set(key, dist + 1);
                    queue.push([nr, nc]);
                }
            }
        }
        return null;
    }

    while(startQueue.length && endQueue.length) {
        let res = null;
        if(startQueue.length <= endQueue.length) {
            res = visit(startQueue, startVisited, endVisited);
        } else {
            res = visit(endQueue, endVisited, startVisited);
        }
        if(res !== null) return res;
    }
    return -1;
};

// Test
console.log(shortestPathBinaryMatrix([[0,1],[1,0]])); // Output: 2

Line Notes

if(grid[0][0] !== 0 || grid[n-1][n-1] !== 0) return -1;Reject if start or end blocked

let startQueue = [[0, 0]];Initialize BFS queue from start

let endQueue = [[n-1, n-1]];Initialize BFS queue from end

let startVisited = new Map([[0, 1]]);Track distances from start

let endVisited = new Map([[n * n - 1, 1]]);Track distances from end

function visit(queue, visited, otherVisited)Expand one BFS level from one side

if(otherVisited.has(key))If node visited from other side, paths meet

visited.set(key, dist + 1);Record distance for new node

⏱

Complexity

TimeO(n^2)

SpaceO(n^2)

Bidirectional BFS reduces the search space roughly by half, but worst case remains O(n^2) for an n x n grid.

💡 For large grids, this approach can be faster in practice by meeting in the middle sooner.

Interview Verdict: Accepted

This is an optimization over standard BFS, useful for large inputs or interview follow-ups.

📊

All Approaches - One-Glance Tradeoffs

💡 BFS is the recommended approach for 95% of interviews due to correctness and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (DFS with Backtracking)	O(8^(n*n))	O(n*n)	Yes (deep recursion)	Yes	Mention only - never code due to inefficiency
2. BFS (Level Order Traversal)	O(n^2)	O(n^2)	No	Yes (with parent tracking)	Code this approach in interviews
3. Bidirectional BFS	O(n^2) but faster in practice	O(n^2)	No	Yes (more complex)	Mention as optimization if asked

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the BFS approach, and prepare to explain tradeoffs and optimizations.

How to Present

Clarify input size, grid constraints, and movement directions.State brute force DFS approach to show understanding of exhaustive search.Explain why BFS is better for shortest path in unweighted graphs.Describe BFS algorithm and code it carefully.Mention bidirectional BFS as an optimization if time permits.Test code on edge cases and explain complexity.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test & Optimize: 5min. Total ~20min

What the Interviewer Tests

Ability to identify BFS for shortest path, implement it correctly on grids with 8 directions, handle edge cases, and optimize if possible.

Common Follow-ups

• What if movement is only 4 directions? → Adjust directions array accordingly.
• How to optimize space? → Use in-place marking or bitmasks if allowed.

💡 These follow-ups test flexibility in adapting BFS and understanding space-time tradeoffs.

🔍

Pattern Recognition

When to Use

Use this pattern when you need shortest path in a grid or graph with uniform edge weights and obstacles.

Signature Phrases

'shortest clear path''8 directions movement''binary matrix with obstacles'

NOT This Pattern When

Dijkstra’s algorithm for weighted graphs or DP for grid path counting problems

Similar Problems

01 Matrix - shortest distance to nearest zero using BFSWalls and Gates - BFS to find shortest distance to gatesMinimum Knight Moves - shortest path with special moves on grid

Practice

1. Consider the following code snippet for the Keys and Rooms problem:

def canVisitAllRooms(rooms):
    n = len(rooms)
    visited = [false] * n
    count = 0
    def dfs(room):
        nonlocal count
        if visited[room]:
            return
        visited[room] = true
        count += 1
        if count == n:
            return
        for key in rooms[room]:
            dfs(key)
    dfs(0)
    return count == n

rooms = [[1], [2], [3], []]
print(canVisitAllRooms(rooms))

What is the value of count after the DFS call completes?

easy

A. 3

B. 0

C. 1

D. 4

Solution

1. Step 1: Trace DFS calls starting from room 0

   Visit room 0 (count=1), then room 1 (count=2), then room 2 (count=3), then room 3 (count=4).

2. Step 2: Confirm all rooms visited

   Since count equals total rooms (4), DFS stops early and returns true.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   All rooms reachable, count matches number of rooms [OK]

Hint: Count increments once per unique room visited [OK]

Common Mistakes:

• Off-by-one error counting rooms
• Assuming count stops at 3 instead of 4
• Confusing count with length of visited list

2. Consider the following Python code that counts connected components using BFS. What is the value of count returned by countComponents(4, [[0,1],[2,3]])?

easy

A. 1

B. 2

C. 3

D. 4

Solution

1. Step 1: Trace BFS starting from node 0

   Nodes 0 and 1 are connected, so BFS visits both, marking them visited. This forms one component.

2. Step 2: Trace BFS starting from node 2

   Nodes 2 and 3 are connected, BFS visits both, marking them visited. This forms the second component.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two disconnected pairs -> 2 components [OK]

Hint: Count increments once per unvisited node BFS start [OK]

Common Mistakes:

• Counting edges instead of components
• Off-by-one in count increment

3. You are given a matrix representing heights of cells on a grid. Water can flow from a cell to its neighboring cells if the neighbor's height is less than or equal to the current cell's height. Find all cells from which water can flow to both the top-left and bottom-right edges of the grid. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Use dynamic programming to store maximum reachable heights and combine results.

B. Run DFS from every cell to check if it can reach both edges independently.

C. Run BFS or DFS starting from the edges inward, marking reachable cells for each edge, then find their intersection.

D. Apply a greedy approach by always moving to the neighbor with the highest height.

Solution

1. Step 1: Understand flow direction

   Water flows from higher or equal height to lower or equal height neighbors, so starting from edges inward ensures we only visit reachable cells.

2. Step 2: Reverse BFS/DFS from edges

   By running BFS/DFS from the edges inward, we mark all cells that can flow to each ocean, then intersect these sets to find cells that can flow to both.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Starting from edges avoids repeated DFS from every cell [OK]

Hint: Reverse BFS/DFS from edges is optimal [OK]

Common Mistakes:

• Thinking BFS/DFS must start from each cell
• Using greedy approach fails on plateaus

4. Suppose the Keys and Rooms problem is modified so that keys can be reused infinitely (i.e., you can revisit rooms multiple times). Which of the following changes to the algorithm is necessary to correctly determine if all rooms can be visited?

hard

A. Remove the visited array and perform DFS without tracking visited rooms

B. Use BFS with a queue and mark rooms as visited when enqueued to avoid infinite loops

C. Keep the visited array but reset it after each DFS call to allow revisits

D. Use a counter to limit the number of visits per room to prevent infinite recursion

Solution

1. Step 1: Understand infinite reuse of keys means cycles are possible

   Without marking visited before enqueueing, BFS can enqueue the same room multiple times causing inefficiency or infinite loops.

2. Step 2: Use BFS with visited marking on enqueue

   Marking visited when enqueuing prevents multiple enqueues of the same room, ensuring termination and correctness.

3. Step 3: Why other options fail

   Removing visited causes infinite loops; resetting visited loses progress; limiting visits is inefficient and complex.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   BFS with visited marking on enqueue is standard for graphs with cycles [OK]

Hint: Mark visited when enqueuing in BFS to handle cycles [OK]

Common Mistakes:

• Removing visited causes infinite loops
• Resetting visited loses track of progress
• Counting visits is inefficient and unnecessary

5. Suppose the problem is modified so that islands can be connected diagonally as well (8-direction connectivity). Which of the following changes to the DFS approach correctly counts islands under this new rule?

hard

A. Add diagonal neighbors (r+1,c+1), (r+1,c-1), (r-1,c+1), (r-1,c-1) to the DFS calls in addition to the four cardinal directions.

B. Keep the DFS calls unchanged but count diagonally adjacent '1's separately after DFS completes.

C. Use BFS instead of DFS without changing neighbor directions, as BFS handles diagonal connectivity automatically.

D. Modify the grid to mark diagonal neighbors as '1' before running the original DFS.

Solution

1. Step 1: Understand the new connectivity rule

   Islands now connect horizontally, vertically, and diagonally, so DFS must explore all 8 neighbors.

2. Step 2: Modify DFS to include diagonal neighbors

   Add recursive DFS calls for (r+1,c+1), (r+1,c-1), (r-1,c+1), and (r-1,c-1) along with the original four directions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only adding diagonal neighbors to DFS ensures correct island counting with 8-direction connectivity [OK]

Hint: Add diagonal neighbors to DFS for 8-direction connectivity [OK]

Common Mistakes:

• Assuming BFS handles diagonals without code change
• Counting diagonals separately after DFS