Katkat
Back

Shortest Path in a Grid with Blocked Cells

UberSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to model a 2D grid as a graph and implement a Breadth-First Search (BFS) to find the shortest path between two points while respecting obstacles.

Shortest Path in a Grid with Blocked Cells

You are given an m x n binary grid where 0 represents an empty space and 1 represents an obstacle. You start at the top-left corner (0, 0) and aim to reach the bottom-right corner (m - 1, n - 1).

Moving is allowed in four directions: up, down, left, and right. You can only move onto grid cells that contain 0.

Write a function shortestPath(grid) that returns the minimum number of steps (number of edges) required to traverse from the start to the destination. If it is impossible to reach the destination, return -1.

Function Signature

def shortestPath(grid: List[List[int]]) -> int:

Constraints

  • m (rows) and n (columns) are between 1 and 200.
  • grid[0][0] and grid[m-1][n-1] are guaranteed to be 0.

Examples

Example 1:

Input: grid = [[0,0,0],[1,1,0],[0,0,0]]
Output: 4
Explanation: The shortest path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2).

Example 2:

Input: grid = [[0,1],[1,0]]
Output: -1
Explanation: The destination is blocked by walls.

Edge Cases

  • A grid of size 1x1.
  • A grid where the destination is completely surrounded by obstacles.
  • Paths that require significant 'zig-zagging' through the grid.

Hints

Hint 1

Since this is an unweighted shortest path problem in a grid, BFS is the most efficient traversal method.

Hint 2

Maintain a 'visited' set or modify the input grid to keep track of cells you have already processed to prevent redundant cycles.

Hint 3

Use a queue to store coordinates along with their current distance from the origin to ensure you process paths layer by layer.

Follow-up questions

  • How would your approach change if you were allowed to remove exactly one obstacle to shorten the path?
  • What is the time and space complexity of your solution in terms of grid dimensions M and N?
  • If the grid were weighted (e.g., some cells cost more to traverse than others), which algorithm would you use instead of BFS?