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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Shortest Path in Binary Matrix

Number: 1171

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Google, Yahoo, TikTok, Palo Alto Networks, Microsoft, Oracle, Bloomberg, Apple

Problem Description

Given an n x n binary matrix, find the length of the shortest clear path from the top-left cell to the bottom-right cell. A clear path only visits cells with 0 and allows moves in 8 directions (horizontal, vertical, and diagonal connections). If either the start or end cell is blocked or no such path exists, return -1.

Key Insights

  • Use Breadth-First Search (BFS) to guarantee the shortest path in an unweighted grid.
  • Movement is allowed in 8 directions, so each cell has up to 8 neighbors.
  • Check boundary conditions and ensure only unvisited cells with value 0 are processed.
  • Mark cells as visited to avoid reprocessing and infinite loops.
  • If the start or finish is blocked (==1), the answer is immediately -1.

Space and Time Complexity

Time Complexity: O(n^2), as in the worst-case scenario every cell in the grid is visited once. Space Complexity: O(n^2), due to the queue used for BFS and storage for visited cells.

Solution

We approach this problem using BFS, which is ideal for finding the shortest path in a grid when each move has the same cost. Initialize the BFS from the top-left cell if it is 0. For every cell dequeued, explore its 8 neighboring cells. If a neighboring cell is within grid bounds, has a value of 0, and hasn’t been visited, mark it as visited and enqueue it with an incremented path length. Continue this process until the bottom-right cell is reached. If the queue is exhausted without reaching the destination, return -1.

Code Solutions

from collections import deque

def shortestPathBinaryMatrix(grid):
    n = len(grid)
    if grid[0][0] != 0 or grid[n-1][n-1] != 0:
        return -1

    # Directions: 8 directions (vertical, horizontal, diagonal)
    directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
    
    # BFS initialization
    queue = deque([(0, 0, 1)])  # (row, column, path_length)
    grid[0][0] = 1  # mark as visited

    while queue:
        row, col, path_length = queue.popleft()
        if row == n - 1 and col == n - 1:
            return path_length
        
        # Explore all neighbors
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            if 0 <= new_row < n and 0 <= new_col < n and grid[new_row][new_col] == 0:
                queue.append((new_row, new_col, path_length + 1))
                grid[new_row][new_col] = 1  # mark as visited

    return -1

# Example usage:
# grid = [[0,1],[1,0]]
# print(shortestPathBinaryMatrix(grid))
← Back to All Questions