Shortest Path in Binary Matrix is a grid traversal problem that checks whether you can combine graph thinking with careful boundary handling. You are given an n x n matrix containing only 0s and 1s.
A value of 0 means the cell is open and can be visited.
A value of 1 means the cell is blocked.
You start at the top-left cell (0, 0) and want to reach the bottom-right cell (n-1, n-1). The goal is to find the length of the shortest path from start to end.
Movement is allowed in eight directions: up, down, left, right, and the four diagonals. The path length is measured by the number of cells visited, including both the starting and ending cells.
If there is no valid path, the result should indicate failure, usually by returning -1.
Why this problem is not just grid iteration
At first glance, this looks like a simple grid walk. The twist is that you are not allowed to revisit cells, and you must find the shortest path, not just any path.
That immediately signals a graph shortest-path problem.
Each open cell acts like a node. Each valid move to a neighboring cell is an edge. All edges have equal weight, since moving to any adjacent cell counts as one step.
Once you see this mapping, the right traversal strategy becomes clear.
Want to explore more coding problem solutions? Check out the Find the Index of the First Occurrence in a String and Swapping Nodes in a Linked List.
The key idea behind the solution
Because every move has the same cost, the shortest path can be found using breadth-first search.
Breadth-first search explores all positions at distance 1, then all positions at distance 2, and so on. The first time you reach the destination, you are guaranteed that the path is the shortest possible.
This level-by-level expansion is exactly what BFS is designed for.
How the traversal works conceptually
You begin by checking the start and end cells.
If either the starting cell or the destination cell is blocked, there is no possible path, and you can return -1 immediately.
If the start is open, you place it into a queue along with its distance from the start, which is initially 1.
You then repeatedly remove the front cell from the queue and explore its neighbors.
For each of the eight possible directions, you check:
- Is the new position inside the grid?
- Is the cell open?
- Has it not been visited before?
If all conditions are satisfied, you mark the cell as visited and add it to the queue with the distance increased by one.
This process continues until either the destination is reached or the queue becomes empty.
Why marking visited cells is essential
Without marking visited cells, the traversal could loop indefinitely or revisit the same positions multiple times.
Marking a cell as visited as soon as it is added to the queue ensures that:
- Each cell is processed only once
- The first time you reach a cell is with the shortest possible distance
This is a core BFS property and an important point interviewers often ask about.
Why diagonal movement matters
Allowing diagonal movement increases the branching factor, but it does not change the correctness of BFS.
You simply include all eight direction offsets when exploring neighbors.
The important part is consistency: every valid move increases the path length by exactly one, regardless of direction.
Performance in simple terms
The grid has n² cells.
Each cell is visited at most once, and each visit checks a constant number of neighbors.
This makes the time complexity proportional to the number of cells in the grid.
Space usage is also proportional to the grid size due to the queue and visited tracking.
This is efficient and expected for this class of problems.
Common mistakes candidates make
A frequent mistake is using depth-first search, which can find a path but not necessarily the shortest one.
Another is forgetting to handle diagonal moves, which leads to incorrect answers.
Some candidates also delay marking cells as visited until they are removed from the queue, which can cause duplicate entries and extra work.
Top comments (0)