Is Shortest Path in Binary Matrix easy or hard?

Shortest Path in Binary Matrix is classified as a Medium problem. The difficulty comes from recognizing that the grid represents an unweighted graph and that BFS guarantees the shortest path. Once that pattern is clear, the implementation becomes straightforward.

Shortest Path in Binary Matrix Python/Java solution

Most implementations use BFS with a queue and a list of 8 direction vectors. Python solutions typically use collections.deque for efficient queue operations, while Java solutions use Queue or ArrayDeque. Both versions iterate through neighbors and return the path length when the bottom-right cell is reached.

How to solve Shortest Path in Binary Matrix in O(n²)?

Use Breadth-First Search starting from cell (0,0). Push the starting cell into a queue, then repeatedly pop cells and explore their 8 neighboring positions if they contain 0 and have not been visited. Track the path length while expanding levels. Since each cell is visited once, the total work stays within O(n²).

What is the best approach for Shortest Path in Binary Matrix?

Breadth-First Search (BFS) is the best approach because the grid forms an unweighted graph and BFS always finds the shortest path in such graphs. Starting from the top-left cell, BFS explores neighbors level by level until the bottom-right cell is reached. The algorithm runs in O(n²) time and O(n²) space for an n x n grid.

Is Shortest Path in Binary Matrix asked at Google/Amazon/Meta?

Shortest Path in Binary Matrix is a common interview problem for companies that test graph traversal and grid search patterns. Variants of this problem appear in interviews at companies like Amazon, Google, and Meta because it evaluates BFS fundamentals and matrix traversal logic.

What data structure is used in Shortest Path in Binary Matrix?

The primary data structure is a queue used for Breadth-First Search. The queue stores grid coordinates along with the current path length. Some implementations also use a visited matrix or modify the input grid to mark visited cells.

What is the time complexity of Shortest Path in Binary Matrix?

The optimal BFS solution runs in O(n²) time because each cell in the n x n grid is processed at most once. For every cell, the algorithm checks up to 8 neighbors. The space complexity is also O(n²) due to the queue and visited tracking.

Description Hints 1 Solution Video 12:34

1091. Shortest Path in Binary Matrix

Medium51.8% acceptance15 companies

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.

Example 1:

Input: grid = [[0,1],[1,0]]
Output: 2

Example 2:

Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4

Example 3:

Input: grid = [[1,0,0],[1,1,0],[1,1,0]]
Output: -1

Constraints:

n == grid.length
n == grid[i].length
1 <= n <= 100
grid[i][j] is 0 or 1

Asked at 15 companies

Anduril Meta Yahoo Snapchat Databricks Applied Intuition

Google Amazon Bloomberg Tiktok Apple Airbnb

+3 more

Microsoft Uber Goldman Sachs

Topics

Hints open one at a time

Hint 1

Do a breadth first search to find the shortest path.

12:34

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution