Frontend School

Shortest Path in a Binary Grid

DSA
easy

Shortest Path in a Binary Grid

Easy
Graph
Breadth-First Search
Matrix
Shortest Path

Overview

Imagine a robot navigating a warehouse represented by a grid. Some cells are clear, others are blocked. The robot needs to find the quickest way from its starting point to a delivery destination. This problem challenges you to find the minimum number of steps required to reach a target cell from a start cell in a grid, avoiding obstacles. This is a fundamental problem in pathfinding and graph theory, crucial for applications like game AI, logistics, and network routing.

What you need to do / Task

Implement a function that calculates the minimum number of steps to reach a target cell from a starting cell in a given binary grid.

  1. You can only move horizontally or vertically (up, down, left, right) to adjacent cells.
  2. You cannot move into cells marked as obstacles (1).
  3. You cannot move outside the grid boundaries.
  4. Each valid move counts as one step.
  5. If the target is unreachable, return -1.

Input & output

  • grid: A 2D array of integers (number[][]) representing the maze. 0 indicates an an open path, 1 indicates an obstacle.
  • start: An array of two integers [row, col] representing the starting cell coordinates.
  • target: An array of two integers [row, col] representing the target cell coordinates.
  • Returns: An integer representing the minimum number of steps to reach the target. Returns -1 if the target is unreachable or if start or target are obstacles.

Clarifications

  • The start and target coordinates will always be within the grid boundaries.
  • If the start cell itself is an obstacle (1), or the target cell is an obstacle (1), the target is considered unreachable, and the function should return -1.
  • If start and target are the same cell and it's not an obstacle, the path length is 0.

Examples

1

Example 1

Input:

grid = [[0,0,0],[0,1,0],[0,0,0]], start = [0,0], target = [2,2]

Output:

4

Note:

Path: (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2). Total 4 steps.

2

Example 2

Input:

grid = [[0,1,0],[0,0,0],[0,1,0]], start = [0,0], target = [2,0]

Output:

6

Note:

Path: (0,0) -> (1,0) -> (1,1) -> (1,2) -> (2,2) -> (2,1) -> (2,0). Total 6 steps.

3

Example 3

Input:

grid = [[0,1,0],[0,1,0],[0,1,0]], start = [0,0], target = [0,2]

Output:

-1

Note:

The target cell [0,2] is unreachable from [0,0] due to obstacles.

Constraints

Constraints & assumptions

  • 1 <= grid.length, grid[0].length <= 200 (Grid dimensions will be at most 200x200)
  • grid[i][j] is 0 or 1.
  • start and target will be valid coordinates within the grid.

Out of scope

  • Diagonal movements are not allowed.
  • Finding all possible shortest paths. Only the length of one shortest path is required.

What interviewers evaluate

  • Ability to correctly model the problem as a graph traversal.
  • Correct application of Breadth-First Search (BFS) for shortest path in an unweighted graph.
  • Handling of edge cases (unreachable target, start/target on obstacle, start == target).
  • Code clarity, efficiency (time/space complexity), and correctness.

Loading editor...