Find shortest path in a grid with obstacles

Q: Find shortest path in a grid with obstacles

This is a Coding & Algorithms interview question from Amazon for Machine Learning Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Find shortest path in a grid with obstacles

Comments (0)