Shortest path in a maze

Medium

Let's say you're given a maze as a binary matrix made up of 1s and 0s, along with start and end coordinates.

maze = [
    [1, 1, 1, 1],
    [1, 0, 0, 1],
    [1, 1, 1, 1],
    [0, 1, 0, 0],
]
start = (0, 0)
end = (3, 1)

A path can be formed only along cells with 1.

0 represents an obstacle that cannot be part of a path.

Assume you can move in 4 directions -- left, right, up, and down.

Write a function that returns the distance of the shortest path from the start to the end coordinate.

For example, given the above inputs, your function should return 4 as highlighted by the following path:

Try it

Before you look at the solution, try to code it yourself.

def shortest_path(maze: list[list[int]], start: tuple[int, int], end: tuple[int, int]) -> int:
    # implement shortest_path
    return -1

1def shortest_path(maze: list[list[int]], start: tuple[int, int], end: tuple[int, int]) -> int:
2    # implement shortest_path
3    return -1
4

In breadth first search, we visit all edges and vertizes.

Therefore, our time complexity is O(V + E).

Master Trees & Graphs by trying the coding challenges below.

Stack Bash helps new and veteran software engineers master data structures and algorithms for technical interviews.