Katkat
Back

Find shortest path in a grid with obstacles

AmazonApplied Scientist · Onsite
MediumApplied ScientistOnsiteCoding & Algorithms

Last updated

This question evaluates understanding of pathfinding in grid-based environments, graph traversal concepts, and algorithmic complexity when navigating obstacles and boundary constraints in an unweighted 2D search space.

You are given a 2D grid of size m x n representing a maze. Each cell in the grid is either empty (0) or blocked (1).

You are also given two coordinates:

  • start = (sx, sy)
  • end = (ex, ey)

You can move from a cell to its 4-directional neighbors (up, down, left, right), but you cannot move into or through blocked cells, and you must remain inside the grid.

Return the length of the shortest path (in number of steps) from start to end. If there is no valid path, return -1.

Assumptions and details:

  • 0 <= sx, ex < m
  • 0 <= sy, ey < n
  • grid[sx][sy] == 0 and grid[ex][ey] == 0
  • 1 <= m, n <= 10^3
  • Time complexity should be efficient for the upper bounds (you may consider BFS or DFS-based approaches).

Input format (for reference):

  • m, n (integers)
  • grid as an m x n matrix of 0s and 1s
  • start coordinate
  • end coordinate

Output:

  • An integer representing the length of the shortest path, or -1 if unreachable.