Stack Bash - Master data structures and algorithms

Shortest path in a maze

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:
Shortest path in a binary maze

Try it

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


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

Want to confidently pass your next coding interview?

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