cswork / libraryOpen practice workspace

Coding questions · MathWorks

Find shortest path using BFS

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 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.

Shortest Path in a Grid (BFS)

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

Example 1

Input: ([[0,0,0],[0,1,0],[0,0,0]], 0, 0, 2, 2)
Output: 4

Explanation: From (0,0) to (2,2) around the central wall: e.g. right, right, down, down = 4 steps.

Example 2

Input: ([[0,1],[1,0]], 0, 0, 1, 1)
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

  1. 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.
  2. 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.
  3. Mark a cell visited the moment you enqueue it (not when you dequeue it) to avoid pushing the same cell multiple times.
  4. Handle the corner cases up front: start == target returns 0, and a start or target that sits on a wall returns -1.