Shortest Path in Binary Matrix
MediumExtra practice. This problem has no walkthrough slides. Try solving it with the pattern template on your own, and lean on the hints if you get stuck.
Question
You're given a grid of tiles where each tile is either open (0) or blocked (1). Starting from the top-left tile, you can move to any of its 8 neighboring tiles, including the 4 diagonal ones, as long as that tile is open.
Return the length of the shortest path from the top-left tile to the bottom-right tile, counted in tiles (including both endpoints). Return -1 if no such path exists.
Input: grid = [[0, 0, 1], [1, 0, 1], [1, 0, 0]]
Output: 3
Moving diagonally through the center tile connects the top-left and bottom-right corners directly, in just 3 tiles.
Input: grid = [[1]]
Output: -1
The only tile in the grid is blocked, so no path can start.
Input: grid = [[0]]
Output: 1
The starting tile and the ending tile are the same single open tile, so the path length is 1.
Clarify the problem
What are some questions you'd ask an interviewer?
Understand the problem
Take a moment to understand the problem and think of your approach before you start coding.