We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Shortest Path in Binary Matrix

Difficulty: Medium

Problem Description

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 are different and they share an edge or a corner).

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

Key Insights

  • The problem requires finding the shortest path in a binary matrix, which can be effectively solved using breadth-first search (BFS).
  • BFS is ideal for unweighted grids, as it explores all possible paths level by level, ensuring the shortest path is found first.
  • Each cell in the matrix can connect to its 8 neighboring cells, offering multiple path options.

Space and Time Complexity

Time Complexity: O(n^2) - In the worst case, each cell in the n x n grid is processed once. Space Complexity: O(n^2) - The BFS queue and visited set can grow to the size of the grid.

Solution

To solve the problem, we will implement a breadth-first search (BFS) algorithm. The BFS will start from the top-left corner of the matrix and explore all possible paths to the bottom-right corner. We will maintain a queue to keep track of the current cell and the length of the path taken to reach there. We will also keep a set to track visited cells to avoid cycles.

  1. Initialize a queue with the starting cell (0, 0) and the path length of 1.
  2. While the queue is not empty, dequeue the front cell and check if it's the destination cell (n-1, n-1). If it is, return the path length.
  3. For each of the 8 possible directions, calculate the new cell coordinates. If the new cell is within bounds, is a 0, and has not been visited, mark it as visited and enqueue it with the incremented path length.
  4. If the queue is exhausted without finding the destination, return -1.

Code Solutions

from collections import deque

def shortestPathBinaryMatrix(grid):
    n = len(grid)
    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        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 = set((0, 0))

    while queue:
        r, c, length = queue.popleft()
        if (r, c) == (n - 1, n - 1):
            return length
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0 and (nr, nc) not in visited:
                visited.add((nr, nc))
                queue.append((nr, nc, length + 1))

    return -1
← Back to All Questions