Limited Time Offer:Up to 25% off Hello Interview Premium

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Low Level Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Tutor

Get Premium

Leetcode 1091. Shortest Path in Binary Matrix

Given an n×n binary grid where 0s are open and 1s are blocked, return the length (number of cells) of the shortest 8-directionally connected path from (0,0) to (n−1,n−1), or -1 if none exists. Core challenge: find the shortest path in a grid with obstacles—typical solution uses BFS over the 8 neighbors (n ≤ 100).

Asked at:

Meta

Amazon

DESCRIPTION

Input:

grid = [[0,0,0],[1,1,0],[0,0,0]]

Output:

Explanation: The shortest path is (0,0) → (0,1) → (0,2) → (1,2) → (2,2), which has length 5 cells

Constraints:

n == grid.length
n == grid[i].length
1 <= n <= 100
grid[i][j] is 0 or 1
grid[0][0] and grid[n-1][n-1] are guaranteed to be 0 in valid test cases

Understanding the Problem

Let's understand what we're being asked to do. We have an n×n binary grid where 0 represents an open cell and 1 represents a blocked cell. We need to find the shortest path from the top-left corner (0,0) to the bottom-right corner (n-1,n-1).

Let's trace through an example with a 3×3 grid:

[[0,0,0],
 [1,1,0],
 [0,0,0]]

Starting at (0,0), we can move to any of the 8 adjacent cells (up, down, left, right, and 4 diagonals). One valid path: (0,0) → (0,1) → (0,2) → (1,2) → (2,2) has length 5 cells.

Important constraint: We can move in 8 directions (not just 4), which means diagonal moves are allowed! This is different from standard grid problems that only allow up/down/left/right.

Edge cases to consider: What if (0,0) or (n-1,n-1) is blocked? (return -1). What if there's no valid path at all? What if n=1 (single cell grid)?

Building Intuition

Since we need the shortest path in an unweighted grid (each step has equal cost), we should explore cells level by level - first all cells reachable in 1 step, then all cells reachable in 2 steps, and so on.

This ensures the first time we reach the destination, we've found the shortest path.

By exploring level by level, we guarantee that when we reach (n-1,n-1), no shorter path exists. Any other path would have been discovered earlier.

This is fundamentally different from exploring as deep as possible first (which might find a long path before discovering a shorter one).

Imagine water spreading from (0,0) outward in all 8 directions. After 1 second, water reaches all cells 1 step away. After 2 seconds, water reaches all cells 2 steps away.

The first moment water touches (n-1,n-1) tells us the shortest distance. We need to track which cells we've already visited (to avoid revisiting) and explore neighbors systematically, always processing closer cells before farther ones.

Common Mistakes

Using DFS instead of BFS - DFS doesn't guarantee the shortest path and may explore very long paths before finding shorter ones

Forgetting to check if start or end cell is blocked - if grid[0][0] or grid[n-1][n-1] is 1, return -1 immediately

Not marking cells as visited - this causes infinite loops as cells get added to the queue repeatedly

Off-by-one errors in boundary checking - ensure 0 <= newRow < n and 0 <= newCol < n when checking neighbors

Returning distance instead of path length - the problem asks for the number of cells in the path, which includes the starting cell (so initialize distance as 1, not 0)

Optimal Solution

Use BFS (Breadth-First Search) to explore the grid level by level. Start from (0,0) and add it to a queue with distance 1. For each cell, explore all 8 neighboring cells that are open and unvisited. Mark visited cells to avoid revisiting. The first time we reach (n-1,n-1), return the distance. If the queue becomes empty without reaching the destination, return -1.

Visualization

from collections import deque
def shortest_path(grid):
    """
    Find shortest 8-directional path from (0,0) to (n-1,n-1) in binary grid.
    Returns path length or -1 if no path exists.
    """
    n = len(grid)
    
    # Check if start or end is blocked
    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1
    
    # BFS initialization
    queue = deque([(0, 0, 1)])  # (row, col, distance)
    visited = [[False] * n for _ in range(n)]
    visited[0][0] = True
    
    # 8 directions: up, down, left, right, and 4 diagonals
    directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
    
    # BFS main loop
    while queue:
        row, col, dist = queue.popleft()
        
        # Check if reached destination
        if row == n - 1 and col == n - 1:
            return dist
        
        # Explore all 8 neighbors
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            
            # Check if neighbor is valid and unvisited
            if 0 <= new_row < n and 0 <= new_col < n and not visited[new_row][new_col] and grid[new_row][new_col] == 0:
                visited[new_row][new_col] = True
                queue.append((new_row, new_col, dist + 1))
    
    # No path found
    return -1

Start BFS to find shortest path in binary grid

0 / 126

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n²) In the worst case, we visit every cell in the n×n grid exactly once. Each cell processes up to 8 neighbors, but this is still O(n²) overall

Space Complexity: O(n²) We need a queue to store cells (up to O(n²) cells in worst case) and a visited set/array to track which cells we've seen (O(n²) space)

What We've Learned

BFS for shortest path in unweighted graphs: When a problem asks for the *shortest* path in a grid or graph where all edges have equal weight (each step costs 1), BFS guarantees the first path found is optimal - unlike DFS which may find longer paths first. BFS explores layer-by-layer, ensuring distance optimality.
8-directional movement pattern: Grid problems may require checking all 8 neighbors (horizontal, vertical, and diagonal) rather than just 4. Store direction vectors as `[(−1,−1), (−1,0), (−1,1), (0,−1), (0,1), (1,−1), (1,0), (1,1)]` and iterate through them systematically to avoid missing valid paths.
In-place visited marking optimization: Instead of maintaining a separate `visited` set (O(n²) space), modify the input grid directly by marking visited cells as 1 (blocked). This reduces space complexity while preventing revisits - only viable when mutating input is acceptable or you can restore it afterward.
Start/end cell validation: A critical edge case is checking if `grid[0][0] == 1` or `grid[n−1][n−1] == 1` before starting BFS - if either endpoint is blocked, immediately return -1. Many solutions fail by queuing invalid starting positions or running unnecessary BFS iterations.
Queue initialization with distance tracking: Initialize BFS queue with `(row, col, distance)` tuples starting at `(0, 0, 1)` - the distance represents path length (number of cells) not steps. This eliminates off-by-one errors and makes the final answer directly retrievable when reaching the target.
Grid traversal pattern generalization: This BFS grid approach extends to any shortest-path problem with obstacles: maze solving, robot navigation, game pathfinding, or network routing where nodes have binary reachability. Recognize the pattern: 2D grid + obstacles + shortest path = BFS with neighbor exploration.

Test Your Understanding

Why is matrix the right data structure for this problem?

matrix provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Mid October, 2025

Meta

Mid-level

Mid September, 2025

Meta

Senior

Early September, 2025

Meta

Mid-level

Get Premium to View All 40+ Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 1091. Shortest Path in Binary Matrix

DESCRIPTION

Understanding the Problem

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact