Find shortest path using BFS
Company: MathWorks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Given an m×n grid grid where grid[r][c] = 0 represents an empty cell and 1 represents a wall, a start cell (sr, sc), and a target cell (tr, tc), you may move one step at a time in four directions (up, down, left, right) into empty cells only. Return the length of the shortest path from start to target or -1 if no path exists. Describe the algorithm and its time/space complexity, and implement it in C++/Java/JavaScript.
Quick Answer: This question evaluates a candidate's proficiency with graph traversal algorithms—particularly breadth-first search—and the ability to model grid-based shortest-path problems while reasoning about time and space complexity.
Given an m×n grid `grid` where `grid[r][c] = 0` represents an empty cell and `1` represents a wall, a start cell `(sr, sc)`, and a target cell `(tr, tc)`, you may move one step at a time in four directions (up, down, left, right) into empty cells only.
Return the length of the shortest path (number of steps) from start to target, or `-1` if no path exists. If the start and target are the same cell, the answer is `0`.
Breadth-first search explores the grid level by level, so the first time the target is dequeued (or reached) it is guaranteed to be via a shortest path.
Constraints
- 1 <= m, n <= 1000
- grid[r][c] is 0 (empty) or 1 (wall)
- 0 <= sr, tr < m and 0 <= sc, tc < n
- Movement is restricted to the four orthogonal directions (no diagonals)
- You may only step into empty (0) cells
Examples
Input: ([[0,0,0],[0,1,0],[0,0,0]], 0, 0, 2, 2)
Expected Output: 4
Explanation: From (0,0) to (2,2) around the central wall: e.g. right, right, down, down = 4 steps.
Input: ([[0,1],[1,0]], 0, 0, 1, 1)
Expected Output: -1
Explanation: The target (1,1) is diagonally adjacent but walls at (0,1) and (1,0) block every orthogonal route, so it is unreachable.
Hints
- BFS, not DFS: BFS expands the grid in rings of increasing distance, so the first time you reach the target you have found the shortest path. DFS would not give you that guarantee.
- Track distance by storing (row, col, dist) in the queue, or process the queue one level at a time and increment a step counter per level.
- Mark a cell visited the moment you enqueue it (not when you dequeue it) to avoid pushing the same cell multiple times.
- Handle the corner cases up front: start == target returns 0, and a start or target that sits on a wall returns -1.