1091. Shortest Path in Binary Matrix
Shortest Path in Binary Matrix (LeetCode 1091) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph BFS - Connected Components / Island Counting subpattern.
How to solve Shortest Path in Binary Matrix
Shortest Path in Binary Matrix is a BFS Connected Components problem, part of Graph Traversal Patterns (DFS & BFS). Use BFS for shortest path in unweighted graphs. Solve word ladder, rotting oranges, and matrix problems.
Work towards the solution in these steps:
- Do a breadth first search to find the shortest path.
The reference solution runs in O(n^2) time and O(n) space.
The Shortest Path in Binary Matrix solution and editorial walks through the full approach with reference code.
Problem statement
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
Topics and companies
Topics: Array, Breadth-First Search, Matrix.
Reported in interviews at Amazon, Facebook, Google, Microsoft, Oracle, Snapchat, Uber.
How to practise Shortest Path in Binary Matrix on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n^2) time and O(n) space.
Open Shortest Path in Binary Matrix in the code editor, or read the Shortest Path in Binary Matrix editorial for a worked solution with its approach and complexity analysis.
Where Shortest Path in Binary Matrix sits in the DSA pattern sheet
- Graph Traversal Patterns (DFS & BFS) pattern guide
- Graph BFS - Connected Components / Island Counting subpattern
- The full DSA patterns sheet
Problems related to Shortest Path in Binary Matrix
Other problems that use the same Graph BFS - Connected Components / Island Counting and Graph Traversal Patterns (DFS & BFS) techniques:
- 01 Matrix — Medium, same subpattern
- Rotting Oranges — Medium, same subpattern
- Walls and Gates — Medium, same subpattern
- Word Ladder — Hard, same subpattern
- Accounts Merge — Medium, same pattern
- Alien Dictionary — Hard, same pattern
Shortest Path in Binary Matrix FAQ
What is the LeetCode number of Shortest Path in Binary Matrix?
Shortest Path in Binary Matrix is LeetCode problem 1091, rated Medium.
What pattern is used to solve Shortest Path in Binary Matrix?
Shortest Path in Binary Matrix is a BFS Connected Components problem. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph BFS - Connected Components / Island Counting subpattern.
What is the time complexity of Shortest Path in Binary Matrix?
The reference solution runs in O(n^2) time and O(n) space.
Which companies ask Shortest Path in Binary Matrix?
Shortest Path in Binary Matrix has been reported in interviews at Amazon, Facebook, Google, Microsoft, Oracle, Snapchat, Uber.