# Shortest path in a maze

MediumLet'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.

## Solution

### Time and Space Complexity

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

Therefore, our time complexity is

`O(V + E)`

.## 9 Essential Trees & Graphs Coding Interview Problems

Master Trees & Graphs by trying the coding challenges below.

- 1.Inorder TraversalEasy
- 2.Tree SumEasy
- 3.Tree HeightEasy
- 4.LCAMedium
- 5.Max Path SumHard
- 6.Search mazeMedium
- 7.Number of islandsMedium
- 8.Kth SmallestMedium
- 9.Sort K ArraysHard