Domain 2MediumMEDIUM

Shortest Path in Binary Matrix

Find the shortest path from top-left to bottom-right in a binary matrix using Breadth-First Search (8-directional movement), returning cell count or -1 if unreachable.

Domain: medium•Updated: 2026-09-08
#BFS#Queue#O(N^2)#O(N^2)

Problem Breakdown

We are given an n×nn \times n binary matrix where 0 represents a walkable cell and 1 represents an obstacle. The goal is to find the minimum number of cells visited in a path from (0, 0) (top-left) to (n-1, n-1) (bottom-right). Movement is allowed in all 8 directions (horizontal, vertical, diagonal), provided both source and destination are 0. If no such path exists, we return -1.

Key Inputs & Outputs:

  • Input: A list of lists representing the grid. nn ranges from 1 to 100.
  • Output: An integer (path length) or -1. Path length is defined as the count of visited cells, including start and end.

Implicit Constraints & Edge Cases:

  • If grid[0][0] or grid[n-1][n-1] are blocked (1), no path exists immediately -> return -1.
  • Single Cell (N=1N=1): The distance is 1 if the cell itself is walkable. My logic must handle this without infinite loops or incorrect returns.
  • No Path: If we exhaust all reachable cells from start and haven’t reached end, return -1.

Intuition

This problem can be modeled as finding the shortest path in an unweighted graph where each cell (i,j)(i, j) is a node, and edges exist between adjacent 0s (8-connectivity).

Why not DFS? Depth-First Search explores one branch fully before backtracking. While it finds a path quickly if one exists near the end of a deep recursion stack, it does not guarantee finding the shortest path in an unweighted graph without visiting all possible paths first (which is exponential).

Why BFS? Breadth-First Search explores nodes layer-by-layer based on their distance from the source. In an unweighted grid, the first time we encounter the target node during traversal, it must be via a shortest path because every edge has weight 1. This guarantees optimality with polynomial complexity compared to brute-force recursion (O(8N)O(8^N)).

Approach

We will implement BFS using collections.deque for O(1)O(1) pops from both ends.

  1. Validation: Check if the start or end cells are blocked (grid[0][0] == 1). If so, return -1.
  2. Initialization: Create a queue and push (0, 0). Track distance dist = 1 (since we count visited nodes).
  3. Visited Tracking: To avoid cycles and redundant processing, mark cells as visited. Since modifying the input is allowed in this context to save space (O(1)O(1) auxiliary vs O(N2)O(N^2)), I will change walkable neighbors from 0 to -1. This acts both as a “visited” flag and an obstacle marker for future steps.
  4. Traversal: While the queue isn’t empty:
    • Process all nodes currently in the queue (level-order processing).
    • For each node, check its 8 neighbors.
    • If a neighbor is valid (0), mark it visited and add to queue.
    • Optimization: Check if the current popped cell is the target (n-1, n-1). Checking on pop handles N=1N=1 case cleanly without special ‘if’ block for generation vs pop timing issues.
  5. Termination: If queue empties without reaching target, return -1.

Complexity Analysis

  • Time Complexity: O(N2)O(N^2). We visit each cell at most once. There are N×NN \times N cells total. Each cell has a constant number of neighbors (8). Thus, operations scale linearly with the number of nodes in the graph (V=N2V = N^2, E≈8N2E \approx 8N^2), resulting in quadratic time relative to grid dimension nn.
  • Space Complexity: O(N2)O(N^2). In the worst case (e.g., a spiral path or open area), the queue can store up to all cells. If we modify the input grid, auxiliary space is dominated by the Queue structure itself (O(V)O(V)).

Solution

from collections import deque

def shortestPathBinaryMatrix(grid):
    n = len(grid)
    
    # Edge case: Start or End blocked immediately implies no path
    if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
        return -1
    
    q = deque([(0, 0)])
    dist = 1
    
    # Mark start as visited by modifying grid to -1 (obstacle)
    grid[0][0] = -1 
    
    directions = [(-1,-1), (-1,0), (-1,1), 
                  (0,-1),           (0,1), 
                  (1,-1),  (1,0),   (1,1)]
    
    while q:
        # Process all nodes at current distance level
        for _ in range(len(q)):
            r, c = q.popleft()
            
            # Check if we reached the target. 
            # If N=1 and grid[0][0] was start/end, this check happens immediately?
            # We need to check inside loop: if neighbor == target return dist + 1, else continue.
            # Checking on pop handles N=1 case cleanly without special 'if' block for generation vs pop timing issues.
            
            if r == n - 1 and c == n - 1:
                return dist
            
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                
                # Check bounds and if cell is walkable (0)
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                    q.append((nr, nc))
                    grid[nr][nc] = -1 # Mark visited
        
        dist += 1
    
    return -1

# Example usage (commented out for submission):
# print(shortestPathBinaryMatrix([[0,1],[1,0]]))) 

Edge Cases Handled

  • Blocked Start/End: The initial check if grid[0][0] == 1 or ... returns -1 immediately.
  • Single Cell Grid (N=1N=1): If the single cell is 0, queue starts with (0,0). Loop runs once, checks if (0,0) equals target (which it does), returns dist = 1. Correct.
  • No Path: Queue empties without reaching target; loop finishes and function returns -1 at the end.
  • Visited Tracking: By modifying grid[nr][nc] = -1, we prevent re-visiting cells, ensuring O(N2)O(N^2) time complexity rather than exponential backtracking.