Implement BFS shortest path in grid
Company: Disney
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a function that returns the length of the shortest path in an unweighted 2D grid from the top-left cell (0,
0) to the bottom-right cell (m-1,n-
1). The grid contains '0' for open cells and '1' for walls; movement is allowed only in four directions (up, down, left, right). If either the start or end is blocked, or no path exists, return -1. Provide the algorithm (BFS), explain why it is appropriate, analyze time and space complexity, and discuss edge cases such as single-cell grids, large grids (up to 10^5 cells), and multiple shortest paths. Optionally extend to support diagonal moves and explain the change needed.
Quick Answer: This question evaluates understanding of graph traversal and pathfinding concepts, particularly breadth-first search on unweighted 2D grids, along with algorithmic complexity analysis and edge-case handling in the Coding & Algorithms domain.
Given an `m x n` grid where each cell is `0` (open) or `1` (a wall), return the length of the shortest path from the top-left cell `(0, 0)` to the bottom-right cell `(m-1, n-1)`. Movement is allowed only in the four cardinal directions (up, down, left, right) between open cells. The path length is the number of cells visited along the path (so a 1x1 open grid has length 1). If the start or end cell is a wall, or no path exists, return `-1`.
Use breadth-first search: because every edge has unit cost in an unweighted grid, BFS explores cells in nondecreasing distance order, so the first time the target is dequeued (or about to be enqueued) gives the shortest path. A mark-on-enqueue `visited` set guarantees each cell is processed once.
Follow-up: to allow diagonal moves, expand the neighbor offsets from the 4 cardinal directions to all 8 surrounding directions — the BFS structure is otherwise unchanged.
Constraints
- 1 <= m, n
- m * n can be up to 10^5 cells
- grid[i][j] is either 0 (open) or 1 (wall)
- Movement is only up/down/left/right between open cells
- Path length counts the number of cells visited (a 1x1 open grid returns 1)
Examples
Input: ([[0,0,0],[0,1,0],[0,0,0]],)
Expected Output: 5
Explanation: A 3x3 grid with a wall in the center. The shortest path around the wall visits 5 cells, e.g. (0,0)->(0,1)->(0,2)->(1,2)->(2,2).
Input: ([[0,1],[1,0]],)
Expected Output: -1
Explanation: The two open cells are diagonal to each other; with only 4-directional moves they are disconnected, so no path exists.
Hints
- Unit-cost edges in an unweighted grid mean BFS (not DFS or Dijkstra) finds the shortest path; the first time you reach the target it is optimal.
- Check the start and end cells for walls up front — if either is a wall, immediately return -1.
- Mark a cell as visited when you enqueue it (not when you dequeue it) so it is never added to the queue twice.
- For the diagonal-moves follow-up, change the 4 cardinal offsets to all 8 surrounding offsets; the rest of the BFS stays the same.